Submission #1096501

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1096501	2024-10-04T15:59:40 Z	mohammadsam	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	274 ms	137312 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;

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 = 1e9 + 10 , 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	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	8 ms	3572 KB	Output is correct
5	Correct	11 ms	4188 KB	Output is correct
6	Correct	12 ms	4204 KB	Output is correct
7	Correct	11 ms	4188 KB	Output is correct
8	Correct	78 ms	30052 KB	Output is correct
9	Correct	160 ms	51540 KB	Output is correct
10	Correct	168 ms	56988 KB	Output is correct
11	Correct	177 ms	61264 KB	Output is correct
12	Correct	184 ms	63052 KB	Output is correct
13	Correct	177 ms	73640 KB	Output is correct
14	Correct	173 ms	74176 KB	Output is correct
15	Correct	251 ms	134700 KB	Output is correct
16	Correct	254 ms	135760 KB	Output is correct
17	Correct	164 ms	75344 KB	Output is correct
18	Correct	172 ms	75444 KB	Output is correct
19	Correct	266 ms	137312 KB	Output is correct
20	Correct	274 ms	137296 KB	Output is correct