Submission #1098756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098756	2024-10-09T20:46:04 Z	SSSM	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	466 ms	219696 KB

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(mid, r, 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	4808 KB	Output is correct
5	Correct	19 ms	5580 KB	Output is correct
6	Correct	19 ms	5324 KB	Output is correct
7	Correct	19 ms	5576 KB	Output is correct
8	Correct	124 ms	35924 KB	Output is correct
9	Correct	278 ms	72568 KB	Output is correct
10	Correct	273 ms	77960 KB	Output is correct
11	Correct	290 ms	82292 KB	Output is correct
12	Correct	297 ms	84012 KB	Output is correct
13	Correct	318 ms	121300 KB	Output is correct
14	Correct	315 ms	121200 KB	Output is correct
15	Correct	446 ms	219692 KB	Output is correct
16	Correct	466 ms	219696 KB	Output is correct
17	Correct	316 ms	121316 KB	Output is correct
18	Correct	327 ms	121200 KB	Output is correct
19	Correct	427 ms	219692 KB	Output is correct
20	Correct	415 ms	219628 KB	Output is correct