Submission #524872

#	Time	Username	Problem	Language	Result	Execution time	Memory
524872		Aktan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	404 ms	207768 KiB

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 (stderr)

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 / 100