Submission #576902

#	Time	Username	Problem	Language	Result	Execution time	Memory
576902		ThegeekKnight16	Simple game (IZhO17_game)	C++17	100 / 100	603 ms	25344 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51