Submission #672511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
672511	2022-12-16T11:41:11 Z	bLIC	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	418 ms	262144 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{
    ll lx, rx;
    ll sm, 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<<31;
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, lz;
      |        ^~
apple.cpp:44:8: warning:   'll Node::lx' [-Wreorder]
   44 |     ll lx, rx;
      |        ^~
apple.cpp:47:5: warning:   when initialized here [-Wreorder]
   47 |     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:125:14: warning: unused variable 'i' [-Wunused-variable]
  125 |     int t=1, i = 1;
      |              ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	6224 KB	Output is correct
5	Correct	16 ms	7504 KB	Output is correct
6	Correct	16 ms	7340 KB	Output is correct
7	Correct	22 ms	7524 KB	Output is correct
8	Correct	122 ms	56512 KB	Output is correct
9	Correct	258 ms	101472 KB	Output is correct
10	Correct	254 ms	108396 KB	Output is correct
11	Correct	263 ms	116608 KB	Output is correct
12	Correct	289 ms	120156 KB	Output is correct
13	Correct	238 ms	142396 KB	Output is correct
14	Correct	244 ms	143676 KB	Output is correct
15	Correct	415 ms	261204 KB	Output is correct
16	Correct	418 ms	262144 KB	Output is correct
17	Correct	251 ms	148728 KB	Output is correct
18	Correct	247 ms	148608 KB	Output is correct
19	Runtime error	413 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-