Submission #1096500

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1096500	2024-10-04T15:59:01 Z	mohammadsam	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	419 ms	207736 KB

apple

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("f.in", "r", stdin); freopen("f.out", "w", stdout);
#define md(x)         (((x%MD)+MD)%MD)
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;
struct node{
    int sum, lazy;
    node  *lid , *rid;
    node(int s,int l,node* l1,node* r1){sum=s,lazy = l ,lid = l1,rid = r1;}
    node(){}
};
node* seg;
node* build(int l,int r){
    node* a = new node(0,-1,NULL,NULL);
    return a;
}
void relax(node* u,int l,int r){
    int mid = (l+r)>>1;
    if(u->lazy == -1) return;
    u->lid->lazy = u->lazy;
    u->rid->lazy = u->lazy;
    u->lid->sum = (mid-l);
    u->rid->sum = (r-mid);
    u->lazy = -1;
}
void update(int s,int e,int v,node* u = seg,int l=1,int r=inf){
    if(e <= s or e <= l or r <= s) return;
    if(s <= l and r <= e){
        u->lazy = v;
        u->sum = (r-l);
        return;
    }
    int mid = (l+r)>>1;
    if(u->lid == NULL) u->lid = build(l,mid);
    if(u->rid == NULL) u->rid = build(mid,r);
    relax(u,l,r);
    update(s,e,v,u->lid,l,mid);
    update(s,e,v,u->rid,mid,r);
    u->sum = u->lid->sum + u->rid->sum;
}
int get(int s,int e,node* u = seg,int l=1,int r=inf){
    if(e <= s ) return 0;
    if(s <= l and r <= e) return u->sum;
    int mid = (l+r)>>1;
    if(u->lid == NULL) u->lid = build(l,mid);
    if(u->rid == NULL) u->rid = build(mid,r);
    relax(u,l,r);
    if(e <= mid) return get(s,e,u->lid,l,mid);
    if(s >= mid) return get(s,e,u->rid,mid,r);
    return get(s,e,u->lid,l,mid)+get(s,e,u->rid,mid,r);
}
int32_t main() {
    //ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int q;
    cin >> q;
    int c = 0;
    seg = build(1,inf);
    for(int i = 0;i<q;i++){
        int d,l,r;
        cin >> d >> l >> r;
        if(d==1) cout << get(l+c,r+c+1) << endl;
        else update(l+c,r+c+1,1);
        if(d==1) c = get(l+c,r+c+1);
        
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	4888 KB	Output is correct
5	Correct	19 ms	6144 KB	Output is correct
6	Correct	19 ms	5724 KB	Output is correct
7	Correct	19 ms	6024 KB	Output is correct
8	Correct	131 ms	44420 KB	Output is correct
9	Correct	273 ms	77276 KB	Output is correct
10	Correct	277 ms	85300 KB	Output is correct
11	Correct	277 ms	91728 KB	Output is correct
12	Correct	304 ms	94520 KB	Output is correct
13	Correct	301 ms	110164 KB	Output is correct
14	Correct	303 ms	111392 KB	Output is correct
15	Correct	400 ms	201812 KB	Output is correct
16	Correct	410 ms	203348 KB	Output is correct
17	Correct	304 ms	114772 KB	Output is correct
18	Correct	298 ms	114768 KB	Output is correct
19	Correct	410 ms	207736 KB	Output is correct
20	Correct	419 ms	207696 KB	Output is correct