Submission #548635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548635	2022-04-14T04:39:41 Z	ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	596 ms	262144 KB

apple

#include<bits/stdc++.h>
using namespace std;
struct node{
    node* child[2];
    bool lazy;
    int tl,tr,sum;
    node(int l, int r){
	lazy = 0;
	sum = 0;
	tl = l;
	tr = r;
	child[0] = child[1] = NULL;
    };
    void add(){
	int tm = (tl + tr)/2;
	if(!child[0])
	   child[0] = new node(tl, tm);
	if(!child[1])
	   child[1] = new node(tm + 1, tr);
    }
    int siz(){
	return tr - tl + 1;
    }
};
node *root = new node(1, 1e9);
void push(node* v){
    if(v->lazy == 0 || v->tl == v->tr)return;
    int tm = (v->tl + v->tr)/2;
    v->add();
    v->child[0]->lazy = 1;
    v->child[1]->lazy = 1;
    v->lazy= 0;
    v->child[0]->sum = v->child[0]->siz();
    v->child[1]->sum = v->child[1]->siz();
}
void update(int l,int r,node *v){
    push(v);
    if(l > r || !v)
	return;
    else if(l <= v->tl && r >= v->tr){
	int siz = v->tr - v->tl + 1;
	v->lazy = 1;
	v->sum = siz;
    }
    else{
	int tm = (v->tl + v->tr)/2;
	v->add();
	update(l, min(tm,r), v->child[0]);
	update(max(l,tm + 1), r, v->child[1]);
	v->sum = v->child[0]->sum + v->child[1]->sum;
    }
}
int query(int l,int r,node* v){
    push(v);
    if(l > r || !v)
	return 0;
    else if(l <= v->tl && r >= v->tr){
	return v->sum;
    }
    else{
	int tm = (v->tl + v->tr)/2;
	v->add();
	return query(l, min(tm, r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    }
}
int main(){
    int q;cin >> q;
    int c = 0;
    while(q--){
	int d, x, y;cin >> d >> x >> y;
	x += c;y+=c;
	if(d == 1){
	    cout << (c = query(x,y,root)) << "\n";
	}
	else{
	    update(x,y,root);
	}
    }
}

Compilation message

apple.cpp: In function 'void push(node*)':
apple.cpp:28:9: warning: unused variable 'tm' [-Wunused-variable]
   28 |     int tm = (v->tl + v->tr)/2;
      |         ^~

Subtask #1

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	1 ms	212 KB	Output is correct
4	Correct	27 ms	8544 KB	Output is correct
5	Correct	41 ms	10324 KB	Output is correct
6	Correct	39 ms	9872 KB	Output is correct
7	Correct	38 ms	10356 KB	Output is correct
8	Correct	261 ms	77004 KB	Output is correct
9	Correct	523 ms	130872 KB	Output is correct
10	Correct	528 ms	146776 KB	Output is correct
11	Correct	579 ms	159252 KB	Output is correct
12	Correct	595 ms	164964 KB	Output is correct
13	Correct	553 ms	204992 KB	Output is correct
14	Correct	578 ms	206992 KB	Output is correct
15	Runtime error	596 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-