Submission #1325570

#TimeUsernameProblemLanguageResultExecution timeMemory
1325570itsKiaRashMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
69 ms28856 KiB
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds; // find_by_order   order_of_key
// template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize ("Ofast")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//#define int ll
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define testc int ttt;cin>>ttt;while(ttt--)
#define alll(x)	(x).begin(),(x).end()
#define pqi priority_queue<pii, vector<pii>, greater<pii>>
#define kill(x)  cout << x << '\n', exit(0)
#define rep(x) cerr<<"report: "<<x<<endl;
#define endl '\n'
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define ff first
#define ss second
#define bg begin
#define rbg rbegin
#define sz size()
#define mset(x,y) memset(x,y,sizeof(x))
#define clr clear()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define vci vector<int>
#define sti set<int>
#define nl cout<<endl
#define upb upper_bound
#define lrb lower_bound
//ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
const ll inf = (ll)1e18 + 18;
const int maxn = 1e5 + 7, MX = 1e9 + 7, mod = 1e9 + 7; //998244353 1594778359 1540481779
int n, q, last, cnt = 1;
#define lc seg[id].l
#define rc seg[id].r
struct node{
    int l = 0, r = 0, val = 0;
} seg[maxn * 70];
void upd(int id, int L, int R, int l, int r){
    if(L > r || R < l || R < L) return;
    if(seg[id].val == R - L + 1) return;
    if(L >= l && R <= r){
        seg[id].val = R - L + 1; return;
    }
    int mid = L + R >> 1;
    if(!lc) lc = ++cnt; if(!rc) rc = ++cnt;
    if(seg[id].val == R - L + 1) {seg[lc].val = mid - L + 1; seg[rc].val = R - mid;}
    upd(lc, L, mid, l, r); upd(rc, mid + 1, R, l, r);
    seg[id].val = seg[lc].val + seg[rc].val;
}
int get(int id, int L, int R, int l, int r){
    if(L > r || R < l || R < L) return 0;
    if(L >= l && R <= r) return seg[id].val;
    int mid = L + R >> 1;
    if(!lc) lc = ++cnt; if(!rc) rc = ++cnt;
    if(seg[id].val == R - L + 1) {seg[lc].val = mid - L + 1; seg[rc].val = R - mid;}
    return get(lc, L, mid, l, r) + get(rc, mid + 1, R, l, r);
}

int32_t main(){
    FAST_IO
    cin >> q ;
    // rep(get(1, 1, MX, 1, 10));
    while(q --){
        int d, l, r; cin >> d >> l >> r ; l += last; r += last;
        if(d == 1){
            last = get(1, 1, MX, l, r); cout << last << endl;
        }
        if(d == 2){
            upd(1, 1, MX, l, r);
        }
        // rep(get(1, 1, MX, 1, 10));
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...