Submission #997247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
997247	2024-06-11T22:00:22 Z	JuanJL	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	90 ms	188252 KB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

struct Node{
	ll val, x, y;
	ll l,r;
	Node(ll v, ll x, ll y) : val(v), x(x), y(y) { l = r = -1; }
};

struct STree{
	ll n; 
	ll indice;
	vector<Node> st;
	vector<ll> lazy;
	STree(ll n) : n(n) , st(4*n+5,Node(0,-1,-1)), lazy(4*n+5,0) { indice=2; }
	
	void push_lazy(ll k, ll l, ll r){
		if(!lazy[k]) return;
		//cout<<k<<" ("<<l<<" "<<r<<") "<<'\n';
		ll mid = (l+r)/2;
		st[k].val=lazy[k]*(r-l);
		if(l+1!=r){
			if(st[k].l==-1){
				st[k].l=indice;
				indice++;
			}
			if(st[k].r==-1){
				st[k].r=indice;
				indice++;
			}
			lazy[st[k].l]=lazy[k];
			lazy[st[k].r]=lazy[k];
		}
		lazy[k]=0;
	}
	
	void upd(ll k, ll l, ll r, ll L, ll R, ll v){
		//cout<<k<<'\n';
		push_lazy(k,l,r);
		if(l>=R||r<=L) return;
		if(l>=L&&r<=R){
			//cout<<k<<" ("<<l<<" "<<r<<") "<<" ("<<L<<" "<<R<<") "<<'\n';
			lazy[k]=v;
			push_lazy(k,l,r);
			return;
		}
		ll mid = (l+r)/2;
		st[k].val=0;
		
		if(st[k].l==-1){
			st[k].l=indice;
			indice++;
		}
		
		//if(st[k].l!=-1){ 
			upd(st[k].l,l,mid,L,R,v);
			st[k].val+=st[st[k].l].val;
		//}
		
		if(st[k].r==-1){
			st[k].r=indice;
			indice++;
		}
		
		//if(st[k].r!=-1){
			upd(st[k].r,mid,r,L,R,v);
			st[k].val+=st[st[k].r].val;
		//}
	}
	
	ll query(ll k, ll l, ll r, ll L, ll R){
		//cout<<k<<" ("<<l<<" "<<r<<")"<<'\n';
		if(l>=R||r<=L) return 0;
		push_lazy(k,l,r);
		//cout<<k<<" ("<<l<<" "<<r<<") "<<" ("<<L<<" "<<R<<") "<<'\n';
		if(l>=L&&r<=R){  return st[k].val;}
		
		ll mid = (l+r)/2;
		ll res = 0;
		if(st[k].l!=-1){ 
			res+=query(st[k].l,l,mid,L,R);
		}
		if(st[k].r!=-1){
			res+=query(st[k].r,mid,r,L,R);
		}
		return res;
	}
	
	void upd(ll l, ll r, ll v){ upd(1,0,n,l,r,v); }
	ll query(ll l, ll r){ return query(1,0,n,l,r); }
};

int main(){
	ll m; cin>>m;
	ll t,c,pC; c=0;
	ll l,r;
	STree stree(1e6+5);
	
	while(m--){
		cin>>t>>l>>r;
		if(t==2){
			stree.upd(c+l,c+r+1,1);
		}else{
			//cout<<"QUERY\n";
			pC=stree.query(l+c,r+c+1);
			cout<<pC<<'\n';
			c=pC;
		}
	}
	return 0;
}

Compilation message

apple.cpp: In member function 'void STree::push_lazy(ll, ll, ll)':
apple.cpp:38:6: warning: unused variable 'mid' [-Wunused-variable]
   38 |   ll mid = (l+r)/2;
      |      ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	188240 KB	Output is correct
2	Correct	23 ms	188240 KB	Output is correct
3	Correct	23 ms	188240 KB	Output is correct
4	Correct	37 ms	188244 KB	Output is correct
5	Correct	38 ms	188244 KB	Output is correct
6	Correct	39 ms	188248 KB	Output is correct
7	Correct	40 ms	188252 KB	Output is correct
8	Incorrect	90 ms	188180 KB	Output isn't correct
9	Halted	0 ms	0 KB	-