Submission #1070834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070834		pawned	New Home (APIO18_new_home)	C++17	12 / 100	5097 ms	45464 KiB

new_home

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

int main() {
	fastIO();
	int N, K, Q;
	cin>>N>>K>>Q;
	// stores of each type
	vector<pair<int, ii>> stores[K];
	// {pos, {start, end}}
	// keep track of all openings / closings
	vector<pair<ii, ii>> actions;
	// {time, type}, {store type, pos}}
	// type = 0 if open, 1 if close
	for (int i = 0; i < N; i++) {
		int x, y, a, b;
		cin>>x>>y>>a>>b;
		x--; y--;
		stores[y].pb({x, {a, b}});
		actions.pb({{a, 0}, {y, x}});	// store open
		actions.pb({{b + 1, 1}, {y, x}});	// store close
	}
	vector<pair<ii, int>> queries;
	// {{time, type}, {pos, id}}
	// type = 2 if query
	for (int i = 0; i < Q; i++) {
		int x, t;	// x = position, t = time
		cin>>x>>t;
		x--;
		actions.pb({{t, 2}, {x, i}});
	}
	sort(actions.begin(), actions.end());
	// queries come after updates
	multiset<int> all[K];	// current open
	vi ans(Q, -1);
	for (pair<ii, ii> p : actions) {
		int ct = p.fi.fi;
		int type = p.fi.se;
		if (type == 0) {	// store open
			int tr = p.se.fi;	// store type
			int pos = p.se.se;
			all[tr].insert(pos);
		}
		else if (type == 1) {
			int tr = p.se.fi;
			int pos = p.se.se;
			all[tr].erase(all[tr].find(pos));
		}
		else {
			int x = p.se.fi;
			int id = p.se.se;
			ans[id] = -1;
			for (int j = 0; j < K; j++) {
				int md = 1e9;	// minimum distance
				// get lower and upper
				auto it1 = all[j].lower_bound(x);
				if (it1 != all[j].end())
					md = min(md, (*it1) - x);
				if (it1 != all[j].begin()) {
					it1--;
					md = min(md, x - (*it1));
				}
				ans[id] = max(ans[id], md);
			}
		}
	}
//	cout<<"ANSWER: "<<endl;
	for (int i = 0; i < Q; i++) {
		if (ans[i] != 1e9)
			cout<<ans[i]<<endl;
		else
			cout<<-1<<endl;
	}
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:53:7: warning: unused variable 'ct' [-Wunused-variable]
   53 |   int ct = p.fi.fi;
      |       ^~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20