Submission #524872

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524872	2022-02-10T07:39:09 Z	Aktan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	404 ms	207768 KB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17;
const int inf = 1e9;
struct node {
	int sum;
	int lz;
	node *c[2];
	node(int x=0,int l=-1) : sum(x), lz(l){
		c[0] = c[1] = NULL;
	}
};
node operator + (node a,node b){
	node c(a.sum+b.sum);
	return c;
}
const int N=1e6;
void push(node *p,int len){
	if (p->lz == -1) return;
	p->sum=len*p->lz;
	if(p->c[0] != NULL){
		p->c[0]->lz = p->c[1]->lz = p->lz;
	}
//	p->lz=-1;
}
void update(node *p,int l,int r,int x,int y,int v){
	push(p,r-l+1);
	if(x>r || y<l){
		return;
	}
	if(x<=l && y>=r){
		p->lz = v;
		push(p,r-l+1);
		return;
	}
	if (p->c[0] == NULL) p->c[0] = new node();
	if (p->c[1] == NULL) p->c[1] = new node();
	push(p,r-l+1);
	int m=(l+r)/2;
	update(p->c[0],l,m,x,y,v);
	update(p->c[1],m+1,r,x,y,v);
	p->sum = p->c[0]->sum + p->c[1]->sum;
}
int query(node *p,int l,int r,int x,int y){
	push(p,r-l+1);
	if(x>r || y<l){
		return 0;
	}
	if(x<=l && y>=r){
		return p->sum;
	}
	if (p->c[0] == NULL) p->c[0] = new node();
	if (p->c[1] == NULL) p->c[1] = new node();
	push(p,r-l+1);
	int m=(r+l)/2;
	return query(p->c[0],l,m,x,y) + query(p->c[1],m+1,r,x,y);
}
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,q;
	cin >> q;
	int c=0;
	node *root = new node();
	while(q--){
		int type;
		cin >> type;
		if(type==2){
			int l,r,v;
			cin >> l >> r;
			update(root,1,inf,l+c,r+c,1);
		}
		else{
			int l,r;
			cin >> l >> r;
			c=query(root,1,inf,l+c,r+c);
			cout << c << "\n";
		}
	}
}

Compilation message

apple.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main(){
      | ^~~~
apple.cpp: In function 'int main()':
apple.cpp:75:12: warning: unused variable 'v' [-Wunused-variable]
   75 |    int l,r,v;
      |            ^
apple.cpp:67:6: warning: unused variable 'n' [-Wunused-variable]
   67 |  int n,q;
      |      ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	16 ms	4828 KB	Output is correct
5	Correct	15 ms	5828 KB	Output is correct
6	Correct	15 ms	5692 KB	Output is correct
7	Correct	15 ms	5792 KB	Output is correct
8	Correct	122 ms	43720 KB	Output is correct
9	Correct	277 ms	75528 KB	Output is correct
10	Correct	256 ms	83644 KB	Output is correct
11	Correct	269 ms	89768 KB	Output is correct
12	Correct	266 ms	92680 KB	Output is correct
13	Correct	242 ms	107844 KB	Output is correct
14	Correct	251 ms	109224 KB	Output is correct
15	Correct	387 ms	201776 KB	Output is correct
16	Correct	397 ms	203332 KB	Output is correct
17	Correct	253 ms	114756 KB	Output is correct
18	Correct	248 ms	114756 KB	Output is correct
19	Correct	389 ms	207768 KB	Output is correct
20	Correct	404 ms	207680 KB	Output is correct