oj.uz

Submission #872130

# Submission time Handle Problem Language Result Execution time Memory
872130 2023-11-12T11:00:51 Z willychan Food Court (JOI21_foodcourt) C++17
21 / 100
 468 ms 38316 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
//#include<bits/extc++.h>
//__gnu_pbds
struct SegTree{
	struct node{
		int Minn = 0;
		int SMinn = (1e18);
		int maxtag= -1;
		int addtag = 0;
		void add(int v){
			Minn+=v;
			if(SMinn<1e18) SMinn+=v;
			if(maxtag!=-1) maxtag+=v;
			addtag +=v;		
		}
		void chmax(int v){
			if(v<=Minn) return;
			//addtag = max(v,addtag);
			maxtag = max(maxtag,v);
			Minn = v;

		}
	};
	node merge(node a,node b){
		node re;
		re.Minn = min(a.Minn,b.Minn);
		if(a.Minn == b.Minn){
			re.SMinn = min(a.SMinn,b.SMinn);
		}else if(a.Minn<b.Minn){
			re.SMinn = min(a.SMinn,b.Minn);
		}else{
			re.SMinn = min(b.SMinn,a.Minn);
		}
		return re;
	}
	vector<node> arr;
	int n;
	void init(int _n){
		n = _n;
		arr.resize(4*n)	;
	}
	void push(int ind){
		if(arr[ind].addtag){
			if(2*ind<4*n) arr[2*ind].add(arr[ind].addtag);
			if(2*ind+1<4*n) arr[2*ind+1].add(arr[ind].addtag);
		}
		arr[ind].addtag=0;
		if(arr[ind].maxtag!=-1){
			if(2*ind<4*n) arr[2*ind].chmax(arr[ind].maxtag);
			if(2*ind+1<4*n) arr[2*ind+1].chmax(arr[ind].maxtag);
		}
		arr[ind].maxtag=-1;
	}
	void built(int ind,int L,int R){
		if(L==R) return;
		int M = (L+R)/2;
		built(2*ind,L,M);
		built(2*ind,M+1,R);
		arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
	}
	void Radd(int ind,int l,int r,int L,int R,int v){
		//cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
		push(ind);
		if(L==l && r==R){
			arr[ind].add(v);
			return;
		}
		int M = (L+R)/2;
		if(r<=M) Radd(2*ind,l,r,L,M,v);
		else if(l>M) Radd(2*ind+1,l,r,M+1,R,v);
		else{
			Radd(2*ind,l,M,L,M,v);
			Radd(2*ind+1,M+1,r,M+1,R,v);
		}
		arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
	}
	void Rchmax(int ind,int l,int r,int L,int R,int v){
		//cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
		push(ind);
		if(l==L && r==R && v<arr[ind].SMinn){
			assert(arr[ind].addtag==0);
			arr[ind].chmax(v);
			return;
		}
		int M = (L+R)/2;
		if(r<=M) Rchmax(2*ind,l,r,L,M,v);
		else if(l>M) Rchmax(2*ind+1,l,r,M+1,R,v);
		else{
			Rchmax(2*ind,l,M,L,M,v);
			Rchmax(2*ind+1,M+1,r,M+1,R,v);
		}
		arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
	}
	int query(int ind,int x,int L,int R){
		push(ind);
		if(L==R) return arr[ind].Minn;
		arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
		int M = (L+R)/2;
		if(x<=M) return query(2*ind,x,L,M);
		else return query(2*ind+1,x,M+1,R);
	}
} seg;



signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m,q;cin>>n>>m>>q;
	seg.init(n);
	seg.built(1,1,n);
	while(q--){
		int t;cin>>t;
		if(t==1){
			int l,r,c,k;cin>>l>>r>>c>>k;
			seg.Radd(1,l,r,1,n,k);
		}
		if(t==2){
			int l,r,k;cin>>l>>r>>k;
			seg.Radd(1,l,r,1,n,-k);
			seg.Rchmax(1,l,r,1,n,0);
		}
		if(t==3){
			int a,b;cin>>a>>b;	
			int g = seg.query(1,a,1,n);
//			cout<<g<<"\n";
			cout<<(g>=b)<<"\n";
		}
	}

	return 0;
}

// segment tree beats + parellal binary search

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 28572 KB Output is correct
2 Correct 337 ms 29128 KB Output is correct
3 Correct 390 ms 37784 KB Output is correct
4 Correct 249 ms 35872 KB Output is correct
5 Correct 229 ms 28500 KB Output is correct
6 Correct 333 ms 38012 KB Output is correct
7 Correct 56 ms 4508 KB Output is correct
8 Correct 60 ms 4436 KB Output is correct
9 Correct 247 ms 38316 KB Output is correct
10 Correct 256 ms 38284 KB Output is correct
11 Correct 356 ms 37764 KB Output is correct
12 Correct 348 ms 37968 KB Output is correct
13 Correct 347 ms 37712 KB Output is correct
14 Correct 402 ms 37968 KB Output is correct
15 Correct 451 ms 37772 KB Output is correct
16 Correct 452 ms 37972 KB Output is correct
17 Correct 444 ms 37876 KB Output is correct
18 Correct 400 ms 37972 KB Output is correct
19 Correct 405 ms 37764 KB Output is correct
20 Correct 409 ms 37712 KB Output is correct
21 Correct 468 ms 37888 KB Output is correct
22 Correct 446 ms 37760 KB Output is correct
23 Correct 409 ms 38036 KB Output is correct
24 Correct 426 ms 37748 KB Output is correct
25 Correct 299 ms 30132 KB Output is correct
26 Correct 291 ms 37456 KB Output is correct
27 Correct 299 ms 37564 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 8356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -