oj.uz

Submission #881338

# Submission time Handle Problem Language Result Execution time Memory
881338 2023-12-01T07:02:51 Z _unknown_2010 Simple game (IZhO17_game) C++17
100 / 100
 245 ms 18260 KB 
//#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 6 ms 16792 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16732 KB Output is correct
7 Correct 5 ms 16732 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 6 ms 16792 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16732 KB Output is correct
7 Correct 5 ms 16732 KB Output is correct
8 Correct 147 ms 17672 KB Output is correct
9 Correct 186 ms 18120 KB Output is correct
10 Correct 186 ms 18260 KB Output is correct
11 Correct 147 ms 17672 KB Output is correct
12 Correct 163 ms 18168 KB Output is correct
13 Correct 168 ms 18008 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 6 ms 16792 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16732 KB Output is correct
7 Correct 5 ms 16732 KB Output is correct
8 Correct 147 ms 17672 KB Output is correct
9 Correct 186 ms 18120 KB Output is correct
10 Correct 186 ms 18260 KB Output is correct
11 Correct 147 ms 17672 KB Output is correct
12 Correct 163 ms 18168 KB Output is correct
13 Correct 168 ms 18008 KB Output is correct
14 Correct 245 ms 17900 KB Output is correct
15 Correct 182 ms 17752 KB Output is correct
16 Correct 188 ms 17748 KB Output is correct
17 Correct 199 ms 17744 KB Output is correct
18 Correct 191 ms 17744 KB Output is correct