oj.uz

Submission #173212

# Submission time Handle Problem Language Result Execution time Memory
173212 2020-01-03T15:15:01 Z achibasadzishvili Simple game (IZhO17_game) C++14
100 / 100
 383 ms 11128 KB 
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,pown = 1,a[500006],m,typ,t[5000005],r,l,ad;
void upd(ll x,ll L,ll R){
    if(L > r || R < l)return;
    if(L >= l && R <= r){
        t[x] += ad;
        return;
    }
    t[2 * x] += t[x];
    t[2 * x + 1] += t[x];
    t[x] = 0;
    upd(2 * x,L,(L+R)/2);
    upd(2 * x + 1,(L+R)/2+1,R);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    while(pown <= 1000005)
        pown *= 2;
    
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    for(int i=2; i<=n; i++){
        l = min(a[i - 1] , a[i]);
        r = max(a[i - 1] , a[i]);
        ad = 1;
        upd(1 , 1 , pown);
    }
    
    while(m--){
        cin >> typ;
        if(typ == 1){
            int x,y;
            cin >> x >> y;
            if(x > 1){
                l = min(a[x - 1] , a[x]);
                r = max(a[x - 1] , a[x]);
                ad = -1;
                upd(1 , 1 , pown);
            }
            if(x < n){
                l = min(a[x + 1] , a[x]);
                r = max(a[x + 1] , a[x]);
                ad = -1;
                upd(1 , 1 , pown);
            }
            a[x] = y;
            if(x > 1){
                l = min(a[x - 1] , a[x]);
                r = max(a[x - 1] , a[x]);
                ad = 1;
                upd(1 , 1 , pown);
            }
            if(x < n){
                l = min(a[x + 1] , a[x]);
                r = max(a[x + 1] , a[x]);
                ad = 1;
                upd(1 , 1 , pown);
            }
        }
        else {
            int x;
            cin >> x;
            ll ans = 0;
            x = pown + x - 1;
            while(x){
                ans += t[x];
                x /= 2;
            }
            cout << ans << '\n';
        }
    }
    
    
    
    
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 6908 KB Output is correct
3 Correct 10 ms 6520 KB Output is correct
4 Correct 11 ms 6776 KB Output is correct
5 Correct 10 ms 6648 KB Output is correct
6 Correct 11 ms 6904 KB Output is correct
7 Correct 7 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 6908 KB Output is correct
3 Correct 10 ms 6520 KB Output is correct
4 Correct 11 ms 6776 KB Output is correct
5 Correct 10 ms 6648 KB Output is correct
6 Correct 11 ms 6904 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 313 ms 1820 KB Output is correct
9 Correct 383 ms 11000 KB Output is correct
10 Correct 383 ms 10908 KB Output is correct
11 Correct 309 ms 1756 KB Output is correct
12 Correct 343 ms 3152 KB Output is correct
13 Correct 317 ms 2916 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 6908 KB Output is correct
3 Correct 10 ms 6520 KB Output is correct
4 Correct 11 ms 6776 KB Output is correct
5 Correct 10 ms 6648 KB Output is correct
6 Correct 11 ms 6904 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 313 ms 1820 KB Output is correct
9 Correct 383 ms 11000 KB Output is correct
10 Correct 383 ms 10908 KB Output is correct
11 Correct 309 ms 1756 KB Output is correct
12 Correct 343 ms 3152 KB Output is correct
13 Correct 317 ms 2916 KB Output is correct
14 Correct 363 ms 10944 KB Output is correct
15 Correct 372 ms 11128 KB Output is correct
16 Correct 361 ms 10872 KB Output is correct
17 Correct 362 ms 10896 KB Output is correct
18 Correct 365 ms 10872 KB Output is correct