oj.uz

Submission #331548

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

typedef long long ll;
typedef long double ld;

const int MAX = 1000000;

int h[MAX+5];

struct segment{
    int val, lazy;
} seg[4*MAX+5];

void propagate(int node, int l, int r){
    seg[node].val += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}

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].lazy += 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){
    propagate(node, l, r);
    if(l == r) return seg[node].val;
    int mid = (l+r)/2;
    if(x <= mid) return query(node*2, l, mid, x);
    return 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;
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 11628 KB Output is correct
3 Correct 10 ms 11244 KB Output is correct
4 Correct 10 ms 11500 KB Output is correct
5 Correct 10 ms 11500 KB Output is correct
6 Correct 10 ms 11628 KB Output is correct
7 Correct 8 ms 9708 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 10 ms 11628 KB Output is correct
3 Correct 10 ms 11244 KB Output is correct
4 Correct 10 ms 11500 KB Output is correct
5 Correct 10 ms 11500 KB Output is correct
6 Correct 10 ms 11628 KB Output is correct
7 Correct 8 ms 9708 KB Output is correct
8 Correct 282 ms 1900 KB Output is correct
9 Correct 349 ms 19436 KB Output is correct
10 Correct 348 ms 19564 KB Output is correct
11 Correct 271 ms 1644 KB Output is correct
12 Correct 303 ms 3436 KB Output is correct
13 Correct 304 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 10 ms 11628 KB Output is correct
3 Correct 10 ms 11244 KB Output is correct
4 Correct 10 ms 11500 KB Output is correct
5 Correct 10 ms 11500 KB Output is correct
6 Correct 10 ms 11628 KB Output is correct
7 Correct 8 ms 9708 KB Output is correct
8 Correct 282 ms 1900 KB Output is correct
9 Correct 349 ms 19436 KB Output is correct
10 Correct 348 ms 19564 KB Output is correct
11 Correct 271 ms 1644 KB Output is correct
12 Correct 303 ms 3436 KB Output is correct
13 Correct 304 ms 19180 KB Output is correct
14 Correct 348 ms 19540 KB Output is correct
15 Correct 349 ms 19436 KB Output is correct
16 Correct 342 ms 19572 KB Output is correct
17 Correct 341 ms 19572 KB Output is correct
18 Correct 346 ms 19692 KB Output is correct