oj.uz

Submission #93286

# Submission time Handle Problem Language Result Execution time Memory
93286 2019-01-07T12:11:01 Z toloraia Simple game (IZhO17_game) C++14
100 / 100
 513 ms 18896 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 4e6 + 5, M = (1<<20);

int T[N];
int sh[N];

void update (int k, int l, int r, int L, int R, int x){
    if (r < L || R < l)
        return;
    if (L <= l && r <= R){
        T[k] += (r - l + 1) * x;
        sh[k] += x;
        return;
    }
    update (k * 2,     l,               (l + r) / 2, l,               (l + r) / 2, sh[k]);
    update (k * 2 + 1, (l + r) / 2 + 1, r,           (l + r) / 2 + 1,  r,          sh[k]);
    update (k * 2,     l,               (l + r) / 2, L, R, x);
    update (k * 2 + 1, (l + r) / 2 + 1, r,           L, R, x);
    sh[k] = 0;
    T[k] = T[k * 2] + T[k * 2 + 1];
}

int calc (int k, int l, int r, int x){
    if (r < x || x < l)
        return 0;
    if (l == r)
        return T[k];
    update (k * 2,     l,               (l + r) / 2, l,               (l + r) / 2, sh[k]);
    update (k * 2 + 1, (l + r) / 2 + 1, r,           (l + r) / 2 + 1,  r,          sh[k]);
    sh[k] = 0;
    T[k] = T[k * 2] + T[k * 2 + 1];
    return calc (k * 2,     l,               (l + r) / 2, x) +
           calc (k * 2 + 1, (l + r) / 2 + 1, r,           x);
}

int n, m;
int a[N];


int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    for (int i = 1; i < n; i++){
        int x = min (a[i], a[i + 1]);
        int y = max (a[i], a[i + 1]);
        update (1, 1, M, x, y, 1);
    }
    while (m--){
        int t;
        cin>>t;
        if (t == 1){
            int l, x;
            cin>>l>>x;
            if (l > 1){
                update (1, 1, M, min (a[l], a[l - 1]), max (a[l], a[l - 1]), -1);
                update (1, 1, M, min (x, a[l - 1]), max (x, a[l - 1]), 1);
            }
            if (l < n){
                update (1, 1, M, min (a[l], a[l + 1]), max (a[l], a[l + 1]), -1);
                update (1, 1, M, min (x, a[l + 1]), max (x, a[l + 1]), 1);
            }
            a[l] = x;
            continue;
        }
        int x;
        cin>>x;
        cout<<calc (1, 1, M, x)<<endl;
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 19 ms 14456 KB Output is correct
3 Correct 20 ms 14072 KB Output is correct
4 Correct 19 ms 14456 KB Output is correct
5 Correct 19 ms 14328 KB Output is correct
6 Correct 17 ms 14456 KB Output is correct
7 Correct 15 ms 12536 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 19 ms 14456 KB Output is correct
3 Correct 20 ms 14072 KB Output is correct
4 Correct 19 ms 14456 KB Output is correct
5 Correct 19 ms 14328 KB Output is correct
6 Correct 17 ms 14456 KB Output is correct
7 Correct 15 ms 12536 KB Output is correct
8 Correct 220 ms 1840 KB Output is correct
9 Correct 353 ms 18680 KB Output is correct
10 Correct 360 ms 18680 KB Output is correct
11 Correct 218 ms 1912 KB Output is correct
12 Correct 259 ms 3340 KB Output is correct
13 Correct 287 ms 18552 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 19 ms 14456 KB Output is correct
3 Correct 20 ms 14072 KB Output is correct
4 Correct 19 ms 14456 KB Output is correct
5 Correct 19 ms 14328 KB Output is correct
6 Correct 17 ms 14456 KB Output is correct
7 Correct 15 ms 12536 KB Output is correct
8 Correct 220 ms 1840 KB Output is correct
9 Correct 353 ms 18680 KB Output is correct
10 Correct 360 ms 18680 KB Output is correct
11 Correct 218 ms 1912 KB Output is correct
12 Correct 259 ms 3340 KB Output is correct
13 Correct 287 ms 18552 KB Output is correct
14 Correct 501 ms 18816 KB Output is correct
15 Correct 507 ms 18680 KB Output is correct
16 Correct 509 ms 18896 KB Output is correct
17 Correct 513 ms 18824 KB Output is correct
18 Correct 502 ms 18808 KB Output is correct