oj.uz

답안 #540385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540385 2022-03-20T08:58:20 Z alvingogo 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 260 ms 79356 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;
};
struct DS{
	
};
vector<qu> vq;
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==2){
			}
			else{
				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;
	Q13 ss;
	int n,m,q;
	cin >> n >> m >> q;
	vq.resize(q);
	ss.init(n+1,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){
			assert(0);
			cin >> vq[i].l >> vq[i].r >> vq[i].c >> vq[i].k;
			vq[i].l--;
			vq[i].r--;
		}
		else{
			cin >> vq[i].c >> vq[i].k;
			vq[i].c--;
			vq[i].l=i;
		}
	}
	ss.solve(n,q);
	return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 23156 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 56 ms 79356 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 26636 KB Output is correct
2 Correct 260 ms 27352 KB Output is correct
3 Correct 234 ms 29048 KB Output is correct
4 Correct 183 ms 23432 KB Output is correct
5 Correct 213 ms 27264 KB Output is correct
6 Correct 249 ms 30444 KB Output is correct
7 Correct 41 ms 7384 KB Output is correct
8 Correct 39 ms 6648 KB Output is correct
9 Correct 64 ms 16756 KB Output is correct
10 Correct 176 ms 24688 KB Output is correct
11 Correct 239 ms 33760 KB Output is correct
12 Correct 240 ms 33712 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -