제출 #1001047

#제출 시각아이디문제언어결과실행 시간메모리
1001047rahidilbayramli원숭이와 사과 나무 (IZhO12_apple)C++17
0 / 100
222 ms191376 KiB
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
const ll sz = 6e6+7;
ll L[sz], R[sz], segtree[sz], lazy[sz], nxt = 1;
void push(ll v, ll l, ll r)
{
    if(lazy[v] != 0)
    {
        segtree[v] = (r - l + 1);
        if(l != r)
        {
            if(!L[v])
                L[v] = ++nxt;
            if(!R[v])
                R[v] = ++nxt;
            lazy[L[v]] = 1;
            lazy[R[v]] = 1;
        }
        lazy[v] = 0;
    }
}
void update(ll v, ll l, ll r, ll tl, ll tr)
{
    push(v, l, r);
    if(l > r || l > tr || r < tl)
        return;
    if(tl <= l && r <= tr)
    {
        segtree[v] = (r - l + 1);
        if(l != r)
        {
            if(!L[v])
                L[v] = ++nxt;
            if(!R[v])
                R[v] = ++nxt;
            lazy[L[v]] = 1;
            lazy[R[v]] = 1;
        }
        return;
    }
    ll mid = (l + r) / 2;
    if(!L[v])
        L[v] = ++nxt;
    if(!R[v])
        R[v] = ++nxt;
    update(L[v], l, mid, tl, tr);
    update(R[v], mid+1, r, tl, tr);
    segtree[v] = segtree[L[v]] + segtree[R[v]];
}
ll findsum(ll v, ll l, ll r, ll tl, ll tr)
{
    if(l > r || l > tr || r < tl)
        return 0;
    push(v, l, r);
    if(tl <= l && r <= tr)
        return segtree[v];
    else
    {
        ll mid = (l + r) / 2;
        ll lans = 0, rans = 0;
        if(L[v])
            lans = findsum(L[v], l, mid, tl, tr);
        if(R[v])
            rans = findsum(R[v], mid+1, r, tl, tr);
        return lans + rans;
    }
}
void solve()
{
    ll n = 1e9+7, m, i, c = 0;
    cin >> m;
    for(i = 1; i <= m; i++)
    {
        ll type;
        cin >> type;
        if(type == 2){
            ll l, r;
            cin >> l >> r;
            l += c, r += c;
            update(1, 1, n, l, r);
        }
        else{
            ll l, r;
            cin >> l >> r;
            l += c, r += c;
            c = findsum(1, 1, n, l, r);
            cout << c << "\n";
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...