Submission #930961

#	Time	Username	Problem	Language	Result	Execution time	Memory
930961		Regulus	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	74 ms	42160 KiB

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 (stderr)

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 / 100