oj.uz

Submission #340634

# Submission time Handle Problem Language Result Execution time Memory
340634 2020-12-28T04:06:32 Z IZhO_2021_I_want_Silver Simple game (IZhO17_game) C++14
100 / 100
 603 ms 19632 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>-

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define show(a) cerr << #a <<" -> "<< a <<" "
#define nl cerr <<"\n"
//#define int ll

const int N = (1 << 20) - 1;
const int MX = 1e6 + 1;

int n, m, t[N*3], add[N*3], a[N];

void push(int v, int tl, int tr) {
    if (add[v]) {
        t[v] += (tr - tl + 1) * add[v];
        if (tl < tr) {
            add[v*2] += add[v];
            add[v*2+1] += add[v];
        }
        add[v] = 0;
    }
}

void upd(int l, int r, int x, int v=1, int tl=1, int tr=MX) {
    push(v, tl, tr);
    if (r < tl || tr < l) { return; }
    if (l <= tl && tr <= r) {
        add[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    upd(l, r, x, v*2, tl, tm);
    upd(l, r, x, v*2+1, tm+1, tr);
    t[v] = t[v*2] + t[v*2+1];
}

int get(int pos, int v=1, int tl=1, int tr=MX) {
    push(v, tl, tr);
    if (tl == tr) { return t[v]; }
    int tm = (tl + tr) / 2;
    if (pos <= tm) { return get(pos, v*2, tl, tm); }
    else { return get(pos, v*2+1, tm+1, tr); }
    return -1; assert(0);
}

void add_or_del(int l, int r, int ch) {
    if (l > r) { swap(l, r); }
    ++l, --r;
    if (l > r) { return; }
    //show(l); show(r); show(ch); nl;
    upd(l, r, ch);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        upd(a[i], a[i], 1);
        if (1 < i) { add_or_del(a[i-1], a[i], +1); }
    }
    for (int i = 1; i <= m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;

            upd(a[pos], a[pos], -1);
            if (1 < pos) { add_or_del(a[pos-1], a[pos], -1); }
            if (pos < n) { add_or_del(a[pos], a[pos+1], -1); }

            a[pos] = val;

            upd(a[pos], a[pos], +1);
            if (1 < pos) { add_or_del(a[pos-1], a[pos], +1); }
            if (pos < n) { add_or_del(a[pos], a[pos+1], +1); }
        }
        else {
            int h;
            cin >> h;
            cout << get(h) <<"\n";
        }
    }
}

 main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tests = 1;
	//cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Just Chalish!
3 3
1 5 1
2 3
1 1 5
2 3
*/

Compilation message

game.cpp:117:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 |  main () {
      |        ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 14 ms 15616 KB Output is correct
3 Correct 14 ms 15212 KB Output is correct
4 Correct 14 ms 15596 KB Output is correct
5 Correct 14 ms 15488 KB Output is correct
6 Correct 14 ms 15596 KB Output is correct
7 Correct 9 ms 12780 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 14 ms 15616 KB Output is correct
3 Correct 14 ms 15212 KB Output is correct
4 Correct 14 ms 15596 KB Output is correct
5 Correct 14 ms 15488 KB Output is correct
6 Correct 14 ms 15596 KB Output is correct
7 Correct 9 ms 12780 KB Output is correct
8 Correct 102 ms 1920 KB Output is correct
9 Correct 297 ms 19564 KB Output is correct
10 Correct 274 ms 19436 KB Output is correct
11 Correct 70 ms 1772 KB Output is correct
12 Correct 168 ms 3436 KB Output is correct
13 Correct 211 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 14 ms 15616 KB Output is correct
3 Correct 14 ms 15212 KB Output is correct
4 Correct 14 ms 15596 KB Output is correct
5 Correct 14 ms 15488 KB Output is correct
6 Correct 14 ms 15596 KB Output is correct
7 Correct 9 ms 12780 KB Output is correct
8 Correct 102 ms 1920 KB Output is correct
9 Correct 297 ms 19564 KB Output is correct
10 Correct 274 ms 19436 KB Output is correct
11 Correct 70 ms 1772 KB Output is correct
12 Correct 168 ms 3436 KB Output is correct
13 Correct 211 ms 19180 KB Output is correct
14 Correct 594 ms 19632 KB Output is correct
15 Correct 581 ms 19436 KB Output is correct
16 Correct 571 ms 19436 KB Output is correct
17 Correct 603 ms 19564 KB Output is correct
18 Correct 593 ms 19564 KB Output is correct