oj.uz

답안 #538554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538554 2022-03-17T04:51:29 Z alvingogo 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 310 ms 79328 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 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);
		}
	}
};
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--;
			ss.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){
			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.qq[vq[i].c].push_back(i);
		}
	}
	ss.trav(0,0,n-1);
	for(int i=0;i<q;i++){
		if(vq[i].t==3){
			cout << vq[i].ans << "\n";
		}
	}
	return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 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 23124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 25188 KB Output is correct
2 Correct 255 ms 27368 KB Output is correct
3 Correct 259 ms 29112 KB Output is correct
4 Correct 183 ms 23392 KB Output is correct
5 Correct 226 ms 27068 KB Output is correct
6 Correct 261 ms 30496 KB Output is correct
7 Correct 46 ms 7416 KB Output is correct
8 Correct 40 ms 6588 KB Output is correct
9 Correct 67 ms 16744 KB Output is correct
10 Correct 183 ms 24680 KB Output is correct
11 Correct 310 ms 33752 KB Output is correct
12 Correct 247 ms 33664 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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