oj.uz

Submission #339971

# Submission time Handle Problem Language Result Execution time Memory
339971 2020-12-26T13:05:38 Z scales Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 599 ms 117636 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;
     w=1;
     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:115:10: warning: unused variable 't' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |          ^
apple.cpp:115:14: warning: unused variable 'j' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |              ^
apple.cpp:115:16: warning: unused variable 'dno' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                ^~~
apple.cpp:115:20: warning: unused variable 'mini' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                    ^~~~
apple.cpp:115:29: warning: unused variable 'q' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                             ^
apple.cpp:115:33: warning: unused variable 'k' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                 ^
apple.cpp:115:35: warning: unused variable 'v' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                   ^
apple.cpp:115:37: warning: unused variable 'n' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                     ^
apple.cpp:115:39: warning: unused variable 'x1' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                       ^~
apple.cpp:115:46: warning: unused variable 'g' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                              ^
apple.cpp:115:48: warning: unused variable 'maxi' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                                ^~~~
apple.cpp:115:53: warning: unused variable 'p' [-Wunused-variable]
  115 |      int t,i,j,dno,mini,x,y,q,m,k,v,n,x1,tip,g,maxi,p,l,r;
      |                                                     ^

Subtask #1
100.0 / 100.0

# 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 25 ms 2924 KB Output is correct
5 Correct 30 ms 3436 KB Output is correct
6 Correct 30 ms 3436 KB Output is correct
7 Correct 32 ms 3564 KB Output is correct
8 Correct 218 ms 24812 KB Output is correct
9 Correct 454 ms 44140 KB Output is correct
10 Correct 459 ms 47212 KB Output is correct
11 Correct 480 ms 51052 KB Output is correct
12 Correct 478 ms 52460 KB Output is correct
13 Correct 420 ms 61932 KB Output is correct
14 Correct 445 ms 62444 KB Output is correct
15 Correct 579 ms 115052 KB Output is correct
16 Correct 598 ms 115052 KB Output is correct
17 Correct 424 ms 65004 KB Output is correct
18 Correct 433 ms 65004 KB Output is correct
19 Correct 599 ms 117576 KB Output is correct
20 Correct 590 ms 117636 KB Output is correct