Submission #344318

#	Time	Username	Problem	Language	Result	Execution time	Memory
344318		scales	Simple game (IZhO17_game)	C++17	100 / 100	442 ms	27836 KiB

game

#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;
long long M=1000000007,raz,ot;
struct der
{
    long long i;
    vector<long long> ver;
    void sozd(long long n)
    {
        raz=1;
        while(raz<n)
        {
            raz=raz*2;
        }
        raz=raz*2-1;
        for(i=0;i<raz;i++)
        {
            ver.push_back(0);
        }
    }
    void zam(long long x, long long y,long long z,long long m ,long long l, long long r)
    {
        if(x>r || y<l)
        {

        }
        else
        {
            if(x<=l && r<=y)
            {
                ver[m]=ver[m]+z;
            }
            else
            {
                zam(x,y,z,2*m+1,l,(l+r)/2);
                zam(x,y,z,2*m+2,(l+r)/2+1,r);
            }
        }
    }
    void viv(long long x, long long m, long long l, long long r)
    {
        if(x<l || x>r)
        {

        }
        else
        {
           if(l!=r)
           {
               viv(x,2*m+1,l,(l+r)/2);
               viv(x,2*m+2,(l+r)/2+1,r);
           }
           ot=ot+ver[m];
        }
    }
};
long long b[1000000];
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
    long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    for(i=0;i<=1000000;i++)
    {
        b[i]=0;
    }
    der h;
    h.sozd(1000000);
    cin>>n;
    cin>>t;
    vector<long long> a(n);
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    b[a[0]]++;
    for(i=1;i<n;i++)
    {
        l=min(a[i],a[i-1]);
        r=max(a[i],a[i-1]);
        if(a[i-1]<=a[i])
        {
            l++;
        }
        else
        {
            r--;
        }
        if(l<=r)
        {
            h.zam(l,r,1,0,0,(raz-1)/2);
        }
    }
    for(q=0;q<t;q++)
    {
        cin>>tip;
        if(tip==2)
        {
            cin>>x;
            ot=0;
            h.viv(x,0,0,(raz-1)/2);
            cout<<b[x]+ot<<endl;
        }
        else
        {
            cin>>x;
            cin>>y;
            x--;
            if(x==0)
            {
                b[a[0]]--;
                b[y]++;
            }
            else
            {
                i=x;
                l=min(a[i],a[i-1]);
                r=max(a[i],a[i-1]);
                if(a[i-1]<=a[i])
                {
                    l++;
                }
                else
                {
                    r--;
                }
                if(l<=r)
                {
                    h.zam(l,r,-1,0,0,(raz-1)/2);
                }


                l=min(a[i-1],y);
                r=max(a[i-1],y);
                if(a[i-1]<=y)
                {
                    l++;
                }
                else
                {
                    r--;
                }
                if(l<=r)
                {
                    h.zam(l,r,1,0,0,(raz-1)/2);
                }
            }
            //cout<<"aaaaaaaaaaaaaaa"<<endl;
            if(x!=n-1)
            {
                i=x+1;
                l=min(a[i],a[i-1]);
                r=max(a[i],a[i-1]);
                if(a[i-1]<=a[i])
                {
                    l++;
                }
                else
                {
                    r--;
                }
                if(l<=r)
                {
                    h.zam(l,r,-1,0,0,(raz-1)/2);
                }


                l=min(a[i],y);
                r=max(a[i],y);
                if(y<=a[i])
                {
                    l++;
                }
                else
                {
                    r--;
                }
                if(l<=r)
                {
                    h.zam(l,r,1,0,0,(raz-1)/2);
                }
            }
            a[x]=y;

        }
    }



    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:68:19: warning: unused variable 'j' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                   ^
game.cpp:68:23: warning: unused variable 'z' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                       ^
game.cpp:68:25: warning: unused variable 'm' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                         ^
game.cpp:68:27: warning: unused variable 'x1' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                           ^~
game.cpp:68:30: warning: unused variable 'y1' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                              ^~
game.cpp:68:33: warning: unused variable 'sum' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                                 ^~~
game.cpp:68:41: warning: unused variable 'f' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                                         ^
game.cpp:68:53: warning: unused variable 'k' [-Wunused-variable]
   68 |     long long t,i,j,y,z,m,x1,y1,sum,n,x,f,q,l,r,tip,k;
      |                                                     ^
game.cpp:73:13: warning: iteration 1000000 invokes undefined behavior [-Waggressive-loop-optimizations]
   73 |         b[i]=0;
      |         ~~~~^~
game.cpp:71:14: note: within this loop
   71 |     for(i=0;i<=1000000;i++)
      |             ~^~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51