oj.uz

Submission #890626

# Submission time Handle Problem Language Result Execution time Memory
890626 2023-12-21T17:05:42 Z aykhn Simple game (IZhO17_game) C++17
100 / 100
 142 ms 20048 KB 
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcountll
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;

int n, m, sz = 1;
int a[MXN], st[40*MXN];

void add(int l, int r, int x, int lx, int rx, int val)
{
    if (l >= rx || r <= lx) return;
    if (l >= lx && r <= rx)
    {
        st[x] += val;
        return;
    }
    int mid = (l + r) >> 1;
    add(l, mid, 2*x + 1, lx, rx, val);
    add(mid, r, 2*x + 2, lx, rx, val);
}

int get(int l, int r, int x, int ind)
{
    if (l + 1 == r) return st[x];
    int mid = (l + r) >> 1;
    if (ind < mid) return st[x] + get(l, mid, 2*x + 1, ind);
    else return st[x] + get(mid, r, 2*x + 2, ind);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    while (sz < 10*MXN) sz <<= 1;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        int l = min(a[i - 1], a[i]);
        int r = max(a[i - 1], a[i]);
        if (l + 1 <= r - 1) add(0, sz, 0, l + 1, r, 1);
    }
    while (m--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int pos, val;
            cin >> pos >> val;
            if (pos > 1)
            {
                int l = min(a[pos - 1], a[pos]);
                int r = max(a[pos - 1], a[pos]);
                if (l + 1 <= r - 1) add(0, sz, 0, l + 1, r, -1);
            }
            if (pos < n)
            {
                int l = min(a[pos + 1], a[pos]);
                int r = max(a[pos + 1], a[pos]);
                if (l + 1 <= r - 1) add(0, sz, 0, l + 1, r, -1);
            }
            a[pos] = val;
            if (pos > 1)
            {
                int l = min(a[pos - 1], a[pos]);
                int r = max(a[pos - 1], a[pos]);
                if (l + 1 <= r - 1) add(0, sz, 0, l + 1, r, 1);
            }
            if (pos < n)
            {
                int l = min(a[pos + 1], a[pos]);
                int r = max(a[pos + 1], a[pos]);
                if (l + 1 <= r - 1) add(0, sz, 0, l + 1, r, 1);
            }
        }
        else
        {
            int h;
            cin >> h;
            cout << get(0, sz, 0, h) << '\n';
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 16952 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17240 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 16952 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17240 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 28 ms 8164 KB Output is correct
9 Correct 70 ms 20048 KB Output is correct
10 Correct 67 ms 19976 KB Output is correct
11 Correct 20 ms 1884 KB Output is correct
12 Correct 51 ms 11224 KB Output is correct
13 Correct 47 ms 7204 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 16952 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 17240 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 28 ms 8164 KB Output is correct
9 Correct 70 ms 20048 KB Output is correct
10 Correct 67 ms 19976 KB Output is correct
11 Correct 20 ms 1884 KB Output is correct
12 Correct 51 ms 11224 KB Output is correct
13 Correct 47 ms 7204 KB Output is correct
14 Correct 127 ms 19976 KB Output is correct
15 Correct 124 ms 20032 KB Output is correct
16 Correct 130 ms 19796 KB Output is correct
17 Correct 123 ms 19996 KB Output is correct
18 Correct 142 ms 20020 KB Output is correct