oj.uz

Submission #173081

# Submission time Handle Problem Language Result Execution time Memory
173081 2020-01-03T10:19:12 Z VEGAnn Simple game (IZhO17_game) C++14
100 / 100
 566 ms 15696 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 100100;
const int oo = 2e9;
ordered_set<pii> lf, rt;
int h[N], n, m;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> h[i];

    lf.clear();
    rt.clear();
    for (int i = 1; i < n; i++) {
        rt.insert(MP(max(h[i], h[i - 1]), i));
        lf.insert(MP(min(h[i], h[i - 1]), i));
    }

    for (; m; m--){
        int tp; cin >> tp;
        if (tp == 1){
            int ps, vl;
            cin >> ps >> vl;
            ps--;

            if (ps > 0){
                rt.erase(MP(max(h[ps], h[ps - 1]), ps));
                lf.erase(MP(min(h[ps], h[ps - 1]), ps));
            }
            if (ps < n - 1){
                rt.erase(MP(max(h[ps], h[ps + 1]), ps + 1));
                lf.erase(MP(min(h[ps], h[ps + 1]), ps + 1));
            }

            h[ps] = vl;

            if (ps > 0){
                rt.insert(MP(max(h[ps], h[ps - 1]), ps));
                lf.insert(MP(min(h[ps], h[ps - 1]), ps));
            }
            if (ps < n - 1){
                rt.insert(MP(max(h[ps], h[ps + 1]), ps + 1));
                lf.insert(MP(min(h[ps], h[ps + 1]), ps + 1));
            }

        } else {
            int vl; cin >> vl;
            int lef = rt.order_of_key(MP(vl, -oo));
            int rgt = n - 1 - lf.order_of_key(MP(vl, +oo));

            cout << n - 1 - lef - rgt << '\n';
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 508 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 167 ms 14200 KB Output is correct
9 Correct 288 ms 15544 KB Output is correct
10 Correct 295 ms 15552 KB Output is correct
11 Correct 157 ms 14132 KB Output is correct
12 Correct 255 ms 15312 KB Output is correct
13 Correct 256 ms 15472 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 508 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 167 ms 14200 KB Output is correct
9 Correct 288 ms 15544 KB Output is correct
10 Correct 295 ms 15552 KB Output is correct
11 Correct 157 ms 14132 KB Output is correct
12 Correct 255 ms 15312 KB Output is correct
13 Correct 256 ms 15472 KB Output is correct
14 Correct 566 ms 15696 KB Output is correct
15 Correct 550 ms 15588 KB Output is correct
16 Correct 552 ms 15344 KB Output is correct
17 Correct 557 ms 15480 KB Output is correct
18 Correct 546 ms 15624 KB Output is correct