oj.uz

Submission #867644

# Submission time Handle Problem Language Result Execution time Memory
867644 2023-10-29T04:05:39 Z sleepntsheep Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 235 ms 99288 KB 
#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

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;
      |             ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 408 KB Output is correct
4 Correct 8 ms 5432 KB Output is correct
5 Correct 11 ms 5724 KB Output is correct
6 Correct 11 ms 5600 KB Output is correct
7 Correct 12 ms 5720 KB Output is correct
8 Correct 68 ms 23636 KB Output is correct
9 Correct 160 ms 36432 KB Output is correct
10 Correct 171 ms 37692 KB Output is correct
11 Correct 173 ms 43048 KB Output is correct
12 Correct 179 ms 43376 KB Output is correct
13 Correct 172 ms 54952 KB Output is correct
14 Correct 155 ms 55180 KB Output is correct
15 Correct 220 ms 98132 KB Output is correct
16 Correct 219 ms 98456 KB Output is correct
17 Correct 157 ms 55860 KB Output is correct
18 Correct 171 ms 55884 KB Output is correct
19 Correct 218 ms 99288 KB Output is correct
20 Correct 235 ms 99132 KB Output is correct