Submission #1098755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098755		SSSM	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	0 ms	348 KiB

apple

#include <bits/stdc++.h>

/*
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
*/

using namespace std;

/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) (a%mod+mod)%mod
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc id<<1
#define rc lc|1
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn=1e5+10, mod=1e9+7, INF=1e18, LOG=60, sq=1e3;

ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

ll n;
vector<ll> seg, lz;
vector<pll> ch;

void Make(ll l, ll r, ll id)
{
    ch[id].F=ch.size();
    ch.pb({-1, -1});
    seg.pb(0);
    lz.pb(-1);
    ch[id].S=ch.size();
    ch.pb({-1, -1});
    seg.pb(0);
    lz.pb(-1);
}

void Modify(ll l, ll r, ll id, ll x)
{
    lz[id]=x;
    seg[id]=(r-l)*x;
}

void Shift(ll l, ll r, ll id)
{
    if(ch[id].F==-1) Make(l, r, id);
    if(lz[id]!=-1 && r-l>1)
    {
        Modify(l, mid, ch[id].F, lz[id]);
        Modify(l, mid, ch[id].S, lz[id]);
        //cout<<id<<"***\n";
        lz[id]=-1;
    }
}

void Upd(ll s, ll e, ll x, ll l=1, ll r=mod, ll id=0)
{
   // cout<<id<<"+++\n";
    if(l>=e || r<=s) return;
    if(s<=l && r<=e){
        Modify(l, r, id, x);
        return;
    }
    Shift(l, r, id);
    Upd(s, e, x, l, mid, ch[id].F);
    Upd(s, e, x, mid, r, ch[id].S);
    seg[id]=seg[ch[id].F]+seg[ch[id].S];
}

ll Get(ll s, ll e, ll l=1, ll r=mod, ll id=0)
{
    if(l>=e || r<=s) return 0;
    if(s<=l && r<=e) return seg[id];
    Shift(l, r, id);
    return Get(s, e, l, mid, ch[id].F)+Get(s, e, mid, r, ch[id].S);
}

int main() {
    
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n;
    ll c=0;

    seg.pb(0);
    lz.pb(-1);
    ch.pb({-1, -1});
    while(n--)
    {
        ll t, l, r;
        cin>>t>>l>>r;
        l+=c;
        r+=c+1;
        if(t==1)
        {
           ll ans=Get(l, r);
           c=ans;
           cout<<ans<<"\n";
        }
        else
        {
            Upd(l, r, 1);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100