oj.uz

답안 #540488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540488 2022-03-20T13:42:47 Z alvingogo 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 1000 ms 123932 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 BIT{
	int n;
	vector<int> bt;
	void init(int nn){
		n=nn;
		bt.resize(n);
	}
	void update(int x,int y){
		x++;
		for(;x<=n;x+=(x&-x)){
			bt[x]+=y;
		}
	}
	int query(int x){
		x++;
		int ans=0;
		for(;x>0;x-=(x&-x)){
			ans+=bt[x];
		}
		return ans;
	}
};
struct qu{
	int t;
	int l,r,c,k;
	int ans=-1;
};
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{
				int p=query(0,0,n-1,h.c);
				//assert(p==0);
				h.k+=p;
			}
		}
	}
};
struct Q13{
	struct upd{
		int t,u,k;
	};
	vector<vector<int> > qq;
	BIT bt;
	vector<vector<upd> > st;
	map<int,int> s;
	void init(int n,int q){
		bt.init(q+10);
		st.resize(4*n);
		qq.resize(n);
	}
	void update(int v,int L,int R,int l,int r,upd a){
		if(l==L && r==R){
			st[v].push_back(a);
			return;
		}
		int m=(L+R)/2;
		if(r<=m){
			update(2*v+1,L,m,l,r,a);
		}
		else if(l>m){
			update(2*v+2,m+1,R,l,r,a);
		}
		else{
			update(2*v+1,L,m,l,m,a);
			update(2*v+2,m+1,R,m+1,r,a);
		}
	}
	void trav(int v,int L,int R){
		for(auto h:st[v]){
			bt.update(h.t,h.k);
			s[h.t]=h.u;
		}
		if(L==R){
			for(auto h:qq[L]){
				int l=0,r=vq[h].l-1;
				while(r>l){
					int m=(l+r+1)/2;
					if(bt.query(m)<vq[h].k){
						l=m;
					}
					else{
						r=m-1;
					}
				}
				if(bt.query(l+1)<vq[h].k){
					vq[h].ans=0;
				}
				else{
					vq[h].ans=(*s.upper_bound(l)).sc;
				}
			}
		}
		else{
			int m=(L+R)/2;
			trav(2*v+1,L,m);
			trav(2*v+2,m+1,R);
		}
		for(auto h:st[v]){
			bt.update(h.t,-h.k);
			s.erase(h.t);
		}
	}
	void solve(int n,int q){
		for(int i=0;i<q;i++){
			if(vq[i].t==1){
				update(0,0,n-1,vq[i].l,vq[i].r,{i+1,vq[i].c,vq[i].k});
			}
			else if(vq[i].t==3){
				qq[vq[i].c].push_back(i);
			}
		}
		trav(0,0,n-1);
		for(int i=0;i<q;i++){
			if(vq[i].t==3){
				cout << vq[i].ans << "\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].c >> vq[i].k;
			vq[i].c--;
			vq[i].l=i;
		}
	}
	DS ds;
	ds.init(n);
	ds.pre(n);
	Q13 ss;
	ss.init(n,q);
	ss.solve(n,q);
	return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 26280 KB Output is correct
2 Correct 138 ms 27468 KB Output is correct
3 Correct 142 ms 27212 KB Output is correct
4 Incorrect 125 ms 28132 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 123932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 37184 KB Output is correct
2 Correct 316 ms 37888 KB Output is correct
3 Correct 340 ms 41500 KB Output is correct
4 Correct 223 ms 35076 KB Output is correct
5 Correct 287 ms 38992 KB Output is correct
6 Correct 336 ms 42956 KB Output is correct
7 Correct 43 ms 7400 KB Output is correct
8 Correct 41 ms 6620 KB Output is correct
9 Correct 87 ms 28664 KB Output is correct
10 Correct 195 ms 34968 KB Output is correct
11 Correct 281 ms 45628 KB Output is correct
12 Correct 280 ms 45404 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -