Submission #128323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
128323	2019-07-10T16:56:46 Z	qkxwsm	New Home (APIO18_new_home)	C++14	10 / 100	531 ms	30056 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	466 ms	29748 KB	Output is correct
2	Correct	438 ms	29620 KB	Output is correct
3	Correct	463 ms	30052 KB	Output is correct
4	Correct	531 ms	29712 KB	Output is correct
5	Correct	406 ms	28280 KB	Output is correct
6	Correct	440 ms	29516 KB	Output is correct
7	Correct	435 ms	30056 KB	Output is correct
8	Correct	438 ms	29796 KB	Output is correct
9	Correct	442 ms	29664 KB	Output is correct
10	Correct	424 ms	28532 KB	Output is correct
11	Correct	390 ms	27748 KB	Output is correct
12	Correct	412 ms	28572 KB	Output is correct