Submission #1098681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098681	2024-10-09T16:59:35 Z	theSkeleton	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	317 ms	260568 KB

apple

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const ll en = 1e9;
const ll mx = 1e7+5;
ll lzy[mx],seg[mx],c1[mx],c2[mx],cnt=1;
void make_c(int l,int r,int u){
    if(l==r) return;
    c1[u]=++cnt,c2[u]=++cnt;
}
void push(int l,int r,int u){
    if(l==r)
        seg[u]=max(seg[u],lzy[u]);
    else
        if(lzy[u]==1){
            seg[u]=r-l+1;
            lzy[c1[u]]=1,
            lzy[c2[u]]=1;
        }
    lzy[u]=0;
}
void upd(ll L,ll R,ll u=1,ll l=1,ll r=en){
    if(c1[u]==0||c2[u]==0)
        make_c(l,r,u);
    push(l,r,u);
    if(L<=l&&r<=R)
        lzy[u]=1,
        push(l,r,u);
    else if(!(R<l||r<L)){
        push(l,r,u);
        int m=(l+r)/2;
        upd(L,R,c1[u],l,m);
        upd(L,R,c2[u],m+1,r);
        seg[u]=seg[c1[u]]+seg[c2[u]];
    }
}
ll red(ll L,ll R,ll u=1,ll l=1,ll r=en){
    if(c1[u]==0||c2[u]==0)
        make_c(l,r,u);
    push(l,r,u);
    if (L<=l&&r<=R)
        return seg[u];
    else if(R<l||r<L)
        return 0;
    else{
        int m=(l+r)/2;
        return red(L,R,c1[u],l,m)
        +red(L,R,c2[u],m+1,r);
    }
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll c=0,m;cin>>m;
    for(ll d,l,r;m--;){
        cin>>d>>l>>r;
        l+=c,r+=c;
        if(d==1){
            ll t=red(l,r);
            cout<<t<<endl;
            c=t;
        }
        if(d==2)
            upd(l,r);

    }
    return 0;
}

Compilation message

apple.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("O3")
      | 
apple.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	5980 KB	Output is correct
5	Correct	13 ms	7004 KB	Output is correct
6	Correct	13 ms	6744 KB	Output is correct
7	Correct	14 ms	7004 KB	Output is correct
8	Correct	95 ms	51596 KB	Output is correct
9	Correct	211 ms	87380 KB	Output is correct
10	Correct	209 ms	98132 KB	Output is correct
11	Correct	211 ms	106580 KB	Output is correct
12	Correct	200 ms	110164 KB	Output is correct
13	Correct	176 ms	136916 KB	Output is correct
14	Correct	178 ms	138320 KB	Output is correct
15	Correct	278 ms	252604 KB	Output is correct
16	Correct	277 ms	254428 KB	Output is correct
17	Correct	180 ms	143444 KB	Output is correct
18	Correct	185 ms	143440 KB	Output is correct
19	Correct	298 ms	260372 KB	Output is correct
20	Correct	317 ms	260568 KB	Output is correct