Submission #1098681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098681		theSkeleton	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	317 ms	260568 KiB

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 (stderr)

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 / 100