oj.uz

Submission #877161

# Submission time Handle Problem Language Result Execution time Memory
877161 2023-11-23T00:46:47 Z __Davit__ Simple game (IZhO17_game) C++17
100 / 100
 250 ms 11344 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define Davit cout.tie(NULL);
const int MAXH = 1000000;
using namespace std;

//#include "algo/debug.h"
vector<int> seg;
int sz = 1;


int get(int l, int r, int x, int index) {
    if (l == r) {
        return seg[x];
    }
    int m = (l + r) >> 1;
    if (index <= m) {
        return seg[x] + get(l, m, x + x + 1, index);
    } else {
        return seg[x] + get(m + 1, r, x + x + 2, index);
    }
}

int get(int index) {
    return get(0, sz - 1, 0, index);
}

void add(int lx, int rx, int x, int l, int r, int val) {
    if (lx > r || rx < l)return;
    if (l <= lx && rx <= r) {
        seg[x] += val;
        return;
    }
    int m = (lx + rx) >> 1;
    add(lx, m, x + x + 1, l, r, val);
    add(m + 1, rx, x + x + 2, l, r, val);
}

void add(int l, int r, int val) {
    add(0, sz - 1, 0, l, r, val);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    while (sz < MAXH) {
        sz <<= 1;
    }
    seg.resize(sz + sz, 0);
    for (int i = 1; i < n; i++) {
        add(min(v[i - 1], v[i]), max(v[i - 1], v[i]), 1);
    }
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;
            if (pos) {
                add(min(v[pos - 1], v[pos]), max(v[pos - 1], v[pos]), -1);
            }
            if (pos < n - 1) {
                add(min(v[pos + 1], v[pos]), max(v[pos + 1], v[pos]), -1);
            }
            v[pos] = val;
            if (pos) {
                add(min(v[pos - 1], v[pos]), max(v[pos - 1], v[pos]), 1);
            }
            if (pos < n - 1) {
                add(min(v[pos + 1], v[pos]), max(v[pos + 1], v[pos]), 1);
            }

        } else {
            int H;
            cin >> H;
            cout << get(H) << endl;
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 171 ms 10228 KB Output is correct
9 Correct 222 ms 11088 KB Output is correct
10 Correct 250 ms 11216 KB Output is correct
11 Correct 167 ms 9860 KB Output is correct
12 Correct 197 ms 10836 KB Output is correct
13 Correct 199 ms 10944 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8540 KB Output is correct
8 Correct 171 ms 10228 KB Output is correct
9 Correct 222 ms 11088 KB Output is correct
10 Correct 250 ms 11216 KB Output is correct
11 Correct 167 ms 9860 KB Output is correct
12 Correct 197 ms 10836 KB Output is correct
13 Correct 199 ms 10944 KB Output is correct
14 Correct 236 ms 11208 KB Output is correct
15 Correct 225 ms 11344 KB Output is correct
16 Correct 217 ms 11108 KB Output is correct
17 Correct 226 ms 11140 KB Output is correct
18 Correct 215 ms 11088 KB Output is correct