oj.uz

Submission #540510

# Submission time Handle Problem Language Result Execution time Memory
540510 2022-03-20T15:43:50 Z alvingogo Food Court (JOI21_foodcourt) C++14
13 / 100
 836 ms 92588 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
#define int long long
using namespace std;
 
typedef pair<int,int> pii;
struct qu{
	int t;
	int l,r,c,k;
};
struct qu2{
	int t,p,k;
	int id;
};
bool cmp(qu2 a,qu2 b){
	if(a.p!=b.p){
		return a.p<b.p;
	}
	return a.t<b.t;
}
vector<qu> vq;
struct DS{
	struct no{
		vector<int> tag;
		int cnt=0;
	};
	vector<no> st;
	vector<int> kk;
	void init(int n){
		st.resize(4*n);
		kk.resize(n);
	}
	void upd(int v,int x){
		while(st[v].tag.size()){
			int y=st[v].tag.back();
			if(y<0 && x>0){
				break;
			}
			if(y>0 && x<0){
				st[v].cnt+=min(abs(y),abs(x));
				x+=y;
			}
			else{
				x+=y;
			}
			st[v].tag.pop_back();
		}
		if(x!=0){
			st[v].tag.push_back(x);
		}
	}
	void pudo(int v){
		st[2*v+1].cnt+=st[v].cnt;
		st[2*v+2].cnt+=st[v].cnt;
		for(auto y:st[v].tag){
			upd(2*v+1,y);
			upd(2*v+2,y);
		}
		st[v].cnt=0;
		st[v].tag.clear();
	}
	void update(int v,int L,int R,int l,int r,int k){
		if(l==L && r==R){
			upd(v,k);
			return;
		}
		pudo(v);
		int m=(L+R)/2;
		if(r<=m){
			update(2*v+1,L,m,l,r,k);
		}
		else if(l>m){
			update(2*v+2,m+1,R,l,r,k);
		}
		else{
			update(2*v+1,L,m,l,m,k);
			update(2*v+2,m+1,R,m+1,r,k);
		}
	}
	int query(int v,int L,int R,int pos){
		if(L==R){
			for(auto h:st[v].tag){
				if(h<0 && kk[L]>0){
					st[v].cnt+=min(abs(h),abs(kk[L]));
				}
				kk[L]+=h;
				kk[L]=max(kk[L],0ll);
			}
			st[v].tag.clear();
			return st[v].cnt;
		}
		pudo(v);
		int m=(L+R)/2;
		if(pos<=m){
			return query(2*v+1,L,m,pos);
		}
		else{
			return query(2*v+2,m+1,R,pos);
		}
	}
	void pre(int n){
		for(auto &h:vq){
			if(h.t==1){
				update(0,0,n-1,h.l,h.r,h.k);
			}
			else if(h.t==2){
				update(0,0,n-1,h.l,h.r,-h.k);
			}
			else{
				h.k+=query(0,0,n-1,h.l);
			}
		}
	}
};
struct Q13{
	vector<int> st;
	vector<qu2> g;
	void update(int v,int L,int R,int pos,int k){
		if(L==R){
			st[v]+=k;
			return;
		}
		int m=(L+R)/2;
		if(pos<=m){
			update(2*v+1,L,m,pos,k);
		}
		else{
			update(2*v+2,m+1,R,pos,k);
		}
		st[v]=st[2*v+1]+st[2*v+2];
	}
	int query(int v,int L,int R,int k){
		if(L==R){
			return L;
		}
		int m=(L+R)/2;
		if(st[2*v+1]>=k){
			return query(2*v+1,L,m,k);
		}
		else{
			return query(2*v+2,m+1,R,k-st[2*v+1]);
		}
	}
	void solve(int n,int q){
		vector<int> ans(q,-1);
		vector<int> co(q,-1);
		st.resize(4*q);
		for(int i=0;i<q;i++){
			if(vq[i].t==1){
				g.push_back({1,vq[i].l,vq[i].k,i});
				g.push_back({1,vq[i].r+1,-vq[i].k,i});
				co[i]=vq[i].c;
			}
			else if(vq[i].t==3){
				g.push_back({3,vq[i].l,vq[i].k,i});
			}
		}
		sort(g.begin(),g.end(),cmp);
		for(auto h:g){
			if(h.p>=n){
				break;
			}
			if(h.t==1){
				update(0,0,q-1,h.id,h.k);
			}
			else{
				int u=query(0,0,q-1,h.k);
				if(u>h.id){
					ans[h.id]=0;
				}
				else{
					ans[h.id]=co[u];
				}
			}
		}
		for(auto y:ans){
			if(y>=0){
				cout << y << "\n";
			}
		}
	}
};
signed main(){
	AquA;
	int n,m,q;
	cin >> n >> m >> q;
	vq.resize(q);
	for(int i=0;i<q;i++){
		cin >> vq[i].t;
		if(vq[i].t==1){
			cin >> vq[i].l >> vq[i].r >> vq[i].c >> vq[i].k;
			vq[i].l--;
			vq[i].r--;
		}
		else if(vq[i].t==2){
			cin >> vq[i].l >> vq[i].r >> vq[i].k;
			vq[i].l--;
			vq[i].r--;
		}
		else{
			cin >> vq[i].l >> vq[i].k;
			vq[i].l--;
		}
	}
	DS ds;
	ds.init(n);
	ds.pre(n);
	Q13 ss;
	ss.solve(n,q);
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21704 KB Output is correct
2 Correct 113 ms 23824 KB Output is correct
3 Correct 121 ms 21652 KB Output is correct
4 Incorrect 118 ms 21668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 73868 KB Output is correct
2 Correct 568 ms 66032 KB Output is correct
3 Correct 784 ms 83956 KB Output is correct
4 Correct 560 ms 75308 KB Output is correct
5 Correct 547 ms 65028 KB Output is correct
6 Correct 755 ms 92588 KB Output is correct
7 Correct 140 ms 34268 KB Output is correct
8 Correct 149 ms 34272 KB Output is correct
9 Correct 697 ms 92288 KB Output is correct
10 Correct 689 ms 92268 KB Output is correct
11 Correct 613 ms 84124 KB Output is correct
12 Correct 751 ms 84112 KB Output is correct
13 Incorrect 836 ms 83924 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 22908 KB Output is correct
2 Correct 135 ms 22084 KB Output is correct
3 Correct 139 ms 24176 KB Output is correct
4 Correct 100 ms 21164 KB Output is correct
5 Correct 127 ms 22720 KB Output is correct
6 Correct 132 ms 24084 KB Output is correct
7 Correct 41 ms 10628 KB Output is correct
8 Correct 43 ms 10192 KB Output is correct
9 Correct 81 ms 23452 KB Output is correct
10 Correct 77 ms 19740 KB Output is correct
11 Correct 113 ms 23576 KB Output is correct
12 Correct 137 ms 23576 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -