fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=100000+10;
  27. int T;
  28.  
  29. int n,m;
  30. int t[MAX],person[MAX],sum[MAX];
  31.  
  32. int l[MAX],r[MAX],Del[MAX],Add[MAX],num[MAX],fugai[MAX];
  33. int next[MAX];
  34.  
  35. int check(int T)
  36. {
  37.     int i;
  38.     REP(i,1,n)
  39.     {
  40.         l[i]=m+1;
  41.         r[i]=0;
  42.     }
  43.     REP(i,1,m)
  44.         num[i]=-1;
  45.     REP(i,1,T)
  46.     {
  47.         if(num[t[i]]!=-1 && num[t[i]]!=sum[i]+1)
  48.             return 0;
  49.         num[t[i]]=sum[i]+1;
  50.  
  51.         int u=person[i];
  52.         if(l[u]>t[i])
  53.             l[u]=t[i];
  54.         if(r[u]<t[i])
  55.             r[u]=t[i];
  56.     }
  57.  
  58.     int be=-1;
  59.     for(i=m;i>=1;--i)
  60.         if(num[i]!=-1)
  61.         {
  62.             next[i]=be;
  63.             be=i;
  64.             Add[i]=Del[i]=0;
  65.             fugai[i]=0;
  66.         }
  67.  
  68.     int have=0;
  69.     REP(i,1,n)
  70.     {
  71.         if(r[i]==0)
  72.             continue;
  73.         ++have;
  74.         int L=l[i];
  75.         int R=r[i];
  76.         fugai[L]+=1;
  77.         if(L!=be)
  78.             Del[L]++;
  79.  
  80.         if(next[R]!=-1)
  81.         {
  82.             fugai[next[R]]--;
  83.             Add[next[R]]++;
  84.         }
  85.     }
  86.  
  87.     int last=0,lasta=0,ans=0;
  88.     int ss=0;
  89.     REP(i,1,m)
  90.     {
  91.         if(num[i]==-1)
  92.             continue;
  93.         ss+=fugai[i];
  94.         int x=Del[i];
  95.         int y=Add[i];
  96.         ans-=x+y;
  97.         int now=num[i]-ss;
  98.         if(now<0)
  99.             return 0;
  100.  
  101.         int tmp=min(x,last);
  102.         x-=tmp;
  103.         last-=tmp;
  104.         if(x>0)
  105.             ans+=x;
  106.  
  107.         lasta+=y;
  108.         int diff=last+lasta-now;
  109.         ans+=abs(diff);
  110.         if(diff>0)
  111.         {
  112.             int tmp=min(diff,lasta);
  113.             lasta-=tmp;
  114.             diff-=tmp;
  115.             last-=diff;
  116.         }
  117.         else
  118.             last+=-diff;
  119.     }
  120.     ans+=last+lasta;
  121.     return ans/2<=n-have;
  122. }
  123.  
  124. int Test;
  125.  
  126. int Main()
  127. {
  128.     int i;
  129.     scanf("%d%d",&n,&m);
  130.     REP(i,1,m)
  131.         scanf("%d%d%d",&t[i],&person[i],&sum[i]);
  132.     int left=1,right=m;
  133. //    if(Test!=1)
  134. //        return 0;
  135. //    printf("%d %d\n",n,m);
  136. //    REP(i,1,m)
  137. //        printf("%d %d %d\n",t[i],person[i],sum[i]);
  138.     while(left<right)
  139.     {
  140.         int mid=(left+right+1)/2;
  141.         if(check(mid))
  142.             left=mid;
  143.         else right=mid-1;
  144.     }
  145.     printf("%d\n",left);
  146.     return 0;
  147. }
  148.  
  149. int main()
  150. {
  151. #ifndef ONLINE_JUDGE
  152. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  153. #endif
  154.     scanf("%d",&T);
  155.     REP(Test,1,T)
  156.         Main();
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0s 7248KB
comments (?)
stdin
copy 
2
3 5
1 1 1
1 2 1
2 3 1
4 1 1
4 2 1
3 3
3 3 0
2 2 0
1 1 0
stdout
copy 
4
3
https://ideone.com/NC1Dje
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!