Submission #991607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991607	2024-06-02T15:44:45 Z	yusuf12360	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	285 ms	206928 KB

apple

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi> 
#define pb push_back
#define fi first
#define se second
#define TII tuple<int, int, int>
#define ts to_string
#pragma gcc optimize("O3");
using namespace std;
const int INF=1e9;
struct node{
    int l, r, sum=0, lazy=0;
    node *left=nullptr, *right=nullptr;
    node(int l, int r) : l(l), r(r) {}

    void extend() {
        if(l==r) return;
        int mid=l+r>>1;
        if(!left) left=new node(l, mid);
        if(!right) right=new node(mid+1, r);
    }
    void push() {
        if(l==r) return;
        extend();
        if(lazy) {
            left->lazy=1;
            left->sum=left->r-left->l+1;
            right->lazy=1;
            right->sum=right->r-right->l+1;
            lazy=0;
        }
    }
    void update(int ql, int qr) {
        if(max(l, ql)>min(r, qr)) return;
        if(ql<=l && r<=qr) {lazy=1; sum=r-l+1; return;}
        push();
        left->update(ql, qr);
        right->update(ql, qr);
        sum=left->sum+right->sum;
    }
    int get(int ql, int qr) {
        if(max(l, ql)>min(r, qr)) return 0;
        if(ql<=l && r<=qr) return sum;
        push();
        return left->get(ql, qr)+right->get(ql, qr);
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, c=0; cin >> m;
    node *root = new node(1, INF);
    while(m--) {
        int type, ql, qr;
        cin >> type >> ql >> qr;
        if(type==1) c=root->get(ql+c, qr+c), cout << c << '\n';
        else root->update(ql+c, qr+c);
    }
    return 0;
}

Compilation message

apple.cpp:11: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
   11 | #pragma gcc optimize("O3");
      | 
apple.cpp: In member function 'void node::extend()':
apple.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	4956 KB	Output is correct
5	Correct	10 ms	5872 KB	Output is correct
6	Correct	10 ms	5720 KB	Output is correct
7	Correct	10 ms	5980 KB	Output is correct
8	Correct	82 ms	43856 KB	Output is correct
9	Correct	172 ms	75860 KB	Output is correct
10	Correct	191 ms	83792 KB	Output is correct
11	Correct	180 ms	89940 KB	Output is correct
12	Correct	188 ms	92796 KB	Output is correct
13	Correct	163 ms	107856 KB	Output is correct
14	Correct	162 ms	108892 KB	Output is correct
15	Correct	272 ms	201044 KB	Output is correct
16	Correct	269 ms	202404 KB	Output is correct
17	Correct	171 ms	114072 KB	Output is correct
18	Correct	164 ms	114000 KB	Output is correct
19	Correct	271 ms	206928 KB	Output is correct
20	Correct	285 ms	206928 KB	Output is correct