oj.uz

Submission #128327

# Submission time Handle Problem Language Result Execution time Memory
128327 2019-07-10T17:21:15 Z qkxwsm New Home (APIO18_new_home) C++14
10 / 100
 4484 ms 251512 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 65 ms 56696 KB Output is correct
2 Correct 67 ms 56732 KB Output is correct
3 Correct 65 ms 56652 KB Output is correct
4 Incorrect 71 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 56696 KB Output is correct
2 Correct 67 ms 56732 KB Output is correct
3 Correct 65 ms 56652 KB Output is correct
4 Incorrect 71 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4434 ms 249120 KB Output is correct
2 Correct 3406 ms 250800 KB Output is correct
3 Correct 4484 ms 249208 KB Output is correct
4 Correct 4345 ms 249384 KB Output is correct
5 Correct 2525 ms 251512 KB Output is correct
6 Correct 3364 ms 251404 KB Output is correct
7 Correct 4431 ms 249480 KB Output is correct
8 Correct 4297 ms 249464 KB Output is correct
9 Correct 4218 ms 249200 KB Output is correct
10 Correct 3714 ms 249328 KB Output is correct
11 Correct 2762 ms 244340 KB Output is correct
12 Correct 3438 ms 245260 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3208 ms 228152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 56696 KB Output is correct
2 Correct 67 ms 56732 KB Output is correct
3 Correct 65 ms 56652 KB Output is correct
4 Incorrect 71 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 56696 KB Output is correct
2 Correct 67 ms 56732 KB Output is correct
3 Correct 65 ms 56652 KB Output is correct
4 Incorrect 71 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -