Submission #339969

# Submission time Handle Problem Language Result Execution time Memory
339969 2020-12-26T13:01:52 Z scales Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
478 ms 62444 KB
#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
int kol,w;
int prav[20000000],lev[20000000],sum[20000000];
short z[20000000];
void zam(int x, int y,int m,int l,int r)
{
   // cout<<"x="<<x<<" y="<<y<<" l="<<l<<" r="<<r<<" m="<<m<<endl;
   if(prav[m]==0)
   {
       prav[m]=w;
       w++;
       z[w]=0;
       sum[w]=0;
   }
   if(lev[m]==0)
   {
       lev[m]=w;
       w++;
       z[w]=0;
       sum[w]=0;
   }


    if(z[m]!=0)
    {
        sum[m]=r-l+1;
        z[m]=0;
        z[lev[m]]=1;
        z[prav[m]]=1;
    }


    if(x<=l && y>=r)
    {
        //cout<<" obrab"<<endl;
        z[m]=1;
        sum[m]=r-l+1;
    }
    else
    {
        if(x>r || y<l)
        {
            return;
        }
        else
        {
            zam(x,y,lev[m],l,(l+r)/2);
            zam(x,y,prav[m],(l+r)/2+1,r);
            sum[m]=sum[prav[m]]+sum[lev[m]];
        }
    }
}



void viv(int x, int y,int m,int l,int r)
{
    //cout<<"x="<<x<<" y="<<y<<" l="<<l<<" r="<<r<<" kol="<<kol<<endl;
    if(prav[m]==0)
   {
       prav[m]=w;
       w++;
       z[w]=0;
       sum[w]=0;
   }
   if(lev[m]==0)
   {
       lev[m]=w;
       w++;
       z[w]=0;
       sum[w]=0;
   }
    if(z[m]!=0)
    {
        //cout<<"aaaaaaa"<<endl;
        sum[m]=r-l+1;
        z[m]=0;
        z[lev[m]]=1;
        z[prav[m]]=1;

    }
    if(x<=l && y>=r)
    {
        kol=kol+sum[m];
        //cout<<"sum[m]="<<sum[m]<<endl;
    }
    else
    {
        if(x>r || y<l)
        {

        }
        else
        {
            viv(x,y,lev[m],l,(l+r)/2);
            viv(x,y,prav[m],(l+r)/2+1,r);
            sum[m]=sum[prav[m]]+sum[lev[m]];
        }
    }
}
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
     cin>>m;
     vector<int> st(31);
     st[0]=1;
     for(i=1;i<=30;i++)
     {
         st[i]=st[i-1]*2;
     }
     kol=0;
     for(i=0;i<m;i++)
     {
         cin>>tip;
         cin>>x;
         cin>>y;
         x=x+kol;
         y=y+kol;
         x--;
         y--;
         l=0;
         r=st[30]-1;
         if(tip==2)
         {
            zam(x,y,0,l,r);
         }
         else
         {
                //cout<<"kol="<<kol<<endl;
             kol=0;
            viv(x,y,0,l,r);
            cout<<kol<<endl;
         }
     }
    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:114:10: warning: unused variable 't' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |          ^
apple.cpp:114:14: warning: unused variable 'j' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |              ^
apple.cpp:114:16: warning: unused variable 'dno' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                ^~~
apple.cpp:114:20: warning: unused variable 'mini' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                    ^~~~
apple.cpp:114:29: warning: unused variable 'q' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                             ^
apple.cpp:114:33: warning: unused variable 'k' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                 ^
apple.cpp:114:35: warning: unused variable 'v' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                   ^
apple.cpp:114:37: warning: unused variable 'n' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                     ^
apple.cpp:114:39: warning: unused variable 'x1' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                       ^~
apple.cpp:114:46: warning: unused variable 'g' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                              ^
apple.cpp:114:48: warning: unused variable 'maxi' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                                ^~~~
apple.cpp:114:53: warning: unused variable 'p' [-Wunused-variable]
  114 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                                     ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 28 ms 2964 KB Output is correct
5 Correct 32 ms 3436 KB Output is correct
6 Correct 32 ms 3436 KB Output is correct
7 Correct 30 ms 3564 KB Output is correct
8 Correct 218 ms 24684 KB Output is correct
9 Correct 462 ms 44160 KB Output is correct
10 Correct 465 ms 47240 KB Output is correct
11 Correct 472 ms 50924 KB Output is correct
12 Correct 478 ms 52548 KB Output is correct
13 Correct 419 ms 61892 KB Output is correct
14 Incorrect 423 ms 62444 KB Output isn't correct
15 Halted 0 ms 0 KB -