oj.uz

Submission #91114

# Submission time Handle Problem Language Result Execution time Memory
91114 2018-12-26T09:50:17 Z popovicirobert Simple game (IZhO17_game) C++14
100 / 100
 66 ms 22880 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e6;

int h[MAXN + 1];
int aib[MAXN + 1];

inline void update(int pos, int val) {
    for(int i = pos; i <= MAXN; i += lsb(i)) {
        aib[i] += val;
    }
}

inline int query(int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= lsb(i)) {
        ans += aib[i];
    }
    return ans;
}

inline void solve(int l, int r, int val) {
    if(l > r) {
        swap(l, r);
    }
    update(l, val);
    update(r + 1, -val);
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for(i = 1; i < n; i++) {
        solve(h[i], h[i + 1], 1);
    }
    for(i = 1; i <= m; i++) {
        int type, pos, val, H;
        cin >> type;
        if(type == 1) {
            cin >> pos >> val;
            if(pos > 1) {
                solve(h[pos - 1], h[pos], -1);
                solve(h[pos - 1], val, 1);
            }
            if(pos < n) {
                solve(h[pos], h[pos + 1], -1);
                solve(val, h[pos + 1], 1);
            }
            h[pos] = val;
        }
        else {
            cin >> H;
            cout << query(H) << "\n";
        }
    }
    //cin.close();
    //cout.close();
    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 5 ms 4088 KB Output is correct
3 Correct 5 ms 4216 KB Output is correct
4 Correct 5 ms 4232 KB Output is correct
5 Correct 5 ms 4268 KB Output is correct
6 Correct 5 ms 4324 KB Output is correct
7 Correct 3 ms 4324 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 5 ms 4088 KB Output is correct
3 Correct 5 ms 4216 KB Output is correct
4 Correct 5 ms 4232 KB Output is correct
5 Correct 5 ms 4268 KB Output is correct
6 Correct 5 ms 4324 KB Output is correct
7 Correct 3 ms 4324 KB Output is correct
8 Correct 37 ms 4324 KB Output is correct
9 Correct 50 ms 8176 KB Output is correct
10 Correct 58 ms 9824 KB Output is correct
11 Correct 38 ms 9824 KB Output is correct
12 Correct 40 ms 9824 KB Output is correct
13 Correct 40 ms 9824 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 5 ms 4088 KB Output is correct
3 Correct 5 ms 4216 KB Output is correct
4 Correct 5 ms 4232 KB Output is correct
5 Correct 5 ms 4268 KB Output is correct
6 Correct 5 ms 4324 KB Output is correct
7 Correct 3 ms 4324 KB Output is correct
8 Correct 37 ms 4324 KB Output is correct
9 Correct 50 ms 8176 KB Output is correct
10 Correct 58 ms 9824 KB Output is correct
11 Correct 38 ms 9824 KB Output is correct
12 Correct 40 ms 9824 KB Output is correct
13 Correct 40 ms 9824 KB Output is correct
14 Correct 66 ms 15040 KB Output is correct
15 Correct 64 ms 16984 KB Output is correct
16 Correct 64 ms 18912 KB Output is correct
17 Correct 66 ms 20840 KB Output is correct
18 Correct 65 ms 22880 KB Output is correct