oj.uz

Submission #576902

# Submission time Handle Problem Language Result Execution time Memory
576902 2022-06-13T18:01:09 Z ThegeekKnight16 Simple game (IZhO17_game) C++17
100 / 100
 603 ms 25344 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int altura[MAXN];
vector<int> e, d, sum, lz;

int create()
{
    e.push_back(0);
    d.push_back(0);
    sum.push_back(0);
    lz.push_back(0);
    return sum.size()-1;
}

void refresh(int pos, int ini, int fim)
{
    if (pos == 0 || lz[pos] == 0) return;
    sum[pos] += lz[pos] * (fim - ini + 1);

    if (ini != fim)
    {
        if (e[pos] == 0)
        {
            int aux = create();
            e[pos] = aux;
        }

        if (d[pos] == 0)
        {
            int aux = create();
            d[pos] = aux;
        }

        lz[e[pos]] += lz[pos];
        lz[d[pos]] += lz[pos];
    }

    lz[pos] = 0;
}

void update(int pos, int ini, int fim, int p, int q, int val)
{
    if (p > q) swap(p, q);
    refresh(pos, ini, fim);
    if (pos == 0) return;
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q)
    {
        lz[pos] += val;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    if (e[pos] == 0)
    {
        int aux = create();
        e[pos] = aux;
    }

    if (d[pos] == 0)
    {
        int aux = create();
        d[pos] = aux;
    }

    update(e[pos], ini,  m , p, q, val);
    update(d[pos], m+1, fim, p, q, val);
    sum[pos] = sum[e[pos]] + sum[d[pos]];
}

int query(int pos, int ini, int fim, int p, int q)
{
    if (p > q) swap(p, q);
    refresh(pos, ini, fim);
    if (pos == 0) return 0;
    if (q < ini || p > fim) return 0;
    if (p <= ini && fim <= q) return sum[pos];
    int m = (ini + fim) >> 1;
    return query(e[pos], ini, m, p, q) + query(d[pos], m+1, fim, p, q);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    create(); create();
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> altura[i];
    altura[0] = -1; altura[N+1] = -1;

    for (int i = 2; i <= N; i++)
    {
        int lastH = altura[i-1];
        int novoH = altura[i];
        update(1, 1, 1e6 + 10, lastH, novoH, 1);
    }

    for (int m = 1; m <= M; m++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int X, val;
            cin >> X >> val;
            int lastH = altura[X-1]; int nextH = altura[X+1];
            if (lastH != -1) {update(1, 1, 1e6 + 10, lastH, altura[X], -1); update(1, 1, 1e6 + 10, lastH, val, +1);}
            if (nextH != -1) {update(1, 1, 1e6 + 10, nextH, altura[X], -1); update(1, 1, 1e6 + 10, nextH, val, +1);}
            altura[X] = val;
        }
        else
        {
            int H;
            cin >> H;
            cout << query(1, 1, 1e6 + 10, H, H) << '\n';
        }
    }

}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1448 KB Output is correct
3 Correct 6 ms 1416 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 6 ms 1488 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1448 KB Output is correct
3 Correct 6 ms 1416 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 6 ms 1488 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 81 ms 1576 KB Output is correct
9 Correct 284 ms 25344 KB Output is correct
10 Correct 293 ms 25296 KB Output is correct
11 Correct 64 ms 1532 KB Output is correct
12 Correct 171 ms 3756 KB Output is correct
13 Correct 159 ms 19264 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1448 KB Output is correct
3 Correct 6 ms 1416 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 6 ms 1484 KB Output is correct
6 Correct 6 ms 1488 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 81 ms 1576 KB Output is correct
9 Correct 284 ms 25344 KB Output is correct
10 Correct 293 ms 25296 KB Output is correct
11 Correct 64 ms 1532 KB Output is correct
12 Correct 171 ms 3756 KB Output is correct
13 Correct 159 ms 19264 KB Output is correct
14 Correct 577 ms 25000 KB Output is correct
15 Correct 589 ms 25024 KB Output is correct
16 Correct 570 ms 24868 KB Output is correct
17 Correct 571 ms 25060 KB Output is correct
18 Correct 603 ms 25024 KB Output is correct