Submission #672513

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672513	2022-12-16T11:46:18 Z	bLIC	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	370 ms	202756 KB

apple

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 998244353;
const ll INFLL = 1e18;
const int INF = 1e9;
const int maxN = 2e5+6;
const int maxK = 10;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}


#define gbit(x, i) (((1<<i)&(x))!=0)


struct Node{
    int lx, rx;
    ll sm;
    bool lz;
    Node *lt, *rt;
    Node(ll x, ll l, ll r):sm(x), lx(l), rx(r), lz(0), lt(NULL), rt(NULL){}
    Node(ll l, ll r): Node(0, l, r){}
    void pushdown(){
        if (lz==0) return;
        ll mid = (lx+rx)/2;
        lt->sm = mid-lx;
        rt->sm = rx-mid;
        lt->lz = 1;
        rt->lz = 1;
        lz = 0;
    }
    void pushup(){
        sm = lt->sm+rt->sm;
    }
    void upd(ll l, ll r, ll val){
        if (l<=lx && rx<=r) {
            sm = (rx-lx);
            lz = 1;
            return;
        }
        if (l>=rx || r<=lx) return;
        ll mid = (lx+rx)/2;
        if (!lt) lt = new Node(lx, mid);
        if (!rt) rt = new Node(mid, rx);
        pushdown();
        lt->upd(l, r, val);
        rt->upd(l, r, val);
        pushup();
    }
    ll query(int l, int r){
        if (l<=lx && rx<=r) return sm;
        if (l>=rx || r<=lx) return 0;
        ll mid = (lx+rx)/2;
        if (!lt) lt = new Node(lx, mid);
        if (!rt) rt = new Node(mid, rx);
        pushdown();
        ll ans = lt->query(l, r) + rt->query(l, r);
        pushup();
        return ans;
    }
};

template <class T>
istream& operator>>(istream& in, vector<T>& v){
    for (T& x:v) in>>x;
    return in;
}

const ll MAXN = 1ll<<30;
void solve(){
    int n;cin>>n;
    int c = 0;

    Node* root = new Node(0, MAXN);
    while(n--){
        int t;cin>>t;
        int x, y;cin>>x>>y;
        if (t==1){
            c = root->query(x-1+c, y+c);
            cout<<c<<"\n";
        }
        else {
            root->upd(x-1+c, y+c, 1);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
// #define _DEBUG
#ifdef _DEBUG
	freopen("haybales.in", "r", stdin);
	freopen("haybales.out", "w", stdout);
	int tt = clock();
#endif
    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        // cout<<'\n';
    }
#ifdef _DEBUG
    cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
    tt = clock();
#endif
}

Compilation message

apple.cpp: In constructor 'Node::Node(ll, ll, ll)':
apple.cpp:45:8: warning: 'Node::sm' will be initialized after [-Wreorder]
   45 |     ll sm;
      |        ^~
apple.cpp:44:9: warning:   'int Node::lx' [-Wreorder]
   44 |     int lx, rx;
      |         ^~
apple.cpp:48:5: warning:   when initialized here [-Wreorder]
   48 |     Node(ll x, ll l, ll r):sm(x), lx(l), rx(r), lz(0), lt(NULL), rt(NULL){}
      |     ^~~~
apple.cpp: In function 'int main()':
apple.cpp:126:14: warning: unused variable 'i' [-Wunused-variable]
  126 |     int t=1, i = 1;
      |              ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	11 ms	4704 KB	Output is correct
5	Correct	13 ms	5560 KB	Output is correct
6	Correct	13 ms	5452 KB	Output is correct
7	Correct	16 ms	5592 KB	Output is correct
8	Correct	108 ms	41908 KB	Output is correct
9	Correct	226 ms	74908 KB	Output is correct
10	Correct	238 ms	80160 KB	Output is correct
11	Correct	240 ms	86352 KB	Output is correct
12	Correct	236 ms	88952 KB	Output is correct
13	Correct	219 ms	105368 KB	Output is correct
14	Correct	222 ms	106396 KB	Output is correct
15	Correct	366 ms	194436 KB	Output is correct
16	Correct	353 ms	196912 KB	Output is correct
17	Correct	221 ms	110120 KB	Output is correct
18	Correct	230 ms	110052 KB	Output is correct
19	Correct	370 ms	202596 KB	Output is correct
20	Correct	362 ms	202756 KB	Output is correct