oj.uz

Submission #780791

# Submission time Handle Problem Language Result Execution time Memory
780791 2023-07-12T13:13:27 Z PoPularPlusPlus Simple game (IZhO17_game) C++17
100 / 100
 371 ms 19344 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1000002;

struct Seg{
    
    int siz;
    vector<int> v,lazy;
    
    void init(int n){
        siz = 1;
        while(siz < n)siz *= 2;
        
        v.assign(siz * 2 , 0);
        lazy.assign(siz*2,0);
    }
    
    void set(int l , int r , int val, int x , int lx , int rx){
        if(l >= rx || r <= lx)return;
        if(lx >= l && rx <= r){
            v[x] += val*(rx-lx);
            lazy[x]+=val;
            return;
        }
        lazy[2 * x + 1] += lazy[x];
        lazy[2 * x + 2] += lazy[x];
        int m = (lx + rx)/2;
        v[2*x+1]+=lazy[x]*(m-lx);
        v[2*x+2]+=lazy[x]*(rx-m);
        lazy[x] = 0;
        set(l,r,val,2*x+1,lx,m);
        set(l,r,val,2*x+2,m,rx);
        v[x]=v[2*x+1] + v[2*x+2];
    }
    
    void set(int l, int r , int val){
        set(l,r,val,0,0,siz);
    }
    
    int sum(int pos , int x, int lx , int rx){
        if(rx-lx==1)return v[x];
        lazy[2 * x + 1] += lazy[x];
        lazy[2 * x + 2] += lazy[x];
        int m = (lx + rx)/2;
        v[2*x+1]+=lazy[x]*(m-lx);
        v[2*x+2]+=lazy[x]*(rx-m);
        lazy[x] = 0;
        return (pos < m ? sum(pos,2*x+1,lx,m):sum(pos,2*x+2,m,rx));
    }
    
    int sum(int pos){
        return sum(pos,0,0,siz);
    }
};

void solve(){
    int n , m;
    cin >> n >> m;
    Seg st;
    st.init(N);
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        if(i){
            st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,1);
        }
    }
    while(m--){
        int t;
        cin >> t;
        if(t==1){
            int i , val;
            cin >> i >> val;
            i--;
            if(i){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,-1);
            }
            i++;
            if(i < n){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,-1);
            }
            i--;
            arr[i] = val;
            if(i){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,1);
            }
            i++;
            if(i < n){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,1);
            }
        }
        else {
            int pos;
            cin>>pos;
            cout << st.sum(pos) << '\n';
        }
    }
}

int main() {
	// your code goes here
//	int t;
//	cin >> t;
//	while(t--){
	    solve();
//	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 11 ms 16724 KB Output is correct
3 Correct 11 ms 16764 KB Output is correct
4 Correct 12 ms 16696 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 12 ms 16764 KB Output is correct
7 Correct 10 ms 16700 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 11 ms 16724 KB Output is correct
3 Correct 11 ms 16764 KB Output is correct
4 Correct 12 ms 16696 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 12 ms 16764 KB Output is correct
7 Correct 10 ms 16700 KB Output is correct
8 Correct 193 ms 18084 KB Output is correct
9 Correct 281 ms 19308 KB Output is correct
10 Correct 266 ms 19276 KB Output is correct
11 Correct 195 ms 17972 KB Output is correct
12 Correct 216 ms 18984 KB Output is correct
13 Correct 241 ms 19148 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 11 ms 16724 KB Output is correct
3 Correct 11 ms 16764 KB Output is correct
4 Correct 12 ms 16696 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 12 ms 16764 KB Output is correct
7 Correct 10 ms 16700 KB Output is correct
8 Correct 193 ms 18084 KB Output is correct
9 Correct 281 ms 19308 KB Output is correct
10 Correct 266 ms 19276 KB Output is correct
11 Correct 195 ms 17972 KB Output is correct
12 Correct 216 ms 18984 KB Output is correct
13 Correct 241 ms 19148 KB Output is correct
14 Correct 350 ms 19316 KB Output is correct
15 Correct 371 ms 19344 KB Output is correct
16 Correct 368 ms 19280 KB Output is correct
17 Correct 350 ms 19228 KB Output is correct
18 Correct 350 ms 19320 KB Output is correct