Submission #474565

#	Time	Username	Problem	Language	Result	Execution time	Memory
474565		cpp219	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	48 ms	2956 KiB

apple

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;

ll Q,type,l,r,C,sz = 1e9;

/// Beware of tricky corner case

struct node{
    node *link[2]; ll sum = 0;
    void upd(ll l,ll r,ll u,ll v){
        if (sum == r - l + 1) return;
        if (u <= l&&r <= v){
            sum = r - l + 1; return;
        }
        ll mid = (l + r)/2;
        if (u <= mid){
            if (!link[0]) link[0] = new node();
            link[0] -> upd(l,mid,u,v);
        }
        if (v > mid){
            if (!link[1]) link[1] = new node();
            link[1] -> upd(mid + 1,r,u,v);
        }
        sum = (link[0] ? link[0] -> sum : 0) + (link[1] ? link[1] -> sum : 0);
    }
    ll Get(ll l,ll r,ll u,ll v){
        if (u <= l && r <= v) return sum;
        if (sum == r - l + 1) return min(r,v) - max(l,u) + 1;
        ll mid = (l + r)/2,ans = 0;
        if (link[0] && u <= mid) ans += link[0] -> Get(l,mid,u,v);
        if (link[1] && v > mid) ans += link[1] -> Get(mid + 1,r,u,v);
        return ans;
    }
}Tree;

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>Q;
    while(Q--){
        cin>>type>>l>>r;
        if (type == 1) C = Tree.Get(1,sz,l + C,r + C),cout<<C<<"\n";
        else Tree.upd(1,sz,l + C,r + C);
    }
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100