Submission #867644

#TimeUsernameProblemLanguageResultExecution timeMemory
867644sleepntsheepMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
235 ms99288 KiB
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005
#define M 80*N

int ALLOC = 1, A[M], L[M], R[M];

int sparse0() { return ALLOC++; }

void push(int v, int l, int r)
{
    if (!L[v] && l != r)
    {
        int m = (l+r)/2;
        L[v] = sparse0();
        R[v] = sparse0();
    }
    if (A[v] == r-l+1)
    {
        if (l != r)
        {
            int m = (l+r)/2;
            A[L[v]] = m-l+1, A[R[v]] = r-m;
        }
    }
}

void ripe(int v, int l, int r, int x, int y)
{
    push(v, l,r );
    if (r < x || y < l) return;
    if (x <= l && r <= y) { A[v] = r-l+1; push(v, l, r); return; }
    int m = (l+r)/2;
    ripe(L[v], l, m, x, y), ripe(R[v], m+1, r, x, y); A[v] = A[L[v]] + A[R[v]];
}

int query(int v, int l, int r,int x, int y)
{
    push(v, l, r);
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) return A[v];
    return query(L[v], l, (l+r)/2, x, y) + query(R[v], (l+r)/2+1, r, x, y);
}

int main()
{
    ++ALLOC;
    ShinLena;
    int m = 1, d, x, y, c = 0;
    for (cin >> m; m--;)
    {
        cin >> d >> x >> y;
        if (d == 1) cout << (c = query(1, 1, 1e9, x+c, y+c)) << '\n';
        else ripe(1, 1, 1e9, x+c, y+c);
    }
    return 0;
}


Compilation message (stderr)

apple.cpp: In function 'void push(int, int, int)':
apple.cpp:25:13: warning: unused variable 'm' [-Wunused-variable]
   25 |         int m = (l+r)/2;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...