Submission #548637

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548637	2022-04-14T04:44:58 Z	ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	530 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();
	if(l > tm){
	    update(l, r, v->child[1]);
	}
	else if(r <= tm){
	    update(l,r, v->child[0]);
	}
	else{
	    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]);
	if(l > tm){
	    return query(l, r, v->child[1]);
	}
	else if(r <= tm){
	    return query(l,r, v->child[0]);
	}
	else{
	    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	25 ms	7724 KB	Output is correct
5	Correct	37 ms	9240 KB	Output is correct
6	Correct	34 ms	8924 KB	Output is correct
7	Correct	31 ms	9300 KB	Output is correct
8	Correct	229 ms	69452 KB	Output is correct
9	Correct	461 ms	118500 KB	Output is correct
10	Correct	476 ms	132532 KB	Output is correct
11	Correct	505 ms	143344 KB	Output is correct
12	Correct	496 ms	148172 KB	Output is correct
13	Correct	485 ms	181760 KB	Output is correct
14	Correct	470 ms	183060 KB	Output is correct
15	Runtime error	530 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-