8

线段树碰线过。。

 Accepted



#   状态  耗时  内存占用
#1  Accepted    3ms     4.34MiB
#2  Accepted    3ms     4.25MiB
#3  Accepted    4ms     4.25MiB
#4  Accepted    4ms     4.316MiB
#5  Accepted    5ms     4.25MiB
#6  Accepted    5ms     4.25MiB
#7  Accepted    30ms    8.625MiB
#8  Accepted    39ms    6.422MiB
#9  Accepted    50ms    6.297MiB
#10     Accepted    66ms    5.375MiB
#11     Accepted    63ms    10.977MiB
#12     Accepted    69ms    11.027MiB
#13     Accepted    106ms   7.293MiB
#14     Accepted    79ms    7.324MiB
#15     Accepted    386ms   22.543MiB
#16     Accepted    537ms   22.422MiB
#17     Accepted    693ms   22.418MiB
#18     Accepted    846ms   22.668MiB
#19     Accepted    1003ms  23.625MiB
#20     Accepted    1051ms  23.875MiB
代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX = 1000000 + 2; 
using namespace std;
int tree[MAX * 8];
int data[MAX];
int lazy[MAX * 8];
int n, m, tot;
void check(int rt)
{
    if(tree[rt] < 0) 
    {
        printf("-1\n%d", tot);
        exit(0);
    }
}
void up(int rt)
{
    tree[rt] = min(tree[rt << 1] , tree[rt << 1 | 1]);
    check(rt);
} 
void built(int l, int r, int rt)
{
    if(l == r) 
    {
        tree[rt] = data[l];
        return;
    }
    int m = l + (r - l) / 2;
    built(l, m, rt << 1);
    built(m + 1, r, rt << 1 | 1); 
    up(rt);
}
void down(int rt, int L, int R)
{
    if(lazy[rt])
    {
        int m = L + (R - L) / 2;
        
        lazy[rt * 2] += lazy[rt];
        lazy[rt * 2 + 1] += lazy[rt];
        tree[rt * 2] -= lazy[rt];
        tree[rt * 2 + 1] -= lazy[rt];
        lazy[rt] = 0; 
    }
}
void modify(int L, int R, int l, int r, int val, int rt)
{

    if(L >= l && R <= r)
    {
        tree[rt] -= val;
        check(rt);
        lazy[rt] += val;
        return;
    }
    check(rt);
    down(rt, L, R);
    int m = L + (R - L) / 2;
    if(m >= l) modify(L, m, l, r, val, rt * 2);
    if(m < r) modify(m + 1, R, l, r, val, rt * 2 + 1);
    up(rt); 
} 
void solve(int n, int m)
{
    int a, b, c;
    for(int i = 1; i <= m; i++)
    {
        tot = i;
        scanf("%d %d %d", &c, &a, &b);
        modify(1, n, a, b, c, 1);
    }
    printf("0");
    return;
}
void init(int n, int m)
{
    
    for(int i = 1; i <= n; i++)
        scanf("%d", &data[i]);
    built(1, n, 1);
}
int main()
{
//  freopen("in.txt","r", stdin);
    scanf("%d %d", &n, &m);
    init(n, m);
    solve(n, m);
    return 0;
}

3

猫粮寸断 LV 10 @ 7 年前

坑点：
1.修改前缀和时要在上一个状态进行修改，不能从头到尾加
2.需要在一开始特判全都能过，否则一TLE一WA
3.并不需要开long long
还有一些细碎的二分之类，自己注意

#include<iostream>
#include<cstring>
using namespace std;
int a[1000100],qian[1000010],gai[1000010];

struct cun{
    int tou,wei,shu;
}q[1000010];

int main() 
{
    int n,i,left,right,mid,ci,m,last=1,haha=0,ans;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(i=1;i<=m;i++)
     cin>>q[i].shu>>q[i].tou>>q[i].wei;
    left=0;
    right=m;
    for(i=1;i<=m;i++) 
     {
        gai[q[i].tou]+=q[i].shu;
        gai[q[i].wei+1]-=q[i].shu;
     } 
    for(i=1;i<=n;i++)
     {
      qian[i]=qian[i-1]+gai[i];
       if(qian[i]>a[i])
        break;
    }
    if(i>n)
    {
        cout<<0;
        return 0;
    }
    memset(qian,0,sizeof(qian));
    memset(gai,0,sizeof(gai));
    while(left<=right)
    {
     mid=(left+right)/2;
     if(mid>haha)
     {
        for(i=haha+1;i<=mid;i++)
         {
            gai[q[i].tou]-=q[i].shu;
            gai[q[i].wei+1]+=q[i].shu;
         }
     }
     else
     {
        for(i=mid+1;i<=haha;i++)
        {
            gai[q[i].tou]+=q[i].shu;
            gai[q[i].wei+1]-=q[i].shu;
        }
     }
     haha=mid;
     for(i=1;i<=n;i++)
     {
        qian[i]=qian[i-1]+gai[i];
         if(qian[i]+a[i]<0)
          break;
     }
     if(i>n)
      {
       left=mid+1;
      } 
     else
     { 
      ans=mid; 
      right=mid-1;
     } 
    }
   cout<<-1<<endl;
   cout<<ans;
     
    return 0;
}

2

污龙tea LV 8 @ 7 年前

一道较为基础的线段树题目。
大体的思路是每输入一组数据，用find函数查看一下是否可行；
如果可以，就调用add函数改变线段树中的数值；
如果不行，就输出-1，还有当前的申请序号，return 0；
如果一直没有return 0，说明都可以，输出0，return 0；
对于find函数大体思路：
区间最值与给的教室数大小关系的判断，都可以就可以，任何一个不行就都不行；
对于add函数大体思路：
当find发现可以借的时候才调用；
线段树对于区间最值的维护，对于符合的根节点tree[i]-=教室数；
并用lazy数组维护；
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int tree[24000010],a[600010],lazy[24000010],n,m,s,r,ans;
void read(int &x)
{
x=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void build(int x,int l,int r)
{
if (l==r)
{
tree[x]=a[l];
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x]=min(tree[x<<1],tree[x<<1|1]);
}
void pushdown(int node,int l,int r)
{
tree[node<<1]+=lazy[node];
lazy[node<<1]+=lazy[node];
tree[node<<1|1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
lazy[node]=0;
}
void add(int node,int l,int r,int x,int y,int z)
{
if (l==x&&r==y)
{
tree[node]-=z;
lazy[node]-=z;
return;
}
if (lazy[node]) pushdown(node,l,r);
int mid=(l+r)>>1;
if (y<=mid)
add(node<<1,l,mid,x,y,z);
else
if (mid<x)
add(node<<1|1,mid+1,r,x,y,z);
else
{
add(node<<1,l,mid,x,mid,z);
add(node<<1|1,mid+1,r,mid+1,y,z);
}
tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
bool find(int node,int l,int r,int x,int y,int z)
{
if(r==y&&x==l)
{
if (tree[node]>=z)
return true;
else
return false;
}
if (lazy[node]) pushdown(node,l,r);
int mid=(l+r)/2;
if (y<=mid)
return find(node<<1,l,mid,x,y,z);
else
if (x>mid)
return find(node<<1|1,mid+1,r,x,y,z);
else
return find(node<<1,l,mid,x,mid,z)&find(node<<1|1,mid+1,r,mid+1,y,z);
}
int main()
{
read(n);
read(m);
for(int i=1;i<=n;i++)
read(a[i]);
build(1,1,n);
for (int i=1;i<=m;i++)
{
int x,y,z;
read(z);
read(x);
read(y);
if (find(1,1,n,x,y,z))
{
add(1,1,n,x,y,z);
}
else
{
cout<<-1<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<0<<endl;
}

1

暗燚 LV 8 @ 6 年前

二分答案
知识准备：使用前缀数组处理数组区间标记，单点查询。
定义sum[i]=j ，假设我们要修改多个区间 [a,b]，区间中每个元素都+c；然后我们询问每一个点，问值为多少？（N<=100w）
如果真正去标记区间[a,b]的话，时间复杂度为 O(n^2) ，显然不行。
那么我们就用一种特殊的方法来处理：
sum[a] + = c; sum[ b + 1 ] - = c;
然后我们从前到后对sum数组累加，每累加一次sum[i]就会得到点i的值。
前缀数组标记的时间复杂度为O(1),单点查询的复杂度为O(n);
借教室的题意分析：从前到后找到第一个不符合要求的订单即可！
也就是check (1,ans-1)==1;
而check (1,ans)==0的那个点ans。显然符合二分的思想，二分的是订单的编号，难点就是如何维护前缀数组sum[ ] ?
我们引入now变量，初值为0，记录当前sum数组中已经记录了从1到now的所有的订单的数据。Int mid=(l+r)>>1;
if(now<mid) 说明要把[now+1,mid]的订单加入到sum数组。
else(now>=mid) 说明要把[mid+1,now]的订单从sum数组中删除。
然后更新now=mid。
本题还有一个难点就是如何确定二分答案的左右端点！
左端点很好得出，可以为0或者1
右端点就有说道了，因为有一种情况是所有的订单都满足和第m个订单不满足情况的区别。
所有我们引入一个多余的空订单，即右端点r=m+1.
庆幸的是输出“0”的测试点并不多——防骗分。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int f,n;
int room[1000001],d[1000001],c[1000001];
int s[1000001],t[1000001],a[1000001];
bool check(int k)
{
    if(k>f)
    {
        for(int i=f+1;i<=k;i++)
        {
            a[s[i]]-=d[i];
            a[t[i]+1]+=d[i];
        }
    }
    else
    {
        for(int i=k+1;i<=f;i++)
        {
            a[s[i]]+=d[i];
            a[t[i]+1]-=d[i];
        }
    }
    f=k;
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+a[i];
        if(c[i]+room[i]<0)
            return false;
    }
    return true;
}
int main()
{
    int m,ans;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&room[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&d[i],&s[i],&t[i]);
    }
    int l=1,r=m+1;
    while(l<r)
    {
            int mid=(l+r)>>1;
            if(check(mid))
                l=mid+1;
            else
                r=mid;
    }
    if(check(m))
    {
        printf("0");
        return 0;
    }
    printf("-1\n%d",l);
    return 0;
}

1

2351599120 LV 9 @ 7 年前

二分答案
跑的飞起

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int f,n;
int room[1000001],mon[1000001],c[1000001];
int s[1000001],t[1000001],a[1000001];
bool check(int k)
{
    if(k>f)
    {
        for(int i=f+1;i<=k;i++)
        {
            a[s[i]]-=mon[i];
            a[t[i]+1]+=mon[i];
        }
    }
    else
    {
        for(int i=k+1;i<=f;i++)
        {
            a[s[i]]+=mon[i];
            a[t[i]+1]-=mon[i];
        }
    }
    f=k;
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+a[i];
        if(c[i]+room[i]<0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int m,l=0,r,mid,ans;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&room[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&mon[i],&s[i],&t[i]);
    }
    r=m;
    if(check(m)==true)
    {
        printf("0");
        return 0;
    }
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid)==true)
        {
            l=mid+1;
        }
        else
        {
            ans=mid;
            r=mid-1;
        }
    }
    printf("-1\n%d",ans);
    return 0;
}

1

vonhyou LV 8 @ 7 年前

二分答案。。。常数优化写不下去了就这样吧。。。交上去之后还挺快
依旧是循环展开+读入优化+寄存器变量，没啥新鲜的

#include <cstdio>
#include <cctype>

const int MAXN = 1000010;

int n, m, ans, a[MAXN], s[MAXN], t[MAXN], k[MAXN];

//读入优化
inline int ReadInt() {
  char _c; int sum(0);
  while (!isdigit(_c = getchar()));
  do sum = sum * 10 + _c - '0';
  while (isdigit(_c = getchar()));
  return sum;
}

//其实judge也是可以搞些小优化的但是我不想写了。。。
inline bool judge(int x) {
  //memset(num, 0, sizeof(num));
  int num[MAXN] = {0}; //我猜测这样可能比memset快一些
  for (register int i = 1; i <= x; ++i) 
    num[s[i]] += k[i], num[t[i] + 1] -= k[i];
  register int sa(0);
  for (register int i = 1; i <= n; ++i) {
    sa += num[i];
    if (sa > a[i])
      return false;
  }
  return true;
}

int main() {
    //前方高能，密集恐惧症患者慎入【滑稽
    //好多的ReadInt()
  n = ReadInt(), m = ReadInt();
  for (register int i = 1; i < n; i += 2)
    a[i] = ReadInt(), a[i + 1] = ReadInt();
  (n & 1) && (a[n] = ReadInt()); //这里就是if else好孩子不要学
  for (register int i = 1; i < m; i += 2)
    k[i] = ReadInt(), s[i] = ReadInt(), t[i] = ReadInt(),
      k[i + 1] = ReadInt(), s[i + 1] = ReadInt(), t[i + 1] = ReadInt();
  (m & 1) && (k[m] = ReadInt(), s[m] = ReadInt(), t[m] = ReadInt());
  register int l = 1, r = m, mid = -1;
  while (l <= r) {
    mid = (l + r) >> 1;
    (judge(mid)) ? (l = mid + 1, ans = mid) : (r = mid - 1);
  }
    //其实这里还可以写的更优美
  (ans < m) ? printf("-1\n%d\n", ans + 1) : printf("0\n");
  return 0;
}

qwq就是这样

#1 Accepted 8ms 10.0MiB
#2 Accepted 7ms 10.0MiB
#3 Accepted 10ms 10.07MiB
#4 Accepted 10ms 10.094MiB
#5 Accepted 8ms 10.07MiB
#6 Accepted 10ms 10.0MiB
#7 Accepted 39ms 10.488MiB
#8 Accepted 45ms 10.469MiB
#9 Accepted 44ms 12.418MiB
#10 Accepted 48ms 16.051MiB
#11 Accepted 46ms 12.496MiB
#12 Accepted 43ms 14.527MiB
#13 Accepted 44ms 12.508MiB
#14 Accepted 45ms 14.598MiB
#15 Accepted 289ms 19.301MiB
#16 Accepted 317ms 19.305MiB
#17 Accepted 349ms 19.539MiB
#18 Accepted 367ms 19.406MiB
#19 Accepted 395ms 19.301MiB
#20 Accepted 393ms 19.305MiB

比线段树要快

vonhyou @ 7 年前

其实我一开始也是想的线段树，但是我本地测的貌似有卡线段树的数据，需要优化
call_me_std @ 7 年前

全部加register啊！
为啥用咸鱼读优不写iobuff或者mmap?
call_me_std @ 7 年前

全部加register啊！
为啥用咸鱼读优不写iobuff或者mmap?
vonhyou @ 7 年前

@call_me_std: qwq好久之前写题全用register挂掉了。。。至于后两个我第一次听说qwq待我去学学
vonhyou @ 7 年前

@call_me_std: %%%谢谢dalao

1

LN_handsome LV 9 @ 9 年前

var a,ca,d,s,t:array[0..1000005] of longint;
i,j,k,l,n,m,r,o,now:longint;
tmt,ans:int64;
p:boolean;
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to m do read(d[i],s[i],t[i]);
d[m+1]:=a[1]+1; s[m+1]:=1; t[m+1]:=1;
l:=1; r:=m+1; now:=0;
while l<=r do
begin
ans:=l+((r-l) shr 1);
if ans>now then
for i:=now+1 to ans do
begin
inc(ca[s[i]],d[i]);
dec(ca[t[i]+1],d[i]);
end
else
for i:=ans+1 to now do
begin
dec(ca[s[i]],d[i]);
inc(ca[t[i]+1],d[i]);
end;
now:=ans;
tmt:=0;
p:=true;
for i:=1 to n do
begin
tmt:=tmt+ca[i];
if tmt>a[i] then begin p:=false; break; end;
end;
if p then l:=ans+1
else r:=ans-1;
end;
if l=m+1 then writeln(0)
else
begin
writeln(-1);
writeln(l);
end;
end.
数组把int64改成longint，最慢的从900+ms变成了600+ms，洛谷上更是从超时两个点到最慢的600+ms，告诉我为什么。
思路：恩二分的话不用讲，然后就是判断满不满足的部分。
用到了一个记录的数组，这个数组的性质是：ca[i]表示a[i]这个数比a[i-1]大ca[i]，然后我想你已经知道了。
这个数组其实就是记录一个差值，然后使区间加减的复杂度变成了O（1），但是查询就是O（n）（查询一个和查询N个复杂度一样）。

0

周子祥 LV 8 @ 2 周前

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
int num,s,w;
}q[200010];

struct node1
{
int num,s,w;
}win[100010];

struct node2
{
int num,s,w;

}lose[100010];
int cmp(const node&x,const node&y)
{
if(x.s>y.s)
return 1;
if(x.s<y.s)
return 0;
return x.num<y.num;
}
int main()
{
int n,r,p,i,len1,len2;
scanf("%d%d%d",&n,&r,&p);
for(i=1;i<=2*n;i++)
scanf("%d",&q[i].s);
for(i=1;i<=2*n;i++)
{
q[i].num=i;
scanf("%d",&q[i].w);
}
sort(q+1,q+2*n+1,cmp);
while(r)
{
for(i=1;i<=n;i++)
if(q[2*i].w>q[2*i-1].w)
{
q[2*i].s++;
win[i].num=q[2*i].num;
win[i].s=q[2*i].s;
win[i].w=q[2*i].w;
lose[i].num=q[2*i-1].num;
lose[i].s=q[2*i-1].s;
lose[i].w=q[2*i-1].w;
}
else
{
q[2*i-1].s++;
win[i].num=q[2*i-1].num;
win[i].s=q[2*i-1].s;
win[i].w=q[2*i-1].w;
lose[i].num=q[2*i].num;
lose[i].s=q[2*i].s;
lose[i].w=q[2*i].w;
}
len1=1;
len2=1;
while(len1<=n&&len2<=n)
{
if(win[len1].s>lose[len2].s)
{
q[len1+len2-1].num=win[len1].num;
q[len1+len2-1].s=win[len1].s;
q[len1+len2-1].w=win[len1].w;
len1++;
}
if(win[len1].s<lose[len2].s)
{
q[len1+len2-1].num=lose[len2].num;
q[len1+len2-1].s=lose[len2].s;
q[len1+len2-1].w=lose[len2].w;
len2++;
}
if(win[len1].s==lose[len2].s)
if(win[len1].num<lose[len2].num)
{
q[len1+len2-1].num=win[len1].num;
q[len1+len2-1].s=win[len1].s;
q[len1+len2-1].w=win[len1].w;
len1++;
}
else
{
q[len1+len2-1].num=lose[len2].num;
q[len1+len2-1].s=lose[len2].s;
q[len1+len2-1].w=lose[len2].w;
len2++;
}
}
while(len1<=n)
{
q[len1+len2-1].num=win[len1].num;
q[len1+len2-1].s=win[len1].s;
q[len1+len2-1].w=win[len1].w;
len1++;
}
while(len2<=n)
{
q[len1+len2-1].num=lose[len2].num;
q[len1+len2-1].s=lose[len2].s;
q[len1+len2-1].w=lose[len2].w;
len2++;
}
r--;
}
printf("%d",q[p].num);
return 0;
}

0

周子祥 LV 8 @ 2 周前

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX = 1000000 + 2;
using namespace std;
int tree[MAX * 8];
int data[MAX];
int lazy[MAX * 8];
int n, m, tot;
void check(int rt)
{
if(tree[rt] < 0)
{
printf("-1\n%d", tot);
exit(0);
}
}
void up(int rt)
{
tree[rt] = min(tree[rt << 1] , tree[rt << 1 | 1]);
check(rt);
}
void built(int l, int r, int rt)
{
if(l == r)
{
tree[rt] = data[l];
return;
}
int m = l + (r - l) / 2;
built(l, m, rt << 1);
built(m + 1, r, rt << 1 | 1);
up(rt);
}
void down(int rt, int L, int R)
{
if(lazy[rt])
{
int m = L + (R - L) / 2;

lazy[rt * 2] += lazy[rt];
lazy[rt * 2 + 1] += lazy[rt];
tree[rt * 2] -= lazy[rt];
tree[rt * 2 + 1] -= lazy[rt];
lazy[rt] = 0;
}
}
void modify(int L, int R, int l, int r, int val, int rt)
{

if(L >= l && R <= r)
{
tree[rt] -= val;
check(rt);
lazy[rt] += val;
return;
}
check(rt);
down(rt, L, R);
int m = L + (R - L) / 2;
if(m >= l) modify(L, m, l, r, val, rt * 2);
if(m < r) modify(m + 1, R, l, r, val, rt * 2 + 1);
up(rt);
}
void solve(int n, int m)
{
int a, b, c;
for(int i = 1; i <= m; i++)
{
tot = i;
scanf("%d %d %d", &c, &a, &b);
modify(1, n, a, b, c, 1);
}
printf("0");
return;
}
void init(int n, int m)
{

for(int i = 1; i <= n; i++)
scanf("%d", &data[i]);
built(1, n, 1);
}
int main()
{
// freopen("in.txt","r", stdin);
scanf("%d %d", &n, &m);
init(n, m);
solve(n, m);
return 0;
}

0

Amove LV 8 @ 6 年前

每个测试点不止1秒？

0

Mark__Zuckerburg LV 8 @ 7 年前

差分+二分答案

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring> 
using namespace std;
#define Maxn 1000001
long long n,m,s[Maxn],t[Maxn],le,ri,mid,ans,sum[Maxn];
long long r[Maxn],d[Maxn],minn=Maxn,e;
bool check(long long x)
{
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=x;i++)
    {
        sum[s[i]]+=d[i];
        sum[t[i]+1]-=d[i];
    }
    long long ss=0;
    for(int i=1;i<=n;i++)
    {
        ss+=sum[i];
        if(ss>r[i])
        {
            minn=min(minn,x);
            return false;
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>r[i];
    for(int i=1;i<=m;i++)
    cin>>d[i]>>s[i]>>t[i];
    le=1;
    ri=m;
    while(le<ri)
    {
        mid=(le+ri)/2;
        if(check(mid))
        le=mid+1;
        else
        ri=mid;
    }
    if(minn==Maxn)
    cout<<0;
    else
    cout<<-1<<endl,cout<<minn<<endl;
    return 0;
}

就完事了

0

wanghaozhou LV 8 @ 7 年前

Lazy线段树，1234ms居然没TLE

状态耗时内存占用

#1 Accepted 4ms 380.0 KiB
#2 Accepted 4ms 348.0 KiB
#3 Accepted 3ms 384.0 KiB
#4 Accepted 4ms 372.0 KiB
#5 Accepted 4ms 360.0 KiB
#6 Accepted 4ms 348.0 KiB
#7 Accepted 42ms 3.219 MiB
#8 Accepted 57ms 3.734 MiB
#9 Accepted 76ms 3.836 MiB
#10 Accepted 96ms 2.375 MiB
#11 Accepted 104ms 2.859 MiB
#12 Accepted 116ms 2.492 MiB
#13 Accepted 150ms 4.25 MiB
#14 Accepted 116ms 3.082 MiB
#15 Accepted 440ms 18.121 MiB
#16 Accepted 619ms 17.84 MiB
#17 Accepted 859ms 17.824 MiB
#18 Accepted 943ms 16.742 MiB
#19 Accepted 1185ms 18.117 MiB
#20 Accepted 1234ms 18.461 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

const int maxn=1000001;
struct fff
{
    int minn,lazy;
}node[(maxn<<2)+(maxn<<1)];
int n,m;

inline void pushup(int u)
{
    node[u].minn=min(node[u<<1].minn,node[u<<1|1].minn);
}

inline void pushdown(int u)
{
    if(node[u].lazy)
    {
        node[u<<1].lazy+=node[u].lazy;
        node[u<<1|1].lazy+=node[u].lazy;
        node[u<<1].minn-=node[u].lazy;
        node[u<<1|1].minn-=node[u].lazy;
        node[u].lazy=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) { read(node[u].minn); return ; }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

int query(int u,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return node[u].minn;
    pushdown(u);
    int mid=(l+r)>>1;
    if(R<=mid) return query(u<<1,l,mid,L,R);
    if(L>mid) return query(u<<1|1,mid+1,r,L,R);
    return min(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R));
}

void update(int u,int l,int r,int L,int R,int val)
{
    if(L<=l&&r<=R)
    {
        node[u].lazy+=val;
        node[u].minn-=val;
        return ;
    }
    pushdown(u);
    int mid=(l+r)>>1;
    if(L<=mid) update(u<<1,l,mid,L,R,val);
    if(R>mid) update(u<<1|1,mid+1,r,L,R,val);
    pushup(u);
    return ;
}

int main()
{
    read(n); read(m);
    build(1,1,n);
    for (register int cas=1,d,s,j;cas<=m;++cas)
    {
        read(d); read(s); read(j);
        int num=query(1,1,n,s,j);
        if(num<d) {printf("-1\n%d",cas); return 0;}
        update(1,1,n,s,j,d);
    }
    printf("0");
    return 0;
}

0

xianggulinger LV 8 @ 7 年前

二分：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int n, m;
int ma[5000000];
int nu[5000000], be[5000000], ed[5000000];
int oka[5000000];
bool ok(int x){
    For(i, 1, n){
        oka[i] = 0;
    }
    For(i, 1, x){
        oka[be[i]] += nu[i];
        oka[ed[i] + 1] -= nu[i];
    }
    int t = 0;
    For(i, 1, n){
        t += oka[i];
        if (t > ma[i]){
            return false;
        }
    }
    return true;
}
int bi(int l, int r){
    if (l == r){
        return l;
    }
    int t = (l + r) / 2;
    if (ok(t)){
        return bi(t + 1, r);
    } else{
        return bi(l, t);
    }
}
int main(){
    cin >> n >> m;
    For(i, 1, n){
        cin >> ma[i];
    }
    For(i, 1, m){
        cin >> nu[i] >> be[i] >> ed[i];
    }
    if (ok(m)){
        cout << 0 << endl;
        return 0;
    }
    int ans = bi(1, m);

    cout << -1 << endl << ans << endl;

    return 0;
}
/*
 *
5 2
100 10001 100 1000 1000
1 2 3
1 1 2
 */

线段树：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int l[10000000], r[10000000], ma[10000000], mi[10000000], sp[10000000];
int n, m;

void in(int le, int ri, int k){
    l[k] = le;
    r[k] = ri;
    if (le == ri){
        mi[k] = ma[le];
        return;
    }
    int mid = (le + ri) / 2;
    in(le, mid, 2 * k);
    in(mid + 1, ri, 2 * k + 1);
    mi[k] = min(mi[2 * k], mi[2 * k + 1]);
}
int smi(int gl, int gr, int k){
    if (gl == l[k] && gr == r[k]){
        return (mi[k] + sp[k]);
    }
    int pm = (l[k] + r[k]) / 2;
    if (gr <= pm){
        return (smi(gl, gr, 2 * k) + sp[k]);
    }
    if (gl >= pm + 1){
        return (smi(gl, gr, 2 * k + 1) + sp[k]);
    }
    return (min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1)) + sp[k]);
}

void oc(int gl, int gr, int gn, int k){
    if (gl == l[k] && gr == r[k]){
        sp[k] -= gn;
        return;
    }
    int pm = (l[k] + r[k]) / 2;
    if (gr <= pm){
        oc(gl, gr, gn, 2 * k);
        mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]);
        return;
    }
    if (gl >= pm + 1){
        oc(gl, gr, gn, 2 * k + 1);
//        mi[k] = min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1));
        mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]);
        return;
    }
    oc(gl, pm, gn, 2 * k);
    oc(pm + 1, gr, gn, 2 * k + 1);
//    mi[k] = min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1));
    mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]);
}
int main(){
    cin >> n >> m;
    For(i, 1, n){
        scanf("%d", &ma[i]);
    }
    in(1, n, 1);
    For(tosn, 1, m){
        int num, be, en;
        cin >> num >> be >> en;
//        cout << smi(be, en, 1) << ' ';
//        cout << smi(be, en, 1) << endl;
        if (smi(be, en, 1) < num){
            cout << -1 << endl << tosn << endl;
            return 0;
        }
        oc(be, en, num, 1);
//        For(i, 1, n){
//            cout << smi(i, i, 1) << ' ';
//        }
//
//        cout << endl;
    }
    cout << 0 << endl;
    return 0;
}

0

Sky1231 (sky1231) LV 10 @ 7 年前

2分

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int a[1048576+1];
int s[1048576+1];
int t[1048576+1];
int num[1048576+1];
int sum[1048576+1];

int check_1(int x)
{
    memset(sum,0,sizeof(sum));
    for (int i=1;i<=x;i++)
        sum[s[i]]+=num[i],sum[t[i]+1]-=num[i];
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        ans+=sum[i];
        if (ans>a[i])
            return 0;
    }
    return 1;
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=m;i++)
            scanf("%d%d%d",&num[i],&s[i],&t[i]);
        int left,right;
        for (left=1,right=m;right-left>1;)
        {
            int mid=(left+right)/2;
            if (check_1(mid))
                left=mid;
            else
                right=mid;
        }
        int ans=oo_max;
        if (check_1(left)==0)
            ans=left;
        else if (check_1(right)==0)
            ans=right;
        if (ans<oo_max)
        {
            printf("%d\n",-1);
            printf("%d\n",ans);
        }
        else
            printf("%d\n",0);
    }
}

Segment Tree

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct segment_tree_1
{
    int l,r,mid,x,lazy;
}st[2*1048576+2];

int n,m;
int a[1048576+1];

void build_segment_tree_1(int now,int l,int r)
{
    st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2,st[now].lazy=0;
    if (l<r)
    {
        if (l<=st[now].mid)
            build_segment_tree_1(now*2,l,st[now].mid);
        if (st[now].mid+1<=r)
            build_segment_tree_1(now*2+1,st[now].mid+1,r);
    }
    if (l==r)
        st[now].x=a[l];
    else
        st[now].x=min(st[now*2].x,st[now*2+1].x);
}

void push_down_1(int now)
{
    if (st[now].lazy)
    {
        st[now*2].lazy+=st[now].lazy,st[now*2+1].lazy+=st[now].lazy;
        st[now*2].x-=st[now].lazy,st[now*2+1].x-=st[now].lazy;
        st[now].lazy=0;
    }
}

void update_1(int now,int l,int r,int x)
{
    if (st[now].l==l&&st[now].r==r)
    {
        st[now].x-=x;
        st[now].lazy+=x;
        return;
    }
    else
    {
        push_down_1(now);
        if (r<=st[now].mid)
            update_1(now*2,l,r,x);
        else if (st[now].mid+1<=l)
            update_1(now*2+1,l,r,x);
        else
            update_1(now*2,l,st[now].mid,x),update_1(now*2+1,st[now].mid+1,r,x);
        st[now].x=min(st[now*2].x,st[now*2+1].x);
    }
}

int sum_1(int now,int l,int r)
{
    if (st[now].l==l&&st[now].r==r)
        return st[now].x;
    else
    {
        push_down_1(now);
        if (r<=st[now].mid)
            return sum_1(now*2,l,r);
        else if (st[now].mid+1<=l)
            return sum_1(now*2+1,l,r);
        else
            return min(sum_1(now*2,l,st[now].mid),sum_1(now*2+1,st[now].mid+1,r));
    }
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        int flag=0;
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build_segment_tree_1(1,1,n);
        for (int i=1;i<=m;i++)
        {
            int l,r,x;
            scanf("%d%d%d",&x,&l,&r);
            if (flag==0)
            {
                if (sum_1(1,l,r)>=x)
                    update_1(1,l,r,x);
                else
                {
                    printf("%d\n",(flag=-1));
                    printf("%d\n",i);
                }
            }
        }
        if (flag==0)
            printf("%d\n",flag);
    }
}

sky1231 @ 7 年前

很H2O的题

0

半仙胡小桃 LV 8 @ 7 年前

2012NOIP DAY2T1
方法1：线段树
使用线段树来维护一个区间的最小值，每次对于输入的L,R区间进行区间修改，如果最小值<0，则无法成功借教室（加了一大堆玄学优化，终于勉强没T）

#include <cstdio>
#include <stdlib.h>
using namespace std;
const int maxn=1e6+100;
struct tree{
    int minn;
    int l,r;
    int adi;
}st[maxn*4];
int a[maxn];
int w;
inline int min(int a,int b)
{
     return a < b ? a : b;
}
void build(int o,int l,int r)
{
    st[o].l=l,st[o].r=r;
    if(l==r)
    {
        st[o].minn=a[l];
        return;
    }
    int mid=(r+l)>>1;
    
    build((o<<1),l,mid);
    build((o<<1)|1,mid+1,r);
    
    st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn);
}
inline void push_down(int o)
{
    int add=st[o].adi;
    st[o].adi=0;
    
    st[(o<<1)].adi+=add;
    st[(o<<1)|1].adi+=add;
    
    st[(o<<1)].minn+=add;
    st[(o<<1)|1].minn+=add;
}
inline void query(int o,int ql,int qr,int ad)
{
    int l=st[o].l,r=st[o].r;
    
    if(l==ql&&r==qr)
    {
        st[o].adi+=ad;
        st[o].minn+=ad;
        if(st[o].minn<0)
         {
            printf("-1\n%d\n",w);
            exit(0);
         }
        return;
    }
    if(st[o].adi) push_down(o);
    
    int mid=(l+r)>>1;
    
    if(qr<=mid) query((o<<1),ql,qr,ad);
     else if(ql>mid)  query((o<<1)|1,ql,qr,ad);
      else query((o<<1),ql,mid,ad),query((o<<1)|1,mid+1,qr,ad);
    
    st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn);
}
inline int read()
{
    int data=0,w=1; char ch=0;
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
    return data*w;
}
int main()
{
    int n,m;
    
    n=read();
    m=read();
    
    for (int i = 1; i <= n; i++) 
    {
        char c = getchar();            
        while(c < '0' || c > '9')
            c = getchar();
        while(c >= '0' && c <= '9') 
        {
            a[i] *= 10;
            a[i] += c - '0';
            c = getchar();
        }
    }
    
    build(1,1,n);
    
    for(int i=1;i<=m;i++)
    {
        int x,y,t;
        t=read();
        x=read();
        y=read();
        w=i;
        query(1,x,y,-t);
    }
    
    printf("0");
    
    return 0;
}

方法2：二分+差分
二分能够成功的方案数，用差分进行区修改，暴力判断有没有超出限制的，时间复杂度O（nlogn）
其实跟线段树的复杂度相同，只是常数比较小，在数据爆炸的题里会快不少！

#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <cstring> 
using namespace std;
const int maxn=1001000;
struct tree{
    int l,r,t;
}a[maxn];
int d[maxn];
int b[maxn];
inline int read()
{
    int data=0,w=1; char ch=0;
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
    return data*w;
}
int n,m;
inline bool check(int mid)
{
    memset(b,0,sizeof(b));
    
    for(int i=1;i<=mid;i++)
     b[a[i].l]+=a[i].t,b[a[i].r+1]-=a[i].t;
    
    int s=0;
    
    for(int i=1;i<=n;i++)
     {
        s+=b[i];
        if(s>d[i])
         return 0;
     }
    
    return 1; 
}
int main()
{
    n=read();
    m=read();
    
    for(int i=1;i<=n;i++)
     d[i]=read();
    
    for(int i=1;i<=m;i++)
      a[i].t=read(),a[i].l=read(),a[i].r=read();
    
    int l=1;
    int r=m;
    int ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(!check(mid))
         ans=mid,r=mid-1;
        else 
         l=mid+1;
    }
    
    if(!ans)
     printf("0");
    else
     printf("-1\n%d",ans);
     
    return 0;
}

0

z20c12h LV 9 @ 7 年前

一击！！！

#include<iostream>
#include<cstdio>
#define INF (0x3f3f3f3f)
using namespace std;
struct DA {int d,s,t;} da[1000010];
struct SGT {int l,r,mi,lz;} sgt[1000010<<2];
int n,m;
int spt[1000010];
int rint () {int num=0,f=1;char cc=getchar();while(cc<'0'||cc>'9') {if (cc=='-') f=-1;cc=getchar();}while(cc>='0'&&cc<='9') {num=num*10+cc-'0';cc=getchar();}return num*f;}
void sgtps (int id) {sgt[id].mi=min(sgt[id<<1].mi,sgt[id<<1|1].mi);return;}
void sgtdn (int id) {
    
    sgt[id<<1].lz+=sgt[id].lz,sgt[id<<1].mi+=sgt[id].lz;
    sgt[id<<1|1].lz+=sgt[id].lz,sgt[id<<1|1].mi+=sgt[id].lz;
    sgt[id].lz=0;
    
}
void sgtbd (int l,int r,int id) {
    
    sgt[id].l=l,sgt[id].r=r,sgt[id].lz=0;
    if (l==r) {sgt[id].mi=spt[l];return;}
    sgtbd(l,(l+r)>>1,id<<1),sgtbd(((l+r)>>1)+1,r,id<<1|1); 
    sgtps(id); 
        
}
void sgtad (int l,int r,int val,int id) {
    
    if (sgt[id].r<l||sgt[id].l>r) return;
    if (sgt[id].l==l&&sgt[id].r==r) {sgt[id].lz+=val,sgt[id].mi+=val;return;}
    sgtdn(id);
    if (r<((sgt[id].l+sgt[id].r)>>1)) sgtad(l,r,val,id<<1);
    else if (l>((sgt[id].l+sgt[id].r)>>1)) sgtad(l,r,val,id<<1|1);
    else sgtad(l,(sgt[id].l+sgt[id].r)>>1,val,id<<1),sgtad(((sgt[id].l+sgt[id].r)>>1)+1,r,val,id<<1|1);
    sgtps(id);
        
}
int sgtmi (int l,int r,int id) {
    
    if (sgt[id].r<l||sgt[id].l>r) return INF;
    if (sgt[id].l==l&&sgt[id].r==r) return sgt[id].mi;
    sgtdn(id);
    if (r<((sgt[id].l+sgt[id].r)>>1)) return sgtmi(l,r,id<<1);
    else if (l>((sgt[id].l+sgt[id].r)>>1)) return sgtmi(l,r,id<<1|1);
    else return min(sgtmi(l,(sgt[id].l+sgt[id].r)>>1,id<<1),sgtmi(((sgt[id].l+sgt[id].r)>>1)+1,r,id<<1|1));
    sgtps(id);
        
}
int main () {
    
    ios::sync_with_stdio(false);
    n=rint(),m=rint();
    for(int i=1;i<=n;i++) spt[i]=rint();
    sgtbd(1,n,1);
    int flag=0;
    int cant;
    for(int i=1;i<=m;i++) {
        da[i].d=rint(),da[i].s=rint(),da[i].t=rint();
        sgtad(da[i].s,da[i].t,-da[i].d,1);
        if (sgtmi(da[i].s,da[i].t,1)<0) {flag=i;break;}
    }
    if (!flag) cout<<"0"<<endl;
    else cout<<"-1"<<endl<<flag<<endl;
    return 0;
    
}

0

williamking5 LV 8 @ 8 年前

两件事情：
1.被卡时限的首先优化读入。
2.结构体、类封装、位运算加速在这道题里面对于程序运行时间影响很小。

编译成功

测试数据 #0: Accepted, time = 46 ms, mem = 47528 KiB, score = 5
测试数据 #1: Accepted, time = 46 ms, mem = 47524 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 47524 KiB, score = 5
测试数据 #3: Accepted, time = 31 ms, mem = 47528 KiB, score = 5
测试数据 #4: Accepted, time = 31 ms, mem = 47524 KiB, score = 5
测试数据 #5: Accepted, time = 46 ms, mem = 47524 KiB, score = 5
测试数据 #6: Accepted, time = 93 ms, mem = 47528 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 47528 KiB, score = 5
测试数据 #8: Accepted, time = 62 ms, mem = 47528 KiB, score = 5
测试数据 #9: Accepted, time = 93 ms, mem = 47528 KiB, score = 5
测试数据 #10: Accepted, time = 93 ms, mem = 47524 KiB, score = 5
测试数据 #11: Accepted, time = 125 ms, mem = 47524 KiB, score = 5
测试数据 #12: Accepted, time = 125 ms, mem = 47524 KiB, score = 5
测试数据 #13: Accepted, time = 78 ms, mem = 47524 KiB, score = 5
测试数据 #14: Accepted, time = 437 ms, mem = 47528 KiB, score = 5
测试数据 #15: Accepted, time = 609 ms, mem = 47524 KiB, score = 5
测试数据 #16: Accepted, time = 734 ms, mem = 47524 KiB, score = 5
测试数据 #17: Accepted, time = 875 ms, mem = 47528 KiB, score = 5
测试数据 #18: Accepted, time = 1000 ms, mem = 47524 KiB, score = 5
测试数据 #19: Accepted, time = 1171 ms, mem = 47528 KiB, score = 5

#include<bits/stdc++.h>
using namespace std;
struct INTERVAL_DATA{
int left,right,Max,lazy;
INTERVAL_DATA(){
left=right=0;
lazy=0;
Max=0;
}
};
INTERVAL_DATA tree[3000000];
inline int read( )
{
int x=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
x=0;
while (ch<='9' && ch>='0')
{
x*=10,x+=ch-'0';
ch=getchar();
}
return x;
}
struct INTERVAL_TREE{
int nn;
INTERVAL_TREE(int height){
nn=height;

int h=0;
tree[0].left=0;tree[0].right=(1<<nn)-1;
for (int i=0;i<((1<<nn)-1);i++){
if (i>(2<<h)-2) h++;
tree[(i<<1)+1].left=tree[i].left;
tree[(i<<1)+2].left=(1<<(nn-h-1))|tree[i].left;
tree[(i<<1)+1].right=tree[(i<<1)+1].left+(1<<(nn-h-1))-1;
tree[(i<<1)+2].right=tree[(i<<1)+2].left+(1<<(nn-h-1))-1;
}
for (int i=0;i<(2<<nn)-1;i++){
tree[i].left++;
tree[i].right++;
}
}
void add(int root,int l,int r,int x){
if (l==tree[root].left&&r==tree[root].right) tree[root].lazy+=x;
else {
int mid=(tree[root].left+tree[root].right)>>1;
tree[(root<<1)+1].lazy+=tree[root].lazy;
tree[(root<<1)+2].lazy+=tree[root].lazy;
tree[root].lazy=0;

if (l>mid) add((root<<1)+2,l,r,x);
else if (r<=mid) add((root<<1)+1,l,r,x);
else {
add((root<<1)+1,l,mid,x);
add((root<<1)+2,mid+1,r,x);
}

tree[root].Max=max(tree[(root<<1)+1].lazy+tree[(root<<1)+1].Max,tree[(root<<1)+2].lazy+tree[(root<<1)+2].Max);
}
}
} a(20);
int main(){
int n,m,x,y,z;
n = read();
m = read();
for (int i=0;i<n;i++){
x = read();
a.add(0,i+1,i+1,-x);
}

for (int i=0;i<m;i++){
x=read();
y=read();
z=read();
a.add(0,y,z,x);
if (tree[0].Max>0) {
cout<<"-1"<<endl<<i+1<<endl;
return 0;
}
}

cout<<0<<endl;
return 0;
}

0

riteme LV 8 @ 9 年前

论普通线段树如何通过

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 48736 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 48740 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 48740 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 48732 KiB, score = 5
测试数据 #4: Accepted, time = 31 ms, mem = 48736 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 48736 KiB, score = 5
测试数据 #6: Accepted, time = 140 ms, mem = 48736 KiB, score = 5
测试数据 #7: Accepted, time = 140 ms, mem = 48740 KiB, score = 5
测试数据 #8: Accepted, time = 125 ms, mem = 48732 KiB, score = 5
测试数据 #9: Accepted, time = 140 ms, mem = 48732 KiB, score = 5
测试数据 #10: Accepted, time = 93 ms, mem = 48736 KiB, score = 5
测试数据 #11: Accepted, time = 101 ms, mem = 48732 KiB, score = 5
测试数据 #12: Accepted, time = 93 ms, mem = 48740 KiB, score = 5
测试数据 #13: Accepted, time = 101 ms, mem = 48732 KiB, score = 5
测试数据 #14: Accepted, time = 1671 ms, mem = 48740 KiB, score = 5
测试数据 #15: Accepted, time = 1296 ms, mem = 48736 KiB, score = 5
测试数据 #16: Accepted, time = 1250 ms, mem = 48736 KiB, score = 5
测试数据 #17: Accepted, time = 1125 ms, mem = 48732 KiB, score = 5
测试数据 #18: Accepted, time = 875 ms, mem = 48732 KiB, score = 5
测试数据 #19: Accepted, time = 843 ms, mem = 48736 KiB, score = 5
Accepted, time = 8115 ms, mem = 48740 KiB, score = 100

关键在于各种**奇技淫巧的优化**，我列出一些：
1. 正确的模拟方法 +30%
2. 堆式存储 +15%
3. 将所有除以2的运算变为位运算 +3%
4. 手动优化尾递归，vijos没有开优化 +5%
5. 循环使用迭代器写法 +5%
6. 读入优化 +3%
7. 大胆的使用int +2%
8. 使用结构体的默认构造函数 +1%
9. 线段树的插入和查询操作中对每条语句的必要性进行严格检查。删去没必要的语句 +2%

优化真是一件有趣的事......
实在过不了的可以到codevs上试试，codevs的机子好多了......

代码：
```c++
// 借教室

#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 1000000
#define MMAX 1000000
#define MEMORY_SIZE 2097151

#define LEFT(x) (x << 1)
#define RIGHT(x) ((x << 1) | 1)
#define PARENT(x) (x >> 1)

// #define FMT "%lld"
// typedef long long ntype;
#define FMT "%d"
typedef int ntype;

struct Reservation {
Reservation() : start(0), end(0), need(0) {}
Reservation(ntype s, ntype t, ntype d) : start(s), end(t), need(d) {}

ntype start;
ntype end;
ntype need;
}; // struct Reservation

struct Node {
Node() : pos(1), l(0), r(0), sum(0) {}
Node(ntype _l, ntype _r) : pos(1), l(_l), r(_r), sum(0) {}

ntype pos;
ntype l;
ntype r;
ntype sum;
};

static ntype n, m;
static ntype r[NMAX + 10];
static Reservation q[MMAX + 10];
static Node heap[MEMORY_SIZE];
static bool flag;
static ntype id;

Node *build_tree(ntype lb, ntype rb, ntype p = 1);
void insert(ntype s, ntype t, ntype value, ntype p = 1);
ntype query(ntype d, ntype p = 1);

inline ntype read() {
ntype x = 0;
char c = getchar();
while (c < '0' or c > '9') c = getchar();
while ('0' <= c and c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}

void initialize();
void quit();

int main() {
initialize();

for (Reservation *beg = &q[1]; beg != &q[n + 1]; beg++) {
insert(beg->start, beg->end, -beg->need, 1);
} // for

Reservation *j = &q[m + 1];
for (ntype i = 1; i <= n; i++) {
while (query(i, 1) < 0) {
j--;
insert(j->start, j->end, j->need, 1);
} // while
} // for

if (j != &q[m + 1]) {
flag = true;
id = j - &q[1] + 1;
}

quit();
return 0;
} // function main

void initialize() {
n = read();
m = read();

for (int *beg = &r[1]; beg != &r[n + 1]; beg++) *beg = read();
for (Reservation *beg = &q[1]; beg != &q[m + 1]; beg++)
beg->need = read(), beg->start = read(), beg->end = read();

flag = false;
id = 0;

build_tree(1, n);
}

void quit() {
if (!flag)
puts("0");
else {
puts("-1");
printf(FMT, id);
}
}

Node *build_tree(ntype lb, ntype rb, ntype p) {
Node *x = &heap[p];
x->l = lb;
x->r = rb;

if (lb != rb) {
ntype mid = (lb + rb) >> 1;
build_tree(lb, mid, LEFT(p));
build_tree(mid + 1, rb, RIGHT(p));
} else
x->sum = r[lb];

return x;
}

void insert(ntype s, ntype t, ntype value, ntype p) {
recursive:
Node *x = &heap[p];

if (s <= x->l and x->r <= t)
x->sum += value;
else {
ntype mid = (x->l + x->r) >> 1;

if (t <= mid) {
// insert(s, t, value, LEFT(p));
p = LEFT(p);
goto recursive;
} else if (s > mid) {
// insert(s, t, value, RIGHT(p));
p = RIGHT(p);
goto recursive;
} else {
insert(s, t, value, LEFT(p));
insert(s, t, value, RIGHT(p));
}
}
}

ntype query(ntype d, ntype p) {
ntype result = 0;

recursive:
Node *x = &heap[p];

if (d == x->l and d == x->r) return result + x->sum;

result += x->sum;
ntype mid = (x->l + x->r) >> 1;

if (d <= mid)
p = LEFT(p);
else
p = RIGHT(p);

goto recursive;
}

0

dfoimjh LV 8 @ 9 年前

你们也交交看，一样的程序有时AC有时TLE

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 317272 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 317268 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 317268 KiB, score = 5
测试数据 #8: Accepted, time = 46 ms, mem = 317272 KiB, score = 5
测试数据 #9: Accepted, time = 78 ms, mem = 317272 KiB, score = 5
测试数据 #10: Accepted, time = 78 ms, mem = 317268 KiB, score = 5
测试数据 #11: Accepted, time = 93 ms, mem = 317272 KiB, score = 5
测试数据 #12: Accepted, time = 140 ms, mem = 317272 KiB, score = 5
测试数据 #13: Accepted, time = 78 ms, mem = 317268 KiB, score = 5
测试数据 #14: Accepted, time = 437 ms, mem = 317272 KiB, score = 5
测试数据 #15: Accepted, time = 703 ms, mem = 317272 KiB, score = 5
测试数据 #16: Accepted, time = 937 ms, mem = 317272 KiB, score = 5
测试数据 #17: Accepted, time = 1218 ms, mem = 317272 KiB, score = 5
测试数据 #18: Accepted, time = 1500 ms, mem = 317272 KiB, score = 5
测试数据 #19: Accepted, time = 1625 ms, mem = 317272 KiB, score = 5
Accepted, time = 7010 ms, mem = 317272 KiB, score = 100
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[1000003],p,tot;
int d,s,t;
struct arr{
int w,c;
}tr[1000003*40];

int read(){
int f=1,x=0;
char s=getchar();
while(s<'0'||s>'9') s=getchar();
while(s>='0' && s<='9'){
x=x*10+(s-48);
s=getchar();
}
return f*x;
}

void push(int num){
tr[2*num].c+=tr[num].c;
tr[2*num+1].c+=tr[num].c;
tr[num].w-=tr[num].c;
tr[num].c=0;
}

void build(int num,int l,int r){
if (l==r){
tr[num].w=a[l];
return;
}
build(2*num,l,(l+r)/2);
build(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int find(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return 2147483647;
if (s<=l && r<=t) return tr[num].w;
return min(find(2*num,l,(l+r)/2),find(2*num+1,(l+r)/2+1,r));
}

void insert(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return;
if (s<=l && r<=t){
tr[num].w-=d;
tr[2*num].c+=d;
tr[2*num+1].c+=d;
return;
}
insert(2*num,l,(l+r)/2);
insert(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for (int i=1;i<=m;i++){
d=read();s=read();t=read();
if (tot) continue;
int dd=find(1,1,n);
if (dd<d) p=i,tot++;
else insert(1,1,n);
}
if (tot) printf("-1\n%d\n",p);
else printf("0\n");
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 317276 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 317276 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 317276 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 317276 KiB, score = 5
测试数据 #7: Accepted, time = 62 ms, mem = 317272 KiB, score = 5
测试数据 #8: Accepted, time = 78 ms, mem = 317272 KiB, score = 5
测试数据 #9: Accepted, time = 124 ms, mem = 317276 KiB, score = 5
测试数据 #10: Accepted, time = 124 ms, mem = 317272 KiB, score = 5
测试数据 #11: Accepted, time = 156 ms, mem = 317272 KiB, score = 5
测试数据 #12: Accepted, time = 187 ms, mem = 317276 KiB, score = 5
测试数据 #13: Accepted, time = 140 ms, mem = 317276 KiB, score = 5
测试数据 #14: Accepted, time = 873 ms, mem = 317272 KiB, score = 5
测试数据 #15: Accepted, time = 1341 ms, mem = 317272 KiB, score = 5
测试数据 #16: Accepted, time = 1700 ms, mem = 317276 KiB, score = 5
测试数据 #17: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
测试数据 #18: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
测试数据 #19: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
TimeLimitExceeded, time = 10867 ms, mem = 317276 KiB, score = 85
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[1000003],p,tot;
int d,s,t;
struct arr{
int w,c;
}tr[1000003*40];

int read(){
int f=1,x=0;
char s=getchar();
while(s<'0'||s>'9') s=getchar();
while(s>='0' && s<='9'){
x=x*10+(s-48);
s=getchar();
}
return f*x;
}

void push(int num){
tr[2*num].c+=tr[num].c;
tr[2*num+1].c+=tr[num].c;
tr[num].w-=tr[num].c;
tr[num].c=0;
}

void build(int num,int l,int r){
if (l==r){
tr[num].w=a[l];
return;
}
build(2*num,l,(l+r)/2);
build(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int find(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return 2147483647;
if (s<=l && r<=t) return tr[num].w;
return min(find(2*num,l,(l+r)/2),find(2*num+1,(l+r)/2+1,r));
}

void insert(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return;
if (s<=l && r<=t){
tr[num].w-=d;
tr[2*num].c+=d;
tr[2*num+1].c+=d;
return;
}
insert(2*num,l,(l+r)/2);
insert(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for (int i=1;i<=m;i++){
d=read();s=read();t=read();
if (tot) continue;
int dd=find(1,1,n);
if (dd<d) p=i,tot++;
else insert(1,1,n);
}
if (tot) printf("-1\n%d\n",p);
else printf("0\n");
return 0;
}

0

sxb_201 LV 10 @ 9 年前

线段树！！经典模板
http://www.ofsxb.com/archives/455

题解

53 条题解

状态耗时内存占用

论普通线段树如何通过

借教室

信息

状态

开发

支持

题解

53 条题解

状态 耗时 内存占用

论**普通线段树**如何通过

借教室

信息

状态

开发

支持

还没有账户？

登录

状态耗时内存占用

论普通线段树如何通过