Submission #127791

#	Time	Username	Problem	Language	Result	Execution time	Memory
127791		qkxwsm	New Home (APIO18_new_home)	C++14	0 / 100	472 ms	15096 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define LIM 100000007
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 600013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, pii> ppp;

int N, K, Q, P;
vector<ppp> arr;
pii quer[MAXN];
int ans[MAXN];
vi compress, pos;
vpi func;
int mx, iter, freq;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> Q;
	arr.resize(N);
	FOR(i, 0, N)
	{
		cin >> arr[i].fi.se >> arr[i].fi.fi >> arr[i].se.fi >> arr[i].se.se;
		arr[i].fi.fi--;
	}
	FOR(i, 0, Q)
	{
		cin >> quer[i].fi >> quer[i].se; //location, time
		compress.PB(quer[i].se);
	}
	compress.PB(0); compress.PB(LIM);
	sort(ALL(compress));
	compress.erase(unique(ALL(compress)), compress.end());
	FOR(i, 0, N)
	{
		arr[i].se.fi = LB(ALL(compress), arr[i].se.fi) - compress.begin();
		arr[i].se.se = UB(ALL(compress), arr[i].se.se) - compress.begin() - 1;
	}
	FOR(i, 0, Q)
	{
		quer[i].se = LB(ALL(compress), quer[i].se) - compress.begin();
	}
	//type, location, times (whaever)
	//ok this is type what:
	sort(ALL(arr));
	freq = 0;
	FOR(i, 0, N)
	{
		//consider the distance functions formed! query max!
		//so for each of the things you should have shit of the form: a distance function that starts at time t that has x-intercept t1
		pos.PB(arr[i].fi.se);
		if (i == N - 1 || arr[i].fi.fi != arr[i + 1].fi.fi)
		{
			//build the shit! how about let's try the negatives first
			func.PB({0, pos[0]});
			// cerr << 0 << ' ' << pos[0] << endl;
			FOR(j, 1, SZ(pos))
			{
				func.PB({(pos[j - 1] + pos[j] + 1) >> 1, pos[j]});
			}
			pos.clear();
			freq++;
		}
	}
	if (freq != K)
	{
		func.PB({0, INF});
	}
	sort(ALL(func));
	mx = -INF; iter = 0;
	FOR(i, 0, SZ(func))
	{
		while(iter < Q && quer[iter].fi < func[i].fi)
		{
			ckmax(ans[iter], -quer[iter].fi + mx);
			iter++;
		}
		ckmax(mx, func[i].se);
		// cerr << "at location " << func[i].fi << " -x + " << func[i].se << endl;
	}
	while(iter < Q)
	{
		ckmax(ans[iter], -quer[iter].fi + mx);
		iter++;
	}
	// freq = 0; func.clear();
	// FOR(i, 0, N)
	// {
	// 	pos.PB(arr[i].fi.se);
	// 	if (i == N - 1 || arr[i].fi.fi != arr[i + 1].fi.fi)
	// 	{
	// 		//build the shit! how about let's try the negatives first
	// 		func.PB({LIM, -pos.back()});
	// 		FORD(j, SZ(func) - 1, 0)
	// 		{
	// 			func.PB({(pos[j] + pos[j + 1]) >> 1, -pos[j]});
	// 		}
	// 		pos.clear();
	// 		freq++;
	// 	}
	// }
	// if (freq != K)
	// {
	// 	func.PB({LIM, INF});
	// }
	// sort(ALL(func));
	// mx = -INF; iter = Q - 1;
	// FORD(i, SZ(func), 0)
	// {
	// 	while(iter >= 0 && quer[iter].fi > func[i].fi)
	// 	{
	// 		ckmax(ans[iter], quer[iter].fi + mx);
	// 		iter--;
	// 	}
	// 	ckmax(mx, func[i].se);
	// 	// cerr << "at location " << func[i].fi << " x + " << func[i].se << endl;
	// }
	// while(iter >= 0)
	// {
	// 	ckmax(ans[iter], quer[iter].fi + mx);
	// 	iter--;
	// }
	//events: OPEN/CLOSE a store at time t, position p, type x, ASK at time t, position p
	FOR(i, 0, Q)
	{
		if (ans[i] >= LIM)
		{
			cout << "-1\n";
			continue;
		}
		cout << ans[i] << '\n';
	}
	return 0;
}

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