题解

51 条题解

  • 7
    @ 2017-07-15 17:13:21

    线段树碰线过。。

     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
    @ 2017-10-30 07:48:09

    坑点:
    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
    @ 2017-11-23 17:20:08

    一道较为基础的线段树题目。
    大体的思路是每输入一组数据,用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
    @ 2018-08-22 20:33:27

    二分答案
    知识准备:使用前缀数组处理数组区间标记,单点查询。
    定义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
    @ 2017-10-27 17:00:06

    二分答案
    跑的飞起

    #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
    @ 2017-08-11 21:21:57

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

    #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

    比线段树要快

    • @ 2017-08-11 21:23:08

      其实我一开始也是想的线段树,但是我本地测的貌似有卡线段树的数据,需要优化

    • @ 2017-10-25 11:32:21

      全部加register啊!
      为啥用咸鱼读优不写iobuff或者mmap?

    • @ 2017-10-25 11:32:21

      全部加register啊!
      为啥用咸鱼读优不写iobuff或者mmap?

    • @ 2017-10-27 21:34:58

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

    • @ 2017-10-27 21:35:09

      @call_me_std: %%%谢谢dalao

  • 1
    @ 2015-11-02 17:42:42

    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
    @ 2019-02-15 09:17:08

    每个测试点不止1秒?

  • 0
    @ 2018-02-11 11:09:07

    差分+二分答案

    #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
    @ 2017-10-24 23:01:24

    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
    @ 2017-10-17 20:10:38

    二分:

    #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
    @ 2017-08-13 16:35:37

    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);
        }
    }
    
  • 0
    @ 2017-08-05 15:56:03

    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
    @ 2017-07-17 11:30:57

    一击!!!

    #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
    @ 2016-05-03 19:47:21

    两件事情:
    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
    @ 2015-12-15 13:06:52

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

    编译成功
    
    测试数据 #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
    @ 2015-11-22 16:00:53

    你们也交交看,一样的程序有时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
    @ 2015-10-22 15:41:44

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

  • 0
    @ 2015-10-07 21:53:14

    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    #define N 1000010
    struct Node{
    int flag;
    int Min;
    }t[N*4];
    int n,m;
    int A[N];
    bool pd=true;
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    void Pushup(int i)
    {
    t[i].Min=min(t[i*2].Min,t[i*2+1].Min);
    }
    void BuildTree(int i,int l,int r)
    {
    if(l==r)
    {
    t[i].Min=A[l];
    return;
    }
    int mid=(l+r)/2;
    BuildTree(i*2,l,mid);
    BuildTree(i*2+1,mid+1,r);
    Pushup(i);
    }
    void Pushdown(int i)
    {
    if(t[i].flag==0)
    return;
    t[i*2].Min+=t[i].flag;
    t[i*2+1].Min+=t[i].flag;
    t[i*2].flag+=t[i].flag;
    t[i*2+1].flag+=t[i].flag;
    t[i].flag=0;
    return;
    }
    void Updata(int i,int l,int r,int left,int right,int c)
    {
    if(l>=left&&r<=right)
    {
    t[i].Min-=c;
    t[i].flag-=c;
    if(t[i].Min<0)
    pd=false;
    return;
    }
    Pushdown(i);
    int mid=(l+r)/2;
    if(right<=mid)
    Updata(i*2,l,mid,left,right,c);
    else if(left>mid)
    Updata(i*2+1,mid+1,r,left,right,c);
    else
    {
    Updata(i*2,l,mid,left,mid,c);
    Updata(i*2+1,mid+1,r,mid+1,right,c);
    }
    Pushup(i);
    }
    int main()
    {
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
    A[i]=read();
    }
    BuildTree(1,1,n);
    bool haha=false;
    for(int i=1;i<=m;i++)
    {
    int x=read(),y=read(),z=read();
    if(haha)
    continue;
    Updata(1,1,n,y,z,x);
    if(!pd)
    {
    haha=true;
    cout<<"-1"<<endl;
    cout<<i<<endl;
    }
    }
    if(pd)
    cout<<"0"<<endl;
    return 0;
    }

  • 0
    @ 2015-10-05 20:55:32
    #include <bits/stdc++.h>
    
    const int MAXN = 1000000 + 5;
    using namespace std;
    struct classroom {
        int need;
        int start;
        int end;
    
    } crm[MAXN];
    
    int prs[MAXN];
    int r[MAXN];
    int n, m, sum, ans = 0;
    
    int in() {
        int x = 0, f = 1, c = getchar();
        while (!isdigit(c)) {
            if (c == '-')f = -1;
            c = getchar();
        }
        while (isdigit(c)) {
            x = x * 10 + c - '0';
            c = getchar();
        }
        return x * f;
    }
    
    
    bool judge(int mid) {
    
        memset(prs, 0, sizeof(prs));
    
        for (int i = 1; i <= mid; ++i) {
            prs[crm[i].start] += crm[i].need;
            prs[crm[i].end + 1] -= crm[i].need;
        }
    
        sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += prs[i];
            if (sum > r[i]) {
                return false;
            }
        }
        return true;
    }
    
    int main() {
        n = in();
        m = in();
        for (int i = 1; i <= n; ++i) {
            r[i] = in();
        }
        for (int i = 1; i <= m; ++i) {
            crm[i].need = in();
            crm[i].start = in();
            crm[i].end = in();
        }
        int front = 1, back = m;
    
        while (front <= back) {
            int mid = (front + back) / 2;
            if (judge(mid)) {
                front = mid + 1;
            } else {
                ans = mid;
                back = mid - 1;
            }
        }
    
        if (ans == 0) {
            printf("0");
        } else {
            printf("-1\n%d", ans);
        }
        return 0;
    }
    

信息

ID
1782
难度
8
分类
模拟 | 其他 | 二分查找数据结构 | 线段树 点击显示
标签
递交数
8184
已通过
1221
通过率
15%
被复制
10
上传者