oj.uz

Submission #1098517

# Submission time Handle Problem Language Result Execution time Memory
1098517 2024-10-09T13:23:32 Z anhthi Simple game (IZhO17_game) C++14
100 / 100
 47 ms 7004 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define heap priority_queue
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

 
template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }
 
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }
 
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }
 
int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcnt(ll x) { return __builtin_popcount(x); }
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}
 
const ll oo = (ll) 1e18 + 5;
const int inf = (ll) 1e9 + 7, mod = (ll) 1e9 + 7;
 
const int N = 1e5 + 5, M = 1e6 + 5;
 
void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

int n, m;
int a[N];

struct fen {
    int n;
    vector<int> bit;
    fen(int n) : n(n) {
        bit.resize(n + 1);
    }
    void upd(int p, int d) {
        for (; p <= n; p += p & -p)
            bit[p] += d;
        return;
    }
    void upd(int l, int r, int d) {
        if (l > r) swap(l, r);
        upd(l, +d); upd(r + 1, -d);
    }
    int get(int p) {
        int ans = 0;
        for (; p > 0; p -= p & -p)
            ans += bit[p];
        return ans;
    }
};

int main(void) {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    rep(i, n) cin >> a[i];

    fen f(M);
    forn(i, 2, n) {
        f.upd(a[i - 1], a[i], +1);
    }

    rep(_, m) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;

            if (pos > 1) f.upd(a[pos - 1], a[pos], -1);
            if (pos < n) f.upd(a[pos + 1], a[pos], -1);

            a[pos] = val;

            if (pos > 1) f.upd(a[pos - 1], a[pos], +1);
            if (pos < n) f.upd(a[pos + 1], a[pos], +1);

        }
        else {
            int H;
            cin >> H;
            cout << f.get(H) << '\n';
        }

    }

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4184 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 27 ms 5724 KB Output is correct
9 Correct 31 ms 7004 KB Output is correct
10 Correct 31 ms 6992 KB Output is correct
11 Correct 25 ms 5460 KB Output is correct
12 Correct 27 ms 6740 KB Output is correct
13 Correct 37 ms 6748 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4184 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 27 ms 5724 KB Output is correct
9 Correct 31 ms 7004 KB Output is correct
10 Correct 31 ms 6992 KB Output is correct
11 Correct 25 ms 5460 KB Output is correct
12 Correct 27 ms 6740 KB Output is correct
13 Correct 37 ms 6748 KB Output is correct
14 Correct 42 ms 6972 KB Output is correct
15 Correct 41 ms 6740 KB Output is correct
16 Correct 47 ms 6740 KB Output is correct
17 Correct 43 ms 6736 KB Output is correct
18 Correct 40 ms 6740 KB Output is correct