oj.uz

Submission #474565

# Submission time Handle Problem Language Result Execution time Memory
474565 2021-09-19T04:12:31 Z cpp219 Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 48 ms 2956 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 456 KB Output is correct
7 Correct 5 ms 452 KB Output is correct
8 Correct 22 ms 1356 KB Output is correct
9 Correct 44 ms 2368 KB Output is correct
10 Correct 44 ms 2372 KB Output is correct
11 Correct 42 ms 2480 KB Output is correct
12 Correct 45 ms 2520 KB Output is correct
13 Correct 48 ms 2832 KB Output is correct
14 Correct 48 ms 2756 KB Output is correct
15 Correct 41 ms 2956 KB Output is correct
16 Correct 45 ms 2904 KB Output is correct
17 Correct 39 ms 2784 KB Output is correct
18 Correct 39 ms 2872 KB Output is correct
19 Correct 43 ms 2892 KB Output is correct
20 Correct 46 ms 2936 KB Output is correct