Submission #128327

#	Time	Username	Problem	Language	Result	Execution time	Memory
128327		qkxwsm	New Home (APIO18_new_home)	C++14	10 / 100	4484 ms	251512 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;
typedef pair<pii, int> ppi;

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

void ins(int w, int L, int R, int a, int b, pii p)
{
	if (a <= L && R <= b)
	{
		arrs[w].PB(p);
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) ins(w << 1, L, mid, a, b, p);
	if (mid < b) ins(w << 1 | 1, mid + 1, R, a, b, p);
}
void qins(int w, int L, int R, int a, pii p)
{
	quers[w].PB(p);
	if (L == R) return;
	int mid = (L + R) >> 1;
	if (a <= mid) qins(w << 1, L, mid, a, p);
	else qins(w << 1 | 1, mid + 1, R, a, p);
}
void proc(int w, int L, int R)
{
	vi curans(SZ(quers[w]));
	freq = 0; func.clear();
	FOR(i, 0, SZ(arrs[w]))
	{
		pos.PB(arrs[w][i].se);
		if (i == SZ(arrs[w]) - 1 || arrs[w][i].fi != arrs[w][i + 1].fi)
		{
			func.PB({0, pos[0]});
			FOR(j, 1, SZ(pos))
			{
				func.PB({(pos[j - 1] + pos[j] + 1) >> 1, pos[j]});
			}
			pos.clear();
			freq++;
		}
	}
	if (freq != K)
	{
		func.clear();
		func.PB({0, INF});
	}
	sort(ALL(func));
	mx = -INF; iter = 0;
	FOR(i, 0, SZ(func))
	{
		while(iter < SZ(quers[w]) && quers[w][iter].fi < func[i].fi)
		{
			ckmax(curans[iter], -quers[w][iter].fi + mx);
			iter++;
		}
		ckmax(mx, func[i].se);
	}
	while(iter < SZ(quers[w]))
	{
		ckmax(curans[iter], -quers[w][iter].fi + mx);
		iter++;
	}
	freq = 0; func.clear();
	FOR(i, 0, SZ(arrs[w]))
	{
		pos.PB(arrs[w][i].se);
		if (i == SZ(arrs[w]) - 1 || arrs[w][i].fi != arrs[w][i + 1].fi)
		{
			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.clear();
		func.PB({LIM, INF});
	}
	sort(ALL(func));
	mx = -INF; iter = SZ(quers[w]) - 1;
	FORD(i, SZ(func), 0)
	{
		while(iter >= 0 && quers[w][iter].fi > func[i].fi)
		{
			ckmax(curans[iter], quers[w][iter].fi + mx);
			iter--;
		}
		ckmax(mx, func[i].se);
	}
	while(iter >= 0)
	{
		ckmax(curans[iter], quers[w][iter].fi + mx);
		iter--;
	}
	FOR(i, 0, SZ(quers[w]))
	{
		ckmin(ans[quers[w][i].se], curans[i]);
	}
	if (L == R) return;
	int mid = (L + R) >> 1;
	proc(w << 1, L, mid);
	proc(w << 1 | 1, mid + 1, R);
}

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].fi.se) - compress.begin();
		ans[i] = INF;
	}
	sort(ALL(quer));
	//type, location, times (whaever)
	//ok this is type what:
	sort(ALL(arr));
	FOR(i, 0, SZ(arr))
	{
		int t1 = arr[i].se.fi, t2 = arr[i].se.se;
		if (t1 > t2) continue;
		ins(1, 0, SZ(compress) - 1, t1, t2, arr[i].fi);
	}
	FOR(i, 0, SZ(quer))
	{
		qins(1, 0, SZ(compress) - 1, quer[i].fi.se, {quer[i].fi.fi, quer[i].se}); //location, id
	}
	proc(1, 0, SZ(compress) - 1);
	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:159: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