Submission #479062

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479062	2021-10-09T19:31:00 Z	MohammadAghil	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	414 ms	207176 KB

apple

#include <bits/stdc++.h> 
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 998244353, maxn = 2e5 + 1, maxk = 30, inf = 1e9 + 5;

struct Node{
    int lx, rx, sum = 0, lazy = -1;
    Node *lc = 0, *rc = 0;
    Node(int lx, int rx): lx(lx), rx(rx){}
    void push(){
        sum = rx - lx;
        lazy = 1;
    }
    void shift(){
        int mid = (lx + rx) >> 1;
        if(!lc) lc = new Node(lx, mid);
        if(!rc) rc = new Node(mid, rx);
        if(lazy != -1){
            lc->push();
            rc->push();
            lazy = -1;
        }
    }
    int query(int l, int r){
        if(l <= lx && r >= rx) return sum;
        if(l >= rx || r <= lx) return 0;
        shift();
        int mid = (lx + rx) >> 1;
        return lc->query(l, r) + rc->query(l, r);
    }
    void upd(int l, int r){
        if(l <= lx && r >= rx) return push();
        if(l >= rx || r <= lx) return;
        shift();
        int mid = (lx + rx) >> 1;
        lc->upd(l, r), rc->upd(l, r);
        sum = lc->sum + rc->sum;
    }
};

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    Node seg(0, inf);
    int q; cin >> q;
    int c = 0;
    while(q--){
        int t, l, r; cin >> t >> l >> r;
        if(t == 1) cout << (c = seg.query(c + l - 1,c + r)) << '\n';
        else seg.upd(c + l - 1,c + r);
    }
    return 0;
}

Compilation message

apple.cpp: In member function 'int Node::query(int, int)':
apple.cpp:37:13: warning: unused variable 'mid' [-Wunused-variable]
   37 |         int mid = (lx + rx) >> 1;
      |             ^~~
apple.cpp: In member function 'void Node::upd(int, int)':
apple.cpp:44:13: warning: unused variable 'mid' [-Wunused-variable]
   44 |         int mid = (lx + rx) >> 1;
      |             ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	13 ms	4996 KB	Output is correct
5	Correct	15 ms	6008 KB	Output is correct
6	Correct	15 ms	5836 KB	Output is correct
7	Correct	16 ms	5964 KB	Output is correct
8	Correct	122 ms	44496 KB	Output is correct
9	Correct	252 ms	77012 KB	Output is correct
10	Correct	268 ms	85180 KB	Output is correct
11	Correct	279 ms	91432 KB	Output is correct
12	Correct	283 ms	94140 KB	Output is correct
13	Correct	244 ms	109380 KB	Output is correct
14	Correct	252 ms	110472 KB	Output is correct
15	Correct	414 ms	201380 KB	Output is correct
16	Correct	405 ms	202564 KB	Output is correct
17	Correct	254 ms	114328 KB	Output is correct
18	Correct	261 ms	114308 KB	Output is correct
19	Correct	412 ms	207176 KB	Output is correct
20	Correct	395 ms	207048 KB	Output is correct