Submission #524870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524870	2022-02-10T07:35:40 Z	Aktan	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	383 ms	262148 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){
	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);
	if(x>r || y<l){
		return;
	}
	if(x<=l && y>=r){
		p->lz = v;
		push(p,r-l+1);
		return;
	}
	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){
	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);
	if(x>r || y<l){
		return 0;
	}
	if(x<=l && y>=r){
		return p->sum;
	}
	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 a[n+1];
	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:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main(){
      | ^~~~
apple.cpp: In function 'int main()':
apple.cpp:74:12: warning: unused variable 'v' [-Wunused-variable]
   74 |    int l,r,v;
      |            ^
apple.cpp:67:6: warning: unused variable 'a' [-Wunused-variable]
   67 |  int a[n+1];
      |      ^

Subtask #1

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	0 ms	204 KB	Output is correct
4	Correct	15 ms	9356 KB	Output is correct
5	Correct	20 ms	11404 KB	Output is correct
6	Correct	19 ms	11012 KB	Output is correct
7	Correct	19 ms	11312 KB	Output is correct
8	Correct	166 ms	86884 KB	Output is correct
9	Correct	342 ms	152260 KB	Output is correct
10	Correct	353 ms	168436 KB	Output is correct
11	Correct	365 ms	180816 KB	Output is correct
12	Correct	383 ms	186560 KB	Output is correct
13	Correct	332 ms	217156 KB	Output is correct
14	Correct	332 ms	219224 KB	Output is correct
15	Runtime error	350 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-