oj.uz

Submission #526026

# Submission time Handle Problem Language Result Execution time Memory
526026 2022-02-13T14:26:52 Z spike1236 Simple game (IZhO17_game) C++14
100 / 100
 52 ms 6848 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 1e6 + 10;
int n, m;
int t[MAXN];
int h[MAXN];
void upd(int r, int val) {
    for(; r <= 1e6; r += r & -r) t[r] += val;
}

int get(int r) {
    int res = 0;
    for(; r > 0; r -= r & -r) res += t[r];
    return res;
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> h[i];
        if(i > 1) upd(min(h[i], h[i - 1]), 1), upd(max(h[i], h[i - 1]) + 1, -1);
    }
    for(int i = 1; i <= m; ++i) {
        int t, x;
        cin >> t >> x;
        if(t == 1) {
            int v;
            cin >> v;
            if(x > 1) {
                upd(min(h[x], h[x - 1]), -1);
                upd(max(h[x], h[x - 1]) + 1, 1);
            }
            if(x < n) {
                upd(min(h[x], h[x + 1]), -1);
                upd(max(h[x], h[x + 1]) + 1, 1);
            }
            h[x] = v;
            if(x > 1) {
                upd(min(h[x], h[x - 1]), 1);
                upd(max(h[x], h[x - 1]) + 1, -1);
            }
            if(x < n) {
                upd(min(h[x], h[x + 1]), 1);
                upd(max(h[x], h[x + 1]) + 1, -1);
            }
        } else cout << get(x) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int CNT_TESTS = 1;
    ///cin >> CNT_TESTS;
    for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
        solve();
        if(NUMCASE != CNT_TESTS) cout << '\n';
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 3 ms 3792 KB Output is correct
3 Correct 2 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 2 ms 3652 KB Output is correct
6 Correct 2 ms 3916 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 3 ms 3792 KB Output is correct
3 Correct 2 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 2 ms 3652 KB Output is correct
6 Correct 2 ms 3916 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 30 ms 1728 KB Output is correct
9 Correct 38 ms 6848 KB Output is correct
10 Correct 41 ms 6808 KB Output is correct
11 Correct 29 ms 1604 KB Output is correct
12 Correct 35 ms 2840 KB Output is correct
13 Correct 36 ms 2740 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 3 ms 3792 KB Output is correct
3 Correct 2 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 2 ms 3652 KB Output is correct
6 Correct 2 ms 3916 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 30 ms 1728 KB Output is correct
9 Correct 38 ms 6848 KB Output is correct
10 Correct 41 ms 6808 KB Output is correct
11 Correct 29 ms 1604 KB Output is correct
12 Correct 35 ms 2840 KB Output is correct
13 Correct 36 ms 2740 KB Output is correct
14 Correct 51 ms 6792 KB Output is correct
15 Correct 52 ms 6780 KB Output is correct
16 Correct 50 ms 6724 KB Output is correct
17 Correct 52 ms 6724 KB Output is correct
18 Correct 52 ms 6776 KB Output is correct