Submission #672513

#	Time	Username	Problem	Language	Result	Execution time	Memory
672513		bLIC	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	370 ms	202756 KiB

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

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