oj.uz

Submission #682517

# Submission time Handle Problem Language Result Execution time Memory
682517 2023-01-16T11:50:29 Z opPO Simple game (IZhO17_game) C++17
100 / 100
 234 ms 19792 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 1e6 + 10;
int sum[4 * N];

void push(int v)
{
    if (sum[v] != 0)
    {
        sum[2 * v + 1] += sum[v];
        sum[2 * v + 2] += sum[v];
        sum[v] = 0;
    }
}

void upd(int l, int r, int delta, int v, int tl, int tr)
{
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r)
    {
        sum[v] += delta;
        return;
    }
    push(v);
    int m = (tl + tr) / 2;
    upd(l, r, delta, 2 * v + 1, tl, m);
    upd(l, r, delta, 2 * v + 2, m + 1, tr);
}

int get(int idx, int v, int tl, int tr)
{
    if (tl == tr) return sum[v];
    push(v);
    int m = (tl + tr) / 2;
    if (idx <= m) return get(idx, 2 * v + 1, tl, m);
    else return get(idx, 2 * v + 2, m + 1, tr);
}

void solve()
{
    int n, q;
    cin >> n >> q;
    vec<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int mn = min(a[i], a[i + 1]);
        int mx = a[i] + a[i + 1] - mn;
        upd(mn, mx, +1, 0, 1, N - 1);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int p, x;
            cin >> p >> x;
            if (p > 1)
            {
                int mn = min(a[p - 1], a[p]);
                int mx = a[p - 1] + a[p] - mn;
                upd(mn, mx, -1, 0, 1, N - 1);
            }
            if (p < n)
            {
                int mn = min(a[p], a[p + 1]);
                int mx = a[p] + a[p + 1] - mn;
                upd(mn, mx, -1, 0, 1, N - 1);
            }
            a[p] = x;
            if (p > 1)
            {
                int mn = min(a[p - 1], a[p]);
                int mx = a[p - 1] + a[p] - mn;
                upd(mn, mx, +1, 0, 1, N - 1);
            }
            if (p < n)
            {
                int mn = min(a[p], a[p + 1]);
                int mx = a[p] + a[p + 1] - mn;
                upd(mn, mx, +1, 0, 1, N - 1);
            }
        }
        else
        {
            int h;
            cin >> h;
            cout << get(h, 0, 1, N - 1) << "\n";
        }
    }
}

int32_t main()
{
//    freopen("game.in", "r", stdin);
//    freopen("game.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 11860 KB Output is correct
4 Correct 7 ms 11972 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 5 ms 9632 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 11860 KB Output is correct
4 Correct 7 ms 11972 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 5 ms 9632 KB Output is correct
8 Correct 40 ms 2032 KB Output is correct
9 Correct 108 ms 19664 KB Output is correct
10 Correct 107 ms 19692 KB Output is correct
11 Correct 35 ms 1996 KB Output is correct
12 Correct 66 ms 3588 KB Output is correct
13 Correct 65 ms 19508 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 11860 KB Output is correct
4 Correct 7 ms 11972 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 8 ms 11972 KB Output is correct
7 Correct 5 ms 9632 KB Output is correct
8 Correct 40 ms 2032 KB Output is correct
9 Correct 108 ms 19664 KB Output is correct
10 Correct 107 ms 19692 KB Output is correct
11 Correct 35 ms 1996 KB Output is correct
12 Correct 66 ms 3588 KB Output is correct
13 Correct 65 ms 19508 KB Output is correct
14 Correct 234 ms 19740 KB Output is correct
15 Correct 215 ms 19704 KB Output is correct
16 Correct 204 ms 19792 KB Output is correct
17 Correct 196 ms 19784 KB Output is correct
18 Correct 210 ms 19660 KB Output is correct