Submission #128323

#	Time	Username	Problem	Language	Result	Execution time	Memory
128323		qkxwsm	New Home (APIO18_new_home)	C++14	10 / 100	531 ms	30056 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;
vector<pair<pii, int> > quer;
int ans[MAXN];
vi compress, pos;
vpi func;
int mx, iter, freq;

int32_t main()
{
	if (fopen("file.in", "r"))
	{
		freopen("file.in", "r", stdin);
	}
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> Q;
	arr.resize(N); quer.resize(Q);
	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.fi >> quer[i].fi.se; //location, time
		compress.PB(quer[i].fi.se);
		quer[i].se = i;
	}
	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].fi.se = LB(ALL(compress), quer[i].se) - compress.begin();
	}
	sort(ALL(quer));
	//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.fi < func[i].fi)
		{
			ckmax(ans[quer[iter].se], -quer[iter].fi.fi + mx);
			iter++;
		}
		ckmax(mx, func[i].se);
		// cerr << "at location " << func[i].fi << " -x + " << func[i].se << endl;
	}
	while(iter < Q)
	{
		ckmax(ans[quer[iter].se], -quer[iter].fi.fi + mx);
		iter++;
	}
	freq = 0; func.clear(); pos.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(pos) - 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.fi > func[i].fi)
		{
			ckmax(ans[quer[iter].se], quer[iter].fi.fi + mx);
			iter--;
		}
		ckmax(mx, func[i].se);
		// cerr << "at location " << func[i].fi << " x + " << func[i].se << endl;
	}
	while(iter >= 0)
	{
		ckmax(ans[quer[iter].se], quer[iter].fi.fi + mx);
		iter--;
	}
	// cerr << "HI\n";
	//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;
		}
		// cerr << "ans " << ans[i] << endl;
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int32_t main()':
new_home.cpp:53:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("file.in", "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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