oj.uz

Submission #331549

# Submission time Handle Problem Language Result Execution time Memory
331549 2020-11-28T21:59:33 Z jovan_b Simple game (IZhO17_game) C++17
100 / 100
 394 ms 9776 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int MAX = 1000000;

int h[MAX+5];

int seg[4*MAX+5];

void upd(int node, int l, int r, int tl, int tr, int val){
    if(l > tr || tl > r) return;
    if(tl <= l && r <= tr){
        seg[node] += val;
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
}

int query(int node, int l, int r, int x){
    if(l == r) return seg[node];
    int mid = (l+r)/2;
    if(x <= mid) return seg[node] + query(node*2, l, mid, x);
    return seg[node] + query(node*2+1, mid+1, r, x);
}

int main(){
    ios_base::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> h[i];
    }
    for(int i=2; i<=n; i++){
        upd(1, 1, MAX, min(h[i-1], h[i]), max(h[i-1], h[i]), 1);
    }
    while(m--){
        int t;
        cin >> t;
        if(t == 1){
            int i, y;
            cin >> i >> y;
            if(i > 1) upd(1, 1, MAX, min(h[i-1], h[i]), max(h[i-1], h[i]), -1);
            if(i < n) upd(1, 1, MAX, min(h[i+1], h[i]), max(h[i+1], h[i]), -1);
            h[i] = y;
            if(i > 1) upd(1, 1, MAX, min(h[i-1], h[i]), max(h[i-1], h[i]), 1);
            if(i < n) upd(1, 1, MAX, min(h[i+1], h[i]), max(h[i+1], h[i]), 1);
        }
        else{
            int y;
            cin >> y;
            cout << query(1, 1, MAX, y) << "\n";
        }
    }
    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 7 ms 6636 KB Output is correct
3 Correct 7 ms 6508 KB Output is correct
4 Correct 7 ms 6508 KB Output is correct
5 Correct 7 ms 6636 KB Output is correct
6 Correct 7 ms 6636 KB Output is correct
7 Correct 4 ms 412 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 7 ms 6636 KB Output is correct
3 Correct 7 ms 6508 KB Output is correct
4 Correct 7 ms 6508 KB Output is correct
5 Correct 7 ms 6636 KB Output is correct
6 Correct 7 ms 6636 KB Output is correct
7 Correct 4 ms 412 KB Output is correct
8 Correct 271 ms 1132 KB Output is correct
9 Correct 351 ms 9776 KB Output is correct
10 Correct 335 ms 9708 KB Output is correct
11 Correct 261 ms 1132 KB Output is correct
12 Correct 296 ms 1772 KB Output is correct
13 Correct 270 ms 1644 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 7 ms 6636 KB Output is correct
3 Correct 7 ms 6508 KB Output is correct
4 Correct 7 ms 6508 KB Output is correct
5 Correct 7 ms 6636 KB Output is correct
6 Correct 7 ms 6636 KB Output is correct
7 Correct 4 ms 412 KB Output is correct
8 Correct 271 ms 1132 KB Output is correct
9 Correct 351 ms 9776 KB Output is correct
10 Correct 335 ms 9708 KB Output is correct
11 Correct 261 ms 1132 KB Output is correct
12 Correct 296 ms 1772 KB Output is correct
13 Correct 270 ms 1644 KB Output is correct
14 Correct 347 ms 9452 KB Output is correct
15 Correct 325 ms 9372 KB Output is correct
16 Correct 326 ms 9452 KB Output is correct
17 Correct 394 ms 9324 KB Output is correct
18 Correct 329 ms 9324 KB Output is correct