Advertisement
Guest User

Untitled

a guest
Jun 18th, 2016
285
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define vlong long long
  6. #define xx first
  7. #define yy second
  8. #define N 100005
  9. #define MOD 1000000007
  10. #define dbg(x) cout<<#x " = "<<(x)<<endl
  11. #define read freopen("in.txt","r",stdin)
  12.  
  13. //int dx[]={1,0,-1,0};                  int dy[]={0,1,0,-1};                // 4 Direction
  14. //int dx[]={1,1,0,-1,-1,-1,0,1};        int dy[]={0,1,1,1,0,-1,-1,-1};      // 8 direction
  15. //int dx[]={2,1,-1,-2,-2,-1,1,2};       int dy[]={1,2,2,1,-1,-2,-2,-1};     // Knight Direction
  16. //int dx[]={-1,-1,+0,+1,+1,+0};         int dy[]={-1,+1,+2,+1,-1,-2};       // Hexagonal Direction
  17.  
  18. int setBit(int n,int pos){return n|(1<<pos);}
  19. int resetBit(int n,int pos){return n&~(1<<pos);}
  20. bool checkBit(int n,int pos){return n&(1<<pos);}
  21. inline vlong bigmod(vlong p,vlong e,vlong M){vlong ret=1;while(e>0){if(e%2)ret=(ret*p)%M;p=(p*p)%M;e/=2;}return ret;}
  22. inline vlong power(vlong x,vlong y){vlong ans=1;while(y>0){if(y%2)ans*=x;x*=x;y/=2;}return ans;}
  23. template<class T> T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  24. template<class T> T lcm(T a,T b){return a*(b/gcd(a,b));}
  25.  
  26. int n,a[N],t[N*3];
  27.  
  28. void build(int num,int st,int ed){
  29.     if(st==ed){
  30.         t[num]=1;
  31.         return;
  32.     }
  33.     int mid=(st+ed)>>1;
  34.     build(num<<1,st,mid);
  35.     build(num<<1|1,mid+1,ed);
  36.     t[num]=t[num<<1]+t[num<<1|1];
  37. }
  38.  
  39. void update(int num,int st,int ed,int in,int v){
  40.     if(st==ed){
  41.         t[num]=v;
  42.         return;
  43.     }
  44.     int mid=(st+ed)>>1;
  45.     if(in<=t[num<<1]){
  46.         update(num<<1,st,mid,in,v);
  47.     }
  48.     else{
  49.         update(num<<1|1,mid+1,ed,in-t[num<<1],v);
  50.     }
  51.     t[num]=t[num<<1]+t[num<<1|1];
  52. }
  53.  
  54. int query(int num,int st,int ed,int in){
  55.     if(st==ed){
  56.         return st;
  57.     }
  58.     int mid=(st+ed)>>1;
  59.     if(in<=t[num<<1]){
  60.         return query(num<<1,st,mid,in);
  61.     }
  62.     else{
  63.         return query(num<<1|1,mid+1,ed,in-t[num<<1]);
  64.     }
  65. }
  66.  
  67. int main(){
  68.     // read;
  69.     int tc,tt=0;
  70.     cin>>tc;
  71.     while(tc--){
  72.         cin>>n;
  73.         memset(t,0,sizeof t);
  74.         for(int i=1;i<=n;i++){
  75.             scanf("%d",a+i);
  76.         }
  77.         build(1,1,n);
  78.         int nn=n;
  79.         for(int i=n;i>1;i--){
  80.             // dbg(nn-a[i]);
  81.             update(1,1,n,nn-a[i],0);
  82.             nn--;
  83.         }
  84.         printf("Case %d: %d\n",++tt,query(1,1,n,1));
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement