oj.uz

Submission #570812

# Submission time Handle Problem Language Result Execution time Memory
570812 2022-05-31T10:20:47 Z knightron0 Simple game (IZhO17_game) C++14
100 / 100
 419 ms 43468 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e6 + 5;
const int MX = 1e6;

int tree[4*MAXN], a[MAXN], lazy[4*MAXN];

void push(int v, int l, int r){
    int m = (l+r)/2;
    lazy[2*v] += lazy[v];
    lazy[2*v + 1] += lazy[v];
    tree[2*v] += lazy[v]*(m-l+1);
    tree[(2*v)+1] += lazy[v] * (r-(m+1)+1);
    lazy[v] = 0;
}

int query(int curr, int start, int end, int l, int r){
    if(r < start or end < l) return 0;
    if(l <= start and end <= r) return tree[curr];
    push(curr, start, end);
    int mid = (start+end)/2;
    int p1 = query(2*curr, start, mid, l, r);
    int p2 = query(2*curr +1, mid+1, end, l, r);
    return p1+ p2;
}

void build(int curr, int start, int end){
    lazy[curr]= 0;
    if(start == end) {
        tree[curr] = a[start];
    } else {
        int mid = (start+end)/2;
        build(2*curr, start, mid);
        build(2*curr+1, mid+1, end);
        tree[curr] = tree[2*curr] +  tree[2*curr+1];
    }
}

void update(int curr, int start, int end, int lx, int rx, int v){
    if(start > rx || end < lx) return;
    if(lx <= start && end <= rx){
        tree[curr] += v*(end-start+1);
        lazy[curr] += v;
        return;
    }
    push(curr, start, end);
    int mid = (start+end)/2;
    update(curr*2, start, mid, lx, rx, v);
    update(curr*2+1, mid+1, end, lx, rx, v);
    tree[curr] = tree[2*curr] + tree[2*curr+1];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int n, k;
    cin>>n>>k;
    clr(a, 0);
    int b[n+3];
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    build(1, 1, MX+2);
    for(int i=2;i<=n;i++){
        update(1, 1, MX+2, min(b[i], b[i-1]), max(b[i], b[i-1]), 1);
    }
    while(k--){
        int t1;
        cin>>t1;
        if(t1 == 1){
            int idx, x;
            cin>>idx>>x;
            if(idx > 1){
                update(1, 1, MX+2, min(b[idx], b[idx-1]), max(b[idx], b[idx-1]), -1);
                update(1, 1, MX+2, min(x, b[idx-1]), max(x, b[idx-1]), 1);
            }
            if(idx < n){
                update(1, 1, MX+2, min(b[idx], b[idx+1]), max(b[idx], b[idx+1]), -1);
                update(1, 1, MX+2, min(x, b[idx+1]), max(x, b[idx+1]), 1);   
            }
            b[idx] = x;
        } else {
            int x;
            cin>>x;
            cout<<query(1, 1, MX+2, x, x)<<endl;
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41036 KB Output is correct
2 Correct 30 ms 40888 KB Output is correct
3 Correct 29 ms 40896 KB Output is correct
4 Correct 24 ms 40964 KB Output is correct
5 Correct 26 ms 40920 KB Output is correct
6 Correct 25 ms 40976 KB Output is correct
7 Correct 27 ms 40916 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41036 KB Output is correct
2 Correct 30 ms 40888 KB Output is correct
3 Correct 29 ms 40896 KB Output is correct
4 Correct 24 ms 40964 KB Output is correct
5 Correct 26 ms 40920 KB Output is correct
6 Correct 25 ms 40976 KB Output is correct
7 Correct 27 ms 40916 KB Output is correct
8 Correct 90 ms 42636 KB Output is correct
9 Correct 184 ms 43316 KB Output is correct
10 Correct 176 ms 43336 KB Output is correct
11 Correct 80 ms 42616 KB Output is correct
12 Correct 125 ms 43468 KB Output is correct
13 Correct 132 ms 43348 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41036 KB Output is correct
2 Correct 30 ms 40888 KB Output is correct
3 Correct 29 ms 40896 KB Output is correct
4 Correct 24 ms 40964 KB Output is correct
5 Correct 26 ms 40920 KB Output is correct
6 Correct 25 ms 40976 KB Output is correct
7 Correct 27 ms 40916 KB Output is correct
8 Correct 90 ms 42636 KB Output is correct
9 Correct 184 ms 43316 KB Output is correct
10 Correct 176 ms 43336 KB Output is correct
11 Correct 80 ms 42616 KB Output is correct
12 Correct 125 ms 43468 KB Output is correct
13 Correct 132 ms 43348 KB Output is correct
14 Correct 328 ms 43056 KB Output is correct
15 Correct 379 ms 42976 KB Output is correct
16 Correct 382 ms 43016 KB Output is correct
17 Correct 419 ms 43084 KB Output is correct
18 Correct 393 ms 43140 KB Output is correct