oj.uz

Submission #881336

# Submission time Handle Problem Language Result Execution time Memory
881336 2023-12-01T06:59:28 Z The_Samurai Simple game (IZhO17_game) C++17
100 / 100
 205 ms 19820 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 3 ms 16728 KB Output is correct
2 Correct 6 ms 16732 KB Output is correct
3 Correct 5 ms 16804 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 8 ms 16732 KB Output is correct
6 Correct 6 ms 16708 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 3 ms 16728 KB Output is correct
2 Correct 6 ms 16732 KB Output is correct
3 Correct 5 ms 16804 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 8 ms 16732 KB Output is correct
6 Correct 6 ms 16708 KB Output is correct
7 Correct 5 ms 16732 KB Output is correct
8 Correct 147 ms 18516 KB Output is correct
9 Correct 185 ms 19792 KB Output is correct
10 Correct 183 ms 19796 KB Output is correct
11 Correct 148 ms 18512 KB Output is correct
12 Correct 164 ms 19536 KB Output is correct
13 Correct 163 ms 19540 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 6 ms 16732 KB Output is correct
3 Correct 5 ms 16804 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 8 ms 16732 KB Output is correct
6 Correct 6 ms 16708 KB Output is correct
7 Correct 5 ms 16732 KB Output is correct
8 Correct 147 ms 18516 KB Output is correct
9 Correct 185 ms 19792 KB Output is correct
10 Correct 183 ms 19796 KB Output is correct
11 Correct 148 ms 18512 KB Output is correct
12 Correct 164 ms 19536 KB Output is correct
13 Correct 163 ms 19540 KB Output is correct
14 Correct 205 ms 19792 KB Output is correct
15 Correct 202 ms 19624 KB Output is correct
16 Correct 192 ms 19800 KB Output is correct
17 Correct 191 ms 19820 KB Output is correct
18 Correct 187 ms 19796 KB Output is correct