oj.uz

Submission #334012

# Submission time Handle Problem Language Result Execution time Memory
334012 2020-12-08T06:05:04 Z BY_KUTBILIM Simple game (IZhO17_game) C++14
100 / 100
 608 ms 19496 KB 
/** @BY_KUTBILIM **/
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long

const int N = (int)1e6 + 7;
int tree[N * 4], add[N * 4];

void push(int v, int l, int r){
    if(add[v] != 0){
        tree[v] +=  (r - l + 1) * add[v];
        if(l != r){
            add[v*2] += add[v];
            add[v*2+1] += add[v];
        }
        add[v] = 0;
    }
}

int get(int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if(l > qr || r < ql)return 0;
    if(ql <= l and r <= qr)return tree[v];
    int m = (l + r) / 2;
    return get(v*2, l, m, ql, qr) + get(v*2+1, m+1, r, ql, qr);
}

void update(int v, int l, int r, int ql, int qr, int val){
    push(v, l, r);
    if(l > qr || r < ql)return ;
    if(ql <= l and r <= qr){
        tree[v] += (r - l + 1) * val;
        if(l != r){
            add[v*2] += val;
            add[v*2+1] += val;
        }
        return ;
    }
    int m = (l + r) / 2;
    update(v*2, l, m, ql, qr, val);
    update(v*2+1, m+1, r, ql, qr, val);
    tree[v] = tree[v*2] + tree[v*2+1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();

    int n, q;
    cin >> n >> q;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n - 1; i++){
        update(1, 1, N, min(a[i], a[i+1]), max(a[i], a[i+1]), 1);
    }
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int i, x;
            cin >> i >> x;
            i--;
            if(i > 0){
                update(1, 1, N, min(a[i], a[i-1]), max(a[i], a[i-1]), -1);
            }
            if(i < n - 1){
                update(1, 1, N, min(a[i], a[i+1]), max(a[i], a[i+1]), -1);
            }
            a[i] = x;
            if(i > 0){
                update(1, 1, N, min(a[i], a[i-1]), max(a[i], a[i-1]), 1);
            }
            if(i < n - 1){
                update(1, 1, N, min(a[i], a[i+1]), max(a[i], a[i+1]), 1);
            }
        } else{
            int h;
            cin >> h;
            cout << get(1, 1, N, h, h) << endl;
        }
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 15084 KB Output is correct
3 Correct 14 ms 14848 KB Output is correct
4 Correct 14 ms 15100 KB Output is correct
5 Correct 15 ms 15104 KB Output is correct
6 Correct 14 ms 15104 KB Output is correct
7 Correct 11 ms 12908 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 15084 KB Output is correct
3 Correct 14 ms 14848 KB Output is correct
4 Correct 14 ms 15100 KB Output is correct
5 Correct 15 ms 15104 KB Output is correct
6 Correct 14 ms 15104 KB Output is correct
7 Correct 11 ms 12908 KB Output is correct
8 Correct 303 ms 1900 KB Output is correct
9 Correct 456 ms 19436 KB Output is correct
10 Correct 466 ms 19496 KB Output is correct
11 Correct 291 ms 1644 KB Output is correct
12 Correct 365 ms 3436 KB Output is correct
13 Correct 364 ms 19180 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 15084 KB Output is correct
3 Correct 14 ms 14848 KB Output is correct
4 Correct 14 ms 15100 KB Output is correct
5 Correct 15 ms 15104 KB Output is correct
6 Correct 14 ms 15104 KB Output is correct
7 Correct 11 ms 12908 KB Output is correct
8 Correct 303 ms 1900 KB Output is correct
9 Correct 456 ms 19436 KB Output is correct
10 Correct 466 ms 19496 KB Output is correct
11 Correct 291 ms 1644 KB Output is correct
12 Correct 365 ms 3436 KB Output is correct
13 Correct 364 ms 19180 KB Output is correct
14 Correct 596 ms 19180 KB Output is correct
15 Correct 603 ms 19188 KB Output is correct
16 Correct 591 ms 19308 KB Output is correct
17 Correct 608 ms 19180 KB Output is correct
18 Correct 595 ms 19180 KB Output is correct