Submission #881338

#	Time	Username	Problem	Language	Result	Execution time	Memory
881338		_unknown_2010	Simple game (IZhO17_game)	C++17	100 / 100	245 ms	18260 KiB

game

//#ifndef LOCAL
    //#pragma GCC optimize ("Ofast")
    //#pragma GCC optimize ("unroll-loops")
    //#endif
     
    #include <bits/stdc++.h>
    using namespace std;
    using vecp = vector<pair<int,int>>;
    #define vecm(a,n,m) vector<vector<int>>a(n,vector<int>(m,0));
    #define int int64_t
    #define pb  push_back
    #define pii pair<int,int>
    #define vi vector<int>
    #define vii vector<pii>
    #define mpii map<int,int>
    #define lb lower_bound
    #define ub upper_bound
    #define foor(i,a,b) for(int i=a;i<b; i++)
    #define foor(i,a) foor(i,0,a)
    #define ins insert
    #define ss second
    #define ff first
    #define until(x, a) for (auto x : a)
    #define ln(x) int(x.size())
    #define all(x) (x).begin(), (x).end()
    #define seea(a,n) for(int i=0;i<n;i++){cin>>a[i];}
    #define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
    const int mod = 1E9+7;
    struct segtree{
        vi tree;
        int sz;
        void init(int n){
            sz=1;
            while(sz<n)sz*=2;
            tree.assign(2*sz-1,0);
        }
        void update(int i,int v,int x,int lx,int rx){
            if(rx-lx==1){
                tree[x]+=v;
                return;
            }
            int m=(lx+rx)/2;
            if(i<m)update(i,v,2*x+1,lx,m);
            else update(i,v,2*x+2,m,rx);
            tree[x]=tree[2*x+1]+tree[2*x+2];
        }
        void update(int i,int v){
            return update(i,v,0,0,sz);
        }
        int sum(int l,int r,int x,int lx,int rx){
            if(rx<=l || r<=lx)return 0;
            if(l<=lx && rx<=r)return tree[x];
            int m=(lx+rx)/2;
            int s1=sum(l,r,2*x+1,lx,m);
            int s2=sum(l,r,2*x+2,m,rx);
            return s1+s2;
        }
        int sum(int l,int r){
            return sum(l,r,0,0,sz);
        }
    };
    void solution(){
        int n,m;
        cin >> n >> m;
        int a[n];
        segtree st;
        int maks=0;
        for(int i=0; i<n; i++){
            cin >> a[i];
            maks=max(a[i],maks);
        }
        st.init(1e6+5);
        for(int i=1; i<n; i++){
            int mn=min(a[i],a[i-1]);
            int mx=max(a[i],a[i-1]);
            st.update(mn-1,1);
            st.update(mx,-1);
        }
        while(m--){
            int op;
            cin >> op;
            if(op==2){
                int k;
                cin >> k;
                cout << st.sum(0,k) << endl;
            }
            else {
                int i,v;
                cin >> i >> v;
                if(i==1){
                    //oraliqlarni o'chirish
                    int mn=min(a[i],a[i-1]);
                    int mx=max(a[i],a[i-1]);
                    st.update(mn-1,-1);
                        st.update(mx,1);
                    //oraliqqa newHeight ni qoshish
                    a[i-1]=v;
                    mn=min(a[i],a[i-1]);
                    mx=max(a[i],a[i-1]);
                    st.update(mn-1,1);
                        st.update(mx,-1);
                }
                else if(i==n){
                    int mn=min(a[i-2],a[i-1]);
                    int mx=max(a[i-2],a[i-1]);
                    st.update(mn-1,-1);
                        st.update(mx,1);
                    a[i-1]=v;
                    mn=min(a[i-1],a[i-2]);
                    mx=max(a[i-1],a[i-2]);
                    st.update(mn-1,1);
                        st.update(mx,-1);
               }
               else {
                    int mn=min(a[i],a[i-1]);
                    int mx=max(a[i],a[i-1]);
                    st.update(mn-1,-1);
                        st.update(mx,1);
                    mn=min(a[i-1],a[i-2]);
                    mx=max(a[i-1],a[i-2]);
                    st.update(mn-1,-1);
                        st.update(mx,1);
                    a[i-1]=v;
                    mn=min(a[i],a[i-1]);
                    mx=max(a[i],a[i-1]);
                    st.update(mn-1,1);
                        st.update(mx,-1);
                    mn=min(a[i-2],a[i-1]);
                    mx=max(a[i-2],a[i-1]);
                    st.update(mn-1,1);
                        st.update(mx,-1);
               }
               }
        }
    }
    int32_t main(){
        clock_t tStart = clock();
        std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int q = 1; // cin >> q;
        while(q--) {
            solution();
            cout << '\n';
        }
        cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
    }
    /*
     
    ██╗  ██╗ █████╗  ██████╗     ██╗██╗   ██╗ ██████╗████████╗
    ██║░░██║██╔══██╗██╔════╝░░░░░██║██║░░░██║██╔════╝╚══██╔══╝
    ███████║██║░░██║╚█████╗░░░░░░██║██║░░░██║╚█████╗░░░░██║░░░
    ██╔══██║██║░░██║░╚═══██╗██╗░░██║██║░░░██║░╚═══██╗░░░██║░░░
    ██║░░██║╚█████╔╝██████╔╝╚█████╔╝╚██████╔╝██████╔╝░░░██║░░░
    ╚═╝░░╚═╝░╚════╝░╚═════╝░░╚════╝░░╚═════╝░╚═════╝░░░░╚═╝░░░
    */

Compilation message (stderr)

game.cpp:19: warning: "foor" redefined
   19 |     #define foor(i,a) foor(i,0,a)
      | 
game.cpp:18: note: this is the location of the previous definition
   18 |     #define foor(i,a,b) for(int i=a;i<b; i++)
      |

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