oj.uz

Submission #128383

# Submission time Handle Problem Language Result Execution time Memory
128383 2019-07-10T20:38:08 Z qkxwsm New Home (APIO18_new_home) C++14
47 / 100
 3406 ms 375788 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;

int N, K, Q, S;
vector<ppp> arr;
vector<pair<pii, int> > quer;
int ans[MAXN];
multiset<int> pts[MAXN];
vector<array<int, 4> > segments;
vector<array<int, 4> > events;
map<pii, vi> cancer;
vpi seg[MAXN];

void ins(int l, int r, int t)
{
	// cerr << "ins " << l << ' ' << r << " time " << t << endl;
	l = (l + r + 1) >> 1;
	cancer[{l, r}].PB(SZ(segments));
	segments.PB({l, r, t, SZ(events)});
}
void del(int l, int r, int t)
{
	// cerr << "del " << l << ' ' << r << " time " << t << endl;
	l = (l + r + 1) >> 1;
	// cerr << "rem " << (cancer[{l, r}]).size() << endl;
	segments[cancer[{l, r}].back()][3] = t;
	cancer[{l, r}].pop_back();
}

void inseg(int w, int L, int R, int a, int b, pii p)
{
	if (a <= L && R <= b)
	{
		seg[w].PB(p);
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) inseg(w << 1, L, mid, a, b, p);
	if (mid < b) inseg(w << 1 | 1, mid + 1, R, a, b, p);
	return;
}
void build(int w, int L, int R)
{
	if (L != R)
	{
		int mid = (L + R) >> 1;
		build(w << 1, L, mid);
		build(w << 1 | 1, mid + 1, R);
	}
	sort(ALL(seg[w]));
	FOR(i, 1, SZ(seg[w]))
	{
		ckmax(seg[w][i].se, seg[w][i - 1].se);
	}
}
int query(int w, int L, int R, int a, int x)
{
	int res = -INF;
	int ind = UB(ALL(seg[w]), MP(x, INF)) - seg[w].begin() - 1;
	if (ind != -1) res = -x + seg[w][ind].se;
	if (L == R) return res;
	int mid = (L + R) >> 1;
	if (a <= mid) ckmax(res, query(w << 1, L, mid, a, x));
	else ckmax(res, query(w << 1 | 1, mid + 1, R, a, x));
	return res;
}

void solve()
{
	//consider distnace functions with negative slope ONLY.
	//arr: something of type t and position p in times (t1, t2)
	//quer: query of position p at time t, qid i
	FOR(i, 0, (1 << (33 - __builtin_clz(SZ(events)))))
	{
		seg[i].clear();
	}
	events.clear();
	cancer.clear();
	segments.clear();
	FOR(i, 0, K) pts[i].clear();
	FOR(i, 0, SZ(arr))
	{
		int t1 = arr[i].se.fi, t2 = arr[i].se.se, ty = arr[i].fi.fi, x = arr[i].fi.se;
		events.PB({t1, -1, ty, x});
		events.PB({t2, 1, ty, x});
	}
	FOR(i, 0, SZ(quer))
	{
		int t = quer[i].fi.se, x = quer[i].fi.fi, qid = quer[i].se;
		events.PB({t, 0, qid, x});
	}
	sort(ALL(events));
	FOR(i, 0, K)
	{
		pts[i].insert(2 * LIM);
		pts[i].insert(-2 * LIM);
		ins(-2 * LIM, 2 * LIM, 0);
	}
	FOR(i, 0, SZ(events))
	{
		int typ = events[i][2], pos = events[i][3];
		if (events[i][1] == -1)
		{
			auto it = pts[typ].UB(pos);
			int rt = *it, lt = *prev(it);
			pts[typ].insert(pos);
			//then between lt and rt you generate some new segments!
			//at time i you have to erase a segment! and then insert two new segments!
			//WARNING: IF NOT DISTINCT, PLEASE CHECK THIS PLACE
			ins(lt, pos, i + 1);
			ins(pos, rt, i + 1);
			del(lt, rt, i + 1);
		}
		if (events[i][1] == 1)
		{
			pts[typ].erase(pts[typ].find(pos));
			auto it = pts[typ].UB(pos);
			int rt = *it, lt = *prev(it);
			del(lt, pos, i + 1);
			del(pos, rt, i + 1);
			ins(lt, rt, i + 1);
		}
	}
	FOR(i, 0, SZ(segments))
	{
		int l = segments[i][2], r = segments[i][3];
		inseg(1, 0, SZ(events), l, r, {segments[i][0], segments[i][1]});
	}
	//ok cool we have the segments
	build(1, 0, SZ(events));
	FOR(i, 0, SZ(events))
	{
		if (events[i][1] == 0)
		{
			int qid = events[i][2], pos = events[i][3];
			ckmax(ans[qid], query(1, 0, SZ(events), i + 1, pos));
			// cerr << "ans " << qid << ' ' << ans[qid] << endl;
		}
	}
}

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--;
	}
	sort(ALL(arr));
	FOR(i, 0, Q)
	{
		cin >> quer[i].fi.fi >> quer[i].fi.se; quer[i].se = i;
	}
	sort(ALL(quer));
	solve();
	FOR(i, 0, N)
	{
		arr[i].fi.se = 100000001 - arr[i].fi.se;
	}
	FOR(i, 0, Q)
	{
		quer[i].fi.fi = 100000001 - quer[i].fi.fi;
	}
	solve();
	//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:183: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 42616 KB Output is correct
2 Correct 43 ms 42616 KB Output is correct
3 Correct 46 ms 42616 KB Output is correct
4 Correct 44 ms 42616 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 49 ms 42968 KB Output is correct
7 Correct 46 ms 43000 KB Output is correct
8 Correct 51 ms 43100 KB Output is correct
9 Correct 51 ms 43000 KB Output is correct
10 Correct 51 ms 42988 KB Output is correct
11 Correct 45 ms 42872 KB Output is correct
12 Correct 52 ms 42872 KB Output is correct
13 Correct 44 ms 42872 KB Output is correct
14 Correct 49 ms 42788 KB Output is correct
15 Correct 51 ms 43044 KB Output is correct
16 Correct 50 ms 43128 KB Output is correct
17 Correct 46 ms 43000 KB Output is correct
18 Correct 46 ms 43000 KB Output is correct
19 Correct 49 ms 42948 KB Output is correct
20 Correct 46 ms 43004 KB Output is correct
21 Correct 45 ms 43000 KB Output is correct
22 Correct 48 ms 42968 KB Output is correct
23 Correct 46 ms 43000 KB Output is correct
24 Correct 46 ms 43000 KB Output is correct
25 Correct 46 ms 42872 KB Output is correct
26 Correct 46 ms 42928 KB Output is correct
27 Correct 45 ms 42872 KB Output is correct
28 Correct 45 ms 42948 KB Output is correct
29 Correct 45 ms 42872 KB Output is correct
30 Correct 44 ms 42872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 42616 KB Output is correct
2 Correct 43 ms 42616 KB Output is correct
3 Correct 46 ms 42616 KB Output is correct
4 Correct 44 ms 42616 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 49 ms 42968 KB Output is correct
7 Correct 46 ms 43000 KB Output is correct
8 Correct 51 ms 43100 KB Output is correct
9 Correct 51 ms 43000 KB Output is correct
10 Correct 51 ms 42988 KB Output is correct
11 Correct 45 ms 42872 KB Output is correct
12 Correct 52 ms 42872 KB Output is correct
13 Correct 44 ms 42872 KB Output is correct
14 Correct 49 ms 42788 KB Output is correct
15 Correct 51 ms 43044 KB Output is correct
16 Correct 50 ms 43128 KB Output is correct
17 Correct 46 ms 43000 KB Output is correct
18 Correct 46 ms 43000 KB Output is correct
19 Correct 49 ms 42948 KB Output is correct
20 Correct 46 ms 43004 KB Output is correct
21 Correct 45 ms 43000 KB Output is correct
22 Correct 48 ms 42968 KB Output is correct
23 Correct 46 ms 43000 KB Output is correct
24 Correct 46 ms 43000 KB Output is correct
25 Correct 46 ms 42872 KB Output is correct
26 Correct 46 ms 42928 KB Output is correct
27 Correct 45 ms 42872 KB Output is correct
28 Correct 45 ms 42948 KB Output is correct
29 Correct 45 ms 42872 KB Output is correct
30 Correct 44 ms 42872 KB Output is correct
31 Correct 2210 ms 102920 KB Output is correct
32 Correct 469 ms 66404 KB Output is correct
33 Correct 1907 ms 101248 KB Output is correct
34 Correct 1848 ms 101708 KB Output is correct
35 Correct 2218 ms 102772 KB Output is correct
36 Correct 2080 ms 101936 KB Output is correct
37 Correct 1310 ms 97152 KB Output is correct
38 Correct 1261 ms 97032 KB Output is correct
39 Correct 877 ms 90432 KB Output is correct
40 Correct 920 ms 91828 KB Output is correct
41 Correct 1364 ms 95736 KB Output is correct
42 Correct 1415 ms 96192 KB Output is correct
43 Correct 396 ms 71828 KB Output is correct
44 Correct 1399 ms 95316 KB Output is correct
45 Correct 1212 ms 91496 KB Output is correct
46 Correct 979 ms 85484 KB Output is correct
47 Correct 683 ms 83152 KB Output is correct
48 Correct 632 ms 81592 KB Output is correct
49 Correct 709 ms 86628 KB Output is correct
50 Correct 1034 ms 93900 KB Output is correct
51 Correct 746 ms 84704 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2803 ms 375788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3406 ms 369464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 42616 KB Output is correct
2 Correct 43 ms 42616 KB Output is correct
3 Correct 46 ms 42616 KB Output is correct
4 Correct 44 ms 42616 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 49 ms 42968 KB Output is correct
7 Correct 46 ms 43000 KB Output is correct
8 Correct 51 ms 43100 KB Output is correct
9 Correct 51 ms 43000 KB Output is correct
10 Correct 51 ms 42988 KB Output is correct
11 Correct 45 ms 42872 KB Output is correct
12 Correct 52 ms 42872 KB Output is correct
13 Correct 44 ms 42872 KB Output is correct
14 Correct 49 ms 42788 KB Output is correct
15 Correct 51 ms 43044 KB Output is correct
16 Correct 50 ms 43128 KB Output is correct
17 Correct 46 ms 43000 KB Output is correct
18 Correct 46 ms 43000 KB Output is correct
19 Correct 49 ms 42948 KB Output is correct
20 Correct 46 ms 43004 KB Output is correct
21 Correct 45 ms 43000 KB Output is correct
22 Correct 48 ms 42968 KB Output is correct
23 Correct 46 ms 43000 KB Output is correct
24 Correct 46 ms 43000 KB Output is correct
25 Correct 46 ms 42872 KB Output is correct
26 Correct 46 ms 42928 KB Output is correct
27 Correct 45 ms 42872 KB Output is correct
28 Correct 45 ms 42948 KB Output is correct
29 Correct 45 ms 42872 KB Output is correct
30 Correct 44 ms 42872 KB Output is correct
31 Correct 2210 ms 102920 KB Output is correct
32 Correct 469 ms 66404 KB Output is correct
33 Correct 1907 ms 101248 KB Output is correct
34 Correct 1848 ms 101708 KB Output is correct
35 Correct 2218 ms 102772 KB Output is correct
36 Correct 2080 ms 101936 KB Output is correct
37 Correct 1310 ms 97152 KB Output is correct
38 Correct 1261 ms 97032 KB Output is correct
39 Correct 877 ms 90432 KB Output is correct
40 Correct 920 ms 91828 KB Output is correct
41 Correct 1364 ms 95736 KB Output is correct
42 Correct 1415 ms 96192 KB Output is correct
43 Correct 396 ms 71828 KB Output is correct
44 Correct 1399 ms 95316 KB Output is correct
45 Correct 1212 ms 91496 KB Output is correct
46 Correct 979 ms 85484 KB Output is correct
47 Correct 683 ms 83152 KB Output is correct
48 Correct 632 ms 81592 KB Output is correct
49 Correct 709 ms 86628 KB Output is correct
50 Correct 1034 ms 93900 KB Output is correct
51 Correct 746 ms 84704 KB Output is correct
52 Correct 1709 ms 108888 KB Output is correct
53 Correct 1534 ms 101708 KB Output is correct
54 Correct 2031 ms 103884 KB Output is correct
55 Correct 1469 ms 102080 KB Output is correct
56 Correct 1453 ms 104420 KB Output is correct
57 Correct 1459 ms 98152 KB Output is correct
58 Correct 1594 ms 101516 KB Output is correct
59 Correct 1629 ms 103932 KB Output is correct
60 Correct 1490 ms 97932 KB Output is correct
61 Correct 572 ms 98152 KB Output is correct
62 Correct 1639 ms 113972 KB Output is correct
63 Correct 1987 ms 106740 KB Output is correct
64 Correct 1976 ms 106048 KB Output is correct
65 Correct 2149 ms 103988 KB Output is correct
66 Correct 1471 ms 98144 KB Output is correct
67 Correct 909 ms 78736 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 42616 KB Output is correct
2 Correct 43 ms 42616 KB Output is correct
3 Correct 46 ms 42616 KB Output is correct
4 Correct 44 ms 42616 KB Output is correct
5 Correct 48 ms 42744 KB Output is correct
6 Correct 49 ms 42968 KB Output is correct
7 Correct 46 ms 43000 KB Output is correct
8 Correct 51 ms 43100 KB Output is correct
9 Correct 51 ms 43000 KB Output is correct
10 Correct 51 ms 42988 KB Output is correct
11 Correct 45 ms 42872 KB Output is correct
12 Correct 52 ms 42872 KB Output is correct
13 Correct 44 ms 42872 KB Output is correct
14 Correct 49 ms 42788 KB Output is correct
15 Correct 51 ms 43044 KB Output is correct
16 Correct 50 ms 43128 KB Output is correct
17 Correct 46 ms 43000 KB Output is correct
18 Correct 46 ms 43000 KB Output is correct
19 Correct 49 ms 42948 KB Output is correct
20 Correct 46 ms 43004 KB Output is correct
21 Correct 45 ms 43000 KB Output is correct
22 Correct 48 ms 42968 KB Output is correct
23 Correct 46 ms 43000 KB Output is correct
24 Correct 46 ms 43000 KB Output is correct
25 Correct 46 ms 42872 KB Output is correct
26 Correct 46 ms 42928 KB Output is correct
27 Correct 45 ms 42872 KB Output is correct
28 Correct 45 ms 42948 KB Output is correct
29 Correct 45 ms 42872 KB Output is correct
30 Correct 44 ms 42872 KB Output is correct
31 Correct 2210 ms 102920 KB Output is correct
32 Correct 469 ms 66404 KB Output is correct
33 Correct 1907 ms 101248 KB Output is correct
34 Correct 1848 ms 101708 KB Output is correct
35 Correct 2218 ms 102772 KB Output is correct
36 Correct 2080 ms 101936 KB Output is correct
37 Correct 1310 ms 97152 KB Output is correct
38 Correct 1261 ms 97032 KB Output is correct
39 Correct 877 ms 90432 KB Output is correct
40 Correct 920 ms 91828 KB Output is correct
41 Correct 1364 ms 95736 KB Output is correct
42 Correct 1415 ms 96192 KB Output is correct
43 Correct 396 ms 71828 KB Output is correct
44 Correct 1399 ms 95316 KB Output is correct
45 Correct 1212 ms 91496 KB Output is correct
46 Correct 979 ms 85484 KB Output is correct
47 Correct 683 ms 83152 KB Output is correct
48 Correct 632 ms 81592 KB Output is correct
49 Correct 709 ms 86628 KB Output is correct
50 Correct 1034 ms 93900 KB Output is correct
51 Correct 746 ms 84704 KB Output is correct
52 Runtime error 2803 ms 375788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -