oj.uz

Submission #173721

# Submission time Handle Problem Language Result Execution time Memory
173721 2020-01-05T08:42:29 Z srvlt Simple game (IZhO17_game) C++14
100 / 100
 86 ms 7036 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;

#define ll long long
#define db double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define endl "\n"
//#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 1e5 + 3, K = 1e6;
int n, m, a[N], fen[K + 3];

void upd(int x, int y) {
    for (; x <= K; x |= (x + 1)) {
        fen[x] += y;
    }
}

int get(int x) {
    int res = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1) {
        res += fen[x];
    }
    return res;
}

void add(int l, int r) {
    if (l > r) {
        swap(l, r);
    }
    r--;
    if (l > r) {
        return;
    }
    upd(l, 1);
    upd(r + 1, -1);
}

void del(int l, int r) {
    if (l > r) {
        swap(l, r);
    }
    r--;
    if (l > r) {
        return;
    }
    upd(l, -1);
    upd(r + 1, 1);
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n >> m;

    int l, r;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i > 1) {
            l = a[i - 1], r = a[i];
            add(l, r);
        }
    }
    int t, pos, val, h;
    for (int i = 1; i <= m; i++) {
        cin >> t;
        if (t == 1) {
            cin >> pos >> val;
            if (pos > 1) {
                l = a[pos - 1], r = a[pos];
                del(l, r);

                l = a[pos - 1], r = val;
                add(l, r);
            }
            if (pos < n) {
                l = a[pos], r = a[pos + 1];
                del(l, r);

                l = val, r = a[pos + 1];
                add(l, r);
            }
            a[pos] = val;
        }   else {
            cin >> h;
            cout << get(h) << endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 6 ms 4036 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 3960 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 45 ms 1836 KB Output is correct
9 Correct 64 ms 7036 KB Output is correct
10 Correct 67 ms 6904 KB Output is correct
11 Correct 39 ms 1656 KB Output is correct
12 Correct 49 ms 2808 KB Output is correct
13 Correct 50 ms 2808 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 6 ms 4036 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 3960 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 45 ms 1836 KB Output is correct
9 Correct 64 ms 7036 KB Output is correct
10 Correct 67 ms 6904 KB Output is correct
11 Correct 39 ms 1656 KB Output is correct
12 Correct 49 ms 2808 KB Output is correct
13 Correct 50 ms 2808 KB Output is correct
14 Correct 86 ms 6876 KB Output is correct
15 Correct 84 ms 6952 KB Output is correct
16 Correct 81 ms 6904 KB Output is correct
17 Correct 85 ms 6904 KB Output is correct
18 Correct 85 ms 6904 KB Output is correct