oj.uz

Submission #345535

# Submission time Handle Problem Language Result Execution time Memory
345535 2021-01-07T14:38:40 Z _ani Simple game (IZhO17_game) C++17
100 / 100
 469 ms 11256 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1'000'002;
const int H = 1'000'000;
int a[N], t[4 * N];
void Upd (int v, int vl, int vr, int l, int r, int val)
{
    if (vl == l && r == vr)
    {
        t[v] += val;
        return;
    }
    int m = (vl + vr) / 2;
    if (l <= m)
        Upd (v * 2, vl, m, l, min (r, m), val);
    if (r > m)
        Upd (v * 2 + 1, m + 1, vr, max (m + 1, l), r, val);
}
int Get (int v, int vl, int vr, int pos)
{
    if (vl == vr)
        return t[v];
    int m = (vl + vr) / 2;
    if (pos <= m)
        return t[v] + Get (v * 2, vl, m, pos);
    return t[v] + Get (v * 2 + 1, m + 1, vr, pos);
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i != 0)
        {
            Upd (1, 1, H, min (a[i - 1], a[i]), max (a[i - 1], a[i]), 1);
        }
    }
    while (m--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            pos--;
            if (pos != 0)
            {
                Upd (1, 1, H, min (a[pos - 1], a[pos]), max (a[pos - 1], a[pos]), -1);
                Upd (1, 1, H, min (a[pos - 1], val), max (a[pos - 1], val), 1);
            }
            if (pos != n - 1)
            {
                Upd (1, 1, H, min (a[pos + 1], a[pos]), max (a[pos + 1], a[pos]), -1);
                Upd (1, 1, H, min (a[pos + 1], val), max (a[pos + 1], val), 1);
            }
            a[pos] = val;
        }
        else
        {
            int h;
            cin >> h;
            cout << Get (1, 1, H, h) << '\n';
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 6636 KB Output is correct
3 Correct 9 ms 6380 KB Output is correct
4 Correct 9 ms 6508 KB Output is correct
5 Correct 10 ms 6600 KB Output is correct
6 Correct 10 ms 6636 KB Output is correct
7 Correct 6 ms 364 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 12 ms 6636 KB Output is correct
3 Correct 9 ms 6380 KB Output is correct
4 Correct 9 ms 6508 KB Output is correct
5 Correct 10 ms 6600 KB Output is correct
6 Correct 10 ms 6636 KB Output is correct
7 Correct 6 ms 364 KB Output is correct
8 Correct 351 ms 1832 KB Output is correct
9 Correct 468 ms 11164 KB Output is correct
10 Correct 469 ms 11128 KB Output is correct
11 Correct 315 ms 1644 KB Output is correct
12 Correct 441 ms 3052 KB Output is correct
13 Correct 345 ms 2840 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 12 ms 6636 KB Output is correct
3 Correct 9 ms 6380 KB Output is correct
4 Correct 9 ms 6508 KB Output is correct
5 Correct 10 ms 6600 KB Output is correct
6 Correct 10 ms 6636 KB Output is correct
7 Correct 6 ms 364 KB Output is correct
8 Correct 351 ms 1832 KB Output is correct
9 Correct 468 ms 11164 KB Output is correct
10 Correct 469 ms 11128 KB Output is correct
11 Correct 315 ms 1644 KB Output is correct
12 Correct 441 ms 3052 KB Output is correct
13 Correct 345 ms 2840 KB Output is correct
14 Correct 454 ms 11204 KB Output is correct
15 Correct 460 ms 11256 KB Output is correct
16 Correct 413 ms 11128 KB Output is correct
17 Correct 430 ms 11204 KB Output is correct
18 Correct 406 ms 11216 KB Output is correct