oj.uz

Submission #344318

# Submission time Handle Problem Language Result Execution time Memory
344318 2021-01-05T13:20:35 Z scales Simple game (IZhO17_game) C++17
100 / 100
 442 ms 27836 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;
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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24792 KB Output is correct
2 Correct 30 ms 24792 KB Output is correct
3 Correct 30 ms 24792 KB Output is correct
4 Correct 30 ms 24792 KB Output is correct
5 Correct 29 ms 24848 KB Output is correct
6 Correct 33 ms 24808 KB Output is correct
7 Correct 28 ms 24792 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24792 KB Output is correct
2 Correct 30 ms 24792 KB Output is correct
3 Correct 30 ms 24792 KB Output is correct
4 Correct 30 ms 24792 KB Output is correct
5 Correct 29 ms 24848 KB Output is correct
6 Correct 33 ms 24808 KB Output is correct
7 Correct 28 ms 24792 KB Output is correct
8 Correct 295 ms 26428 KB Output is correct
9 Correct 393 ms 27708 KB Output is correct
10 Correct 395 ms 27580 KB Output is correct
11 Correct 284 ms 26428 KB Output is correct
12 Correct 354 ms 27452 KB Output is correct
13 Correct 371 ms 27612 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24792 KB Output is correct
2 Correct 30 ms 24792 KB Output is correct
3 Correct 30 ms 24792 KB Output is correct
4 Correct 30 ms 24792 KB Output is correct
5 Correct 29 ms 24848 KB Output is correct
6 Correct 33 ms 24808 KB Output is correct
7 Correct 28 ms 24792 KB Output is correct
8 Correct 295 ms 26428 KB Output is correct
9 Correct 393 ms 27708 KB Output is correct
10 Correct 395 ms 27580 KB Output is correct
11 Correct 284 ms 26428 KB Output is correct
12 Correct 354 ms 27452 KB Output is correct
13 Correct 371 ms 27612 KB Output is correct
14 Correct 417 ms 27836 KB Output is correct
15 Correct 417 ms 27836 KB Output is correct
16 Correct 423 ms 27580 KB Output is correct
17 Correct 442 ms 27580 KB Output is correct
18 Correct 412 ms 27708 KB Output is correct