oj.uz

Submission #549249

# Submission time Handle Problem Language Result Execution time Memory
549249 2022-04-15T12:48:41 Z Vladth11 Simple game (IZhO17_game) C++14
100 / 100
 70 ms 6816 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 1000002;
const ll VMAX = 26;
const ll INF = (1LL << 55);
const ll MOD = 90000000000000001;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

int aib[NMAX];

void update(int node, int x) {
    for(; node < NMAX; node += node&(-node))
        aib[node] += x;
}

int query(int node) {
    int x = 0;
    for(; node > 0; node -= node&(-node))
        x += aib[node];
    return x;
}

int v[NMAX];

void baga(int a, int b, int c){
    if(a > b) swap(a, b);
    update(a, c);
    update(b + 1, -c);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i, m;
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        cin >> v[i];
        if(i > 1)
        baga(v[i], v[i - 1], 1);
    }
    for(i = 1; i <= m; i++) {
        int c;
        int l, r;
        cin >> c >> l;
        if(c == 2) {
            cout << query(l) << "\n";
        } else {
            cin >> r;
            if(l < n)
                baga(v[l], v[l + 1], -1);
            if(l > 1)
                baga(v[l - 1], v[l], -1);
            v[l] = r;
            if(l < n)
                baga(v[l], v[l + 1], 1);
            if(l > 1)
                baga(v[l - 1], v[l], 1);

        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 2 ms 3792 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 2 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 2 ms 3792 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 36 ms 1716 KB Output is correct
9 Correct 46 ms 6804 KB Output is correct
10 Correct 50 ms 6748 KB Output is correct
11 Correct 31 ms 1632 KB Output is correct
12 Correct 38 ms 2840 KB Output is correct
13 Correct 37 ms 2760 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 2 ms 3792 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 36 ms 1716 KB Output is correct
9 Correct 46 ms 6804 KB Output is correct
10 Correct 50 ms 6748 KB Output is correct
11 Correct 31 ms 1632 KB Output is correct
12 Correct 38 ms 2840 KB Output is correct
13 Correct 37 ms 2760 KB Output is correct
14 Correct 51 ms 6756 KB Output is correct
15 Correct 50 ms 6808 KB Output is correct
16 Correct 49 ms 6732 KB Output is correct
17 Correct 70 ms 6816 KB Output is correct
18 Correct 60 ms 6800 KB Output is correct