Submission #705472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
705472	2023-03-04T13:00:06 Z	hoangnghiep	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	440 ms	262144 KB

apple

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=5e5;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e9;
int n,m,x,y,k,t,e,q,d;
int dx[8]={1,-1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,1,-1,1,-1};
char c;
string s;
int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5];
struct node{
   int sum,lazy,tl,tr,l,r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};
node segtree[5000000];
int cnt=1;
void push(int node){
	if(segtree[node].lazy){
		segtree[node].sum=segtree[node].tr - segtree[node].tl+1;
		int mid=(segtree[node].tl+segtree[node].tr)>>1;
		if(segtree[node].l==-1){
			segtree[node].l=cnt++;
			segtree[segtree[node].l].tl=segtree[node].tl;
			segtree[segtree[node].l].tr=mid;
		}
			if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy=segtree[segtree[node].r].lazy=1;
		segtree[node].lazy=0;
	}
}
void update(int node,int l,int r){
	push(node);
	if(l>segtree[node].tr || r<segtree[node].tl){
		return;
	}
	 if(l<=segtree[node].tl && segtree[node].tr<=r){
		segtree[node].lazy=1;
		push(node);
		return;
	}
	int mid=(segtree[node].tl + segtree[node].tr)>>1;
	if(segtree[node].l==-1){
			segtree[node].l=cnt++;
			segtree[segtree[node].l].tl=segtree[node].tl;
			segtree[segtree[node].l].tr=mid;
		}
	if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
	update(segtree[node].l,l,r);
    update(segtree[node].r,l,r);
    segtree[node].sum=segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
}
int query(int node, int l, int r) {
	if(l>segtree[node].tr || r<segtree[node].tl){
		return 0;
	}
	push(node);
	 if(l<=segtree[node].tl && segtree[node].tr<=r){
	 	return segtree[node].sum;
	}
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
			return query(segtree[node].l, l, r) +
			       query(segtree[node].r, l, r);
}
bool notprime[LIM+5];
map<int,int> mp;
char grid[100+5][100+5];
int power(int a,int b){
   if(b==0) return 1;
    int t=power(a,b/2);
    t = t * t %mod;
    if(b%2==1) t = t * a %mod;
    return t;
}
bool check(int x,int y){
    if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='T'){
   return false;
     }
    return true;
}
class DSU{
	int *parent;
	int *rank;
	int *tot;
	public:
	DSU(int n){
		rank=new int[n+5];
		parent=new int[n+5];
		tot=new int [n+5];
		for(int i=0;i<n+5;i++){
			parent[i]=i;
			rank[i]=0;
			tot[i]=1;
		}
	}
	int find(int i){
		if(parent[i]==i){
			return i;
		}
		return parent[i]=find(parent[i]);
	}
	void unite(int u,int v){
		int i=find(u);
		int j=find(v);
		if(i!=j){
			if(rank[i]>rank[j]){
				parent[j]=i;
				tot[i]+=tot[j];
			}
			else if(rank[i]<rank[j]){
				parent[i]=j;
				tot[j]+=tot[i];
			}
			else{
				parent[j]=i;
				rank[i]++;
				tot[i]+=tot[j];
			}
		}
	}
	int total(int u){
	   return tot[u];
	}
};
void precal(int n){
	factorial[0]=1;
	inv_fact[0]=1;
    for (int i = 1; i <n; ++i)
	{
		factorial[i] = factorial[i - 1] * i % mod;
		inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod;
	}
}
int choose(int n,int k){
	if(k<0 || k>n) return 0;
	return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod;
}
void Sieve(){
	notprime[0]=notprime[1]=true;
    for(int i=2;i<LIM+5;++i){
    	if(notprime[i]==false){
    	for(int j=i*i;j<LIM+5;j+=i){
    		notprime[j]=true;
		}
    }
	}
}
void solve(){
//Sieve();
//   precal();
    cin>>m;
    segtree[0].sum=0;
    segtree[0].lazy=0;
    segtree[0].tl=1;
    segtree[0].tr=1e9;
    int c=0;
    while(m--){
    	cin>>d>>x>>y;
    	if(d==1){
    		c=query(0,x+c,y+c);
    		cout<<c<<endl;
		}
		else{
			update(0,x+c,y+c);
		}
	}
}
signed main(){
  // freopen(".inp","r",stdin);
  // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int test;
	test=1;
	#ifdef multipletest
	cin>>test;
	#endif
	while(test--){
        solve();
        #ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	    #endif
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	235084 KB	Output is correct
2	Correct	87 ms	235128 KB	Output is correct
3	Correct	90 ms	235072 KB	Output is correct
4	Correct	110 ms	235276 KB	Output is correct
5	Correct	124 ms	235296 KB	Output is correct
6	Correct	106 ms	235212 KB	Output is correct
7	Correct	109 ms	235344 KB	Output is correct
8	Correct	240 ms	235988 KB	Output is correct
9	Correct	401 ms	237200 KB	Output is correct
10	Correct	425 ms	237272 KB	Output is correct
11	Correct	413 ms	237320 KB	Output is correct
12	Correct	440 ms	237256 KB	Output is correct
13	Correct	385 ms	237708 KB	Output is correct
14	Correct	366 ms	237608 KB	Output is correct
15	Runtime error	415 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-