oj.uz

Submission #768463

# Submission time Handle Problem Language Result Execution time Memory
768463 2023-06-28T07:42:41 Z minhcool Sweeping (JOI20_sweeping) C++17
1 / 100
 18000 ms 1008580 KB 
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2000005 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n, m, q;
int x[N], y[N];
int type[N], width[N];
 
ii answer[N];
 
vector<ii> asks[N];// ask which node, after which query?
 
vector<int> queries[N];// queries like "we start from query i, we ask for this node"
 
set<int> IT1[(2LL << 21)], IT2[(2LL << 21)];
 
void upd1(int id, int l, int r, int pos, int val, bool add){
	if(add) IT1[id].insert(val);
	else IT1[id].erase(val);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd1(id << 1, l, mid, pos, val, add);
	else upd1(id << 1 | 1, mid + 1, r, pos, val, add);
}
 
int get1(int id, int l, int r, int le, int ri){
	if(IT1[id].size() == 0) return oo;
	if(l == r){
		int temp = (*IT1[id].begin());
		if(temp > ri || temp < le) return oo;
		return l;
	}
//	cout << "ID " << id << " ";
//	for(auto it : IT1[id]) cout << it << " ";
//	cout << "\n";
	int mid = (l + r) >> 1;
	if(!IT1[id << 1].size()) return get1(id << 1 | 1, mid + 1, r, le, ri);
	else{
		set<int>::iterator it = IT1[id << 1].lower_bound(le);
		if(it == IT1[id << 1].end() || (*it) > ri) return get1(id << 1 | 1, mid + 1, r, le, ri);
		else return get1(id << 1, l, mid, le, ri);
	}
}
 
void upd2(int id, int l, int r, int pos, int val, bool add){
	if(add) IT2[id].insert(val);
	else IT2[id].erase(val);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd2(id << 1, l, mid, pos, val, add);
	else upd2(id << 1 | 1, mid + 1, r, pos, val, add);
}
 
int get2(int id, int l, int r, int le, int ri){
	if(IT2[id].size() == 0) return oo;
	if(l == r){
		int temp = (*IT2[id].begin());
		if(temp > ri || temp < le) return oo;
		return l;
	}
	int mid = (l + r) >> 1;
	if(!IT2[id << 1].size()) return get2(id << 1 | 1, mid + 1, r, le, ri);
	else{
		set<int>::iterator it = IT2[id << 1].lower_bound(le);
		if(it == IT2[id << 1].end() || (*it) > ri) return get2(id << 1 | 1, mid + 1, r, le, ri);
		else return get2(id << 1, l, mid, le, ri);
	}
}
 
vector<int> v1, v2;
 
#ifdef local
void process(){
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++){
		cin >> x[i] >> y[i];
		queries[1].pb(i);
	} 
	int cnt1 = m, cnt2 = 0, cnt3 = 0;
	for(int i = 1; i <= q; i++){
		int typ;
		cin >> typ;
		if(typ == 1){
			int x;
			cin >> x;
			cnt3++;
			asks[x].pb({cnt2, cnt3});
		}
		else if(typ == 2){
			cnt2++;	
			int l;
			cin >> l;
			type[cnt2] = 0, width[cnt2] = l;
		}
		else if(typ == 3){
			cnt2++;
			int l;
			cin >> l;
			type[cnt2] = 1, width[cnt2] = l;
		}
		else{
			cnt1++;
			cin >> x[cnt1] >> y[cnt1];
			queries[cnt2 + 1].pb(cnt1);
		}
	}
	for(int i = 1; i <= cnt1; i++) reverse(asks[i].begin(), asks[i].end());
	int cnth = 0, cntv = 0;
	for(int i = 1; i <= cnt2; i++){
		if(type[i] == 0) cnth++;
		else cntv++;
	}
	int temph = cnth, tempv = cntv;
	cnth = 0, cntv = 0;
	v1.pb(-1), v2.pb(-1);
	for(int i = 1; i <= cnt2; i++){
		if(type[i] == 0){
			cnth++;
		//	cout << "OKOKOK " << width[i] << "\n";
			upd1(1, 1, temph, cnth, width[i], 1);
			v1.pb(i);
		}
		else{
			cntv++;
			upd2(1, 1, tempv, cntv, width[i], 1);
			v2.pb(i);
		}
	}
	v1.pb(oo), v2.pb(oo);
	//return;
	cnth = 0, cntv = 0;
	for(int i = 1; i <= cnt2; i++){
		for(auto it : queries[i]){
			int pos = it, pos1 = oo, pos2 = oo;
			// H first: given current (x, y)
			int le = y[pos], ri = n - x[pos] - 1;
			if(le <= ri) pos1 = get1(1, 1, temph, le, ri);
		//	cout << le << " " << ri << "\n";
			le = x[pos], ri = n - y[pos] - 1;
			if(le <= ri) pos2 = get2(1, 1, tempv, le, ri);
		//	cout << le << " " << ri << "\n";
		//	continue;
			pos1 = v1[min((int)v1.size() - 1, pos1)], pos2 = v2[min((int)v2.size() - 1, pos2)];
		//	cout << i << " " << pos << " " << pos1 << " " << pos2 << "\n";
			while(asks[pos].size() && asks[pos].back().fi < min(pos1, pos2)){
		//		cout << "OK " << asks[pos].back().fi << " " << asks[pos].back().se << "\n";
				answer[asks[pos].back().se] = make_pair(x[pos], y[pos]);
				asks[pos].pop_back();
			}
			if(min(pos1, pos2) > cnt2) continue;
		//	cout << pos1 << " " << pos2 << "\n";
		//	continue;
			if(pos1 < pos2) x[pos] = n - width[pos1];
			else y[pos] = n - width[pos2];
		//	cout << pos1 << " " << pos2 << "\n";
		//	continue;
			queries[min(pos1, pos2) + 1].pb(it);
		}
		if(type[i] == 0){
			cnth++;
			upd1(1, 1, temph, cnth, width[i], 0);
		}
		else{
			cntv++;
			upd2(1, 1, tempv, cntv, width[i], 0);
		}
	}
	for(int i = 1; i <= cnt1; i++){
		for(auto it : asks[i]) answer[it.se] = {x[i], y[i]};
	}
	for(int i = 1; i <= cnt3; i++) cout << answer[i].fi << " " << answer[i].se << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("sweep.inp", "r", stdin);
	//freopen("sweep.out", "w", stdout);
	cin.tie(0);
	process();
}
#endif

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 489164 KB Output is correct
2 Correct 202 ms 489440 KB Output is correct
3 Correct 196 ms 488396 KB Output is correct
4 Correct 197 ms 489092 KB Output is correct
5 Correct 203 ms 489792 KB Output is correct
6 Correct 196 ms 488540 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12531 ms 906204 KB Output is correct
2 Correct 11941 ms 906368 KB Output is correct
3 Correct 10759 ms 906416 KB Output is correct
4 Incorrect 6490 ms 906048 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12117 ms 998796 KB Output is correct
2 Correct 11279 ms 989624 KB Output is correct
3 Correct 3861 ms 978084 KB Output is correct
4 Execution timed out 18107 ms 1008580 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 12117 ms 998796 KB Output is correct
2 Correct 11279 ms 989624 KB Output is correct
3 Correct 3861 ms 978084 KB Output is correct
4 Execution timed out 18107 ms 1008580 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 489164 KB Output is correct
2 Correct 202 ms 489440 KB Output is correct
3 Correct 196 ms 488396 KB Output is correct
4 Correct 197 ms 489092 KB Output is correct
5 Correct 203 ms 489792 KB Output is correct
6 Correct 196 ms 488540 KB Output is correct
7 Correct 12531 ms 906204 KB Output is correct
8 Correct 11941 ms 906368 KB Output is correct
9 Correct 10759 ms 906416 KB Output is correct
10 Incorrect 6490 ms 906048 KB Output isn't correct
11 Halted 0 ms 0 KB -