Submission #930961

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930961	2024-02-21T00:41:53 Z	Regulus	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	74 ms	42160 KB

apple

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
//#define TEST

const int N = 1e5+5;
int tot = 0;
struct SegTree {
    int sum=0, l=0, r=0, laz=0;
} Seg[N * 35];

inline void push(int L, int R, int v)
{
    if (!Seg[v].laz) return;
    int mid((L+R) >> 1);
    if (!Seg[v].l) Seg[v].l = ++tot;
    if (!Seg[v].r) Seg[v].r = ++tot;
    Seg[Seg[v].l].sum = mid - L + 1;
    Seg[Seg[v].r].sum = R - mid;
    Seg[Seg[v].l].laz = Seg[Seg[v].r].laz = 1;
    Seg[v].laz = 0;
}

inline void modify(int L, int R, int ql, int qr, int v)
{
    if (Seg[v].sum == R-L+1) return;
    if (ql <= L && R <= qr)
    {
        //debug(L), debug(R), endl;
        Seg[v].sum = R - L + 1, Seg[v].laz = 1;
        return;
    }

    int mid((L+R) >> 1);
    if (ql <= mid)
    {
        if (!Seg[v].l) Seg[v].l = ++tot;
        modify(L, mid, ql, qr, Seg[v].l);
    }
    if (qr > mid)
    {
        if (!Seg[v].r) Seg[v].r = ++tot;
        modify(mid+1, R, ql, qr, Seg[v].r);
    }
    Seg[v].sum = Seg[Seg[v].l].sum + Seg[Seg[v].r].sum;
}

inline int query(int L, int R, int ql, int qr, int v)
{
    //debug(L), debug(R), debug(Seg[v].sum), endl;
    if (ql <= L && R <= qr) return Seg[v].sum;

    int mid((L+R) >> 1), ret = 0;
    push(L, R, v);
    if (ql <= mid && Seg[v].l)
        ret += query(L, mid, ql, qr, Seg[v].l);
    if (qr > mid && Seg[v].r)
        ret += query(mid+1, R, ql, qr, Seg[v].r);
    return ret;
}

int main(void)
{ IO
    int Q, cur=0, i;

    cin >> Q;
    tot = 1;
    do {
        int ty, L, R; cin >> ty >> L >> R;

        L += cur, R += cur;
        if (ty == 2)
        {
            modify(1, 1e9, L, R, 1);
        } else {
            int ret = query(1, 1e9, L, R, 1);
            cur = ret;
            cout << ret << '\n';
        }
    } while (--Q);

    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:75:19: warning: unused variable 'i' [-Wunused-variable]
   75 |     int Q, cur=0, i;
      |                   ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	5 ms	2652 KB	Output is correct
5	Correct	6 ms	2652 KB	Output is correct
6	Correct	5 ms	2652 KB	Output is correct
7	Correct	5 ms	2652 KB	Output is correct
8	Correct	28 ms	11760 KB	Output is correct
9	Correct	57 ms	19028 KB	Output is correct
10	Correct	59 ms	21188 KB	Output is correct
11	Correct	58 ms	21076 KB	Output is correct
12	Correct	62 ms	21144 KB	Output is correct
13	Correct	61 ms	23636 KB	Output is correct
14	Correct	59 ms	23528 KB	Output is correct
15	Correct	74 ms	39992 KB	Output is correct
16	Correct	72 ms	40020 KB	Output is correct
17	Correct	54 ms	23680 KB	Output is correct
18	Correct	57 ms	23612 KB	Output is correct
19	Correct	70 ms	42068 KB	Output is correct
20	Correct	70 ms	42160 KB	Output is correct