oj.uz

Submission #113782

# Submission time Handle Problem Language Result Execution time Memory
113782 2019-05-28T08:36:09 Z ckodser New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 238252 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 300005, INF = 2e8 + 10;
int n, k, A[N], TP[N], L[N], R[N];
int q, B[N], T[N], P[N], rev[N], res[N];
vector < int > U, S[N], E[N], Q[N];
multiset < int > ST[N];
struct SEGT
{
	multiset < int > MS[N * 2];
	inline void Add(int le, int ri, int val)
	{
		le += q; ri += q;
		for (; le < ri; le >>= 1, ri >>= 1)
		{
			if (le & 1) MS[le ++].insert(val);
			if (ri & 1) MS[-- ri].insert(val);
		}
	}
	inline void Del(multiset < int > &SS, int val)
	{
		auto it = SS.lower_bound(val);
		if ((*it) == val)
			SS.erase(it);
	}
	inline void Del(int le, int ri, int val)
	{
		le += q; ri += q;
		for (; le < ri; le >>= 1, ri >>= 1)
		{
			if (le & 1) Del(MS[le], val), le ++;
			if (ri & 1) ri --, Del(MS[ri], val);
		}
	}
	inline int Get(int i)
	{
		int Mn = INT_MAX, Mx = INT_MIN;
		for (int id = i + q; id; id >>= 1)
			if (MS[id].size())
			{
				Mn = min(Mn, *MS[id].begin());
				Mx = max(Mx, *MS[id].rbegin());
			}
		return (max(Mx - B[P[i]], B[P[i]] - Mn));
	}
};
SEGT SG;
inline bool CMP(int i, int j)
{
	return (B[i] < B[j]);
}
inline void Fix(int l, int r, int tp)
{
	B[q] = l; int le = lower_bound(P, P + q, q, CMP) - P;
	B[q] = r; int ri = upper_bound(P, P + q, q, CMP) - P;
	B[q] = (l + r) >> 1; int md = upper_bound(P, P + q, q, CMP) - P;
	if (tp == 1)
	{
		SG.Add(le, md, l);
		SG.Add(md, ri, r);
	}
	else
	{
		SG.Del(le, md, l);
		SG.Del(md, ri, r);
	}
}
int main()
{
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 0; i < n; i++)
		scanf("%d%d%d%d", &A[i], &TP[i], &L[i], &R[i]), U.pb(L[i]), U.pb(R[i] + 1);
	for (int i = 0; i < q; i++)
		scanf("%d%d", &B[i], &T[i]);

	for (int i = 0; i < 10; i++)
		U.pb(i);

	sort(U.begin(), U.end());
	U.resize(unique(U.begin(), U.end()) - U.begin());
	for (int i = 0; i < n; i++)
	{
		L[i] = (int)(lower_bound(U.begin(), U.end(), L[i]) - U.begin());
		R[i] = (int)(lower_bound(U.begin(), U.end(), R[i] + 1) - U.begin());

		S[L[i]].pb(i); E[R[i]].pb(i);
	}
	for (int i = 0; i < q; i++)
	{
		T[i] = (int)(upper_bound(U.begin(), U.end(), T[i]) - U.begin()) - 1;
		Q[T[i]].pb(i); P[i] = i;
	}
	sort(P, P + q, CMP);
	for (int i = 0; i < q; i++)
		rev[P[i]] = i;
	int bad = k;
	for (int i = 1; i <= k; i++)
	{
		ST[i].insert(-INF);
		ST[i].insert(INF);
		SG.Add(0, q, INF);
	}
	for (int i = 0; i <= (int)U.size(); i++)
	{
		for (int &id : E[i])
		{
			int tp = TP[id], l, r;
			auto it = ST[tp].lower_bound(A[id]);
			it = ST[tp].erase(it);
			r = * it; it --; l = * it;
			Fix(l, A[id], -1);
			Fix(A[id], r, -1);
			Fix(l, r, 1);
			bad += (ST[tp].size() == 2);
		}
		for (int &id : S[i])
		{
			int tp = TP[id], l, r;
			bad -= (ST[tp].size() == 2);
			auto it = ST[tp].lower_bound(A[id]);
			r = * it; it --; l = * it;
			ST[tp].insert(A[id]);
			Fix(l, r, -1);
			Fix(l, A[id], 1);
			Fix(A[id], r, 1);
		}
		for (int &id : Q[i])
		{
			if (bad)
				res[id] = -1;
			else
				res[id] = SG.Get(rev[id]);
		}
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", res[i]);
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:74:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A[i], &TP[i], &L[i], &R[i]), U.pb(L[i]), U.pb(R[i] + 1);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &B[i], &T[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63736 KB Output is correct
2 Correct 53 ms 63736 KB Output is correct
3 Correct 55 ms 63736 KB Output is correct
4 Correct 54 ms 63892 KB Output is correct
5 Correct 55 ms 63864 KB Output is correct
6 Correct 55 ms 63864 KB Output is correct
7 Correct 56 ms 63992 KB Output is correct
8 Correct 57 ms 64124 KB Output is correct
9 Correct 56 ms 64120 KB Output is correct
10 Correct 57 ms 63864 KB Output is correct
11 Correct 56 ms 63864 KB Output is correct
12 Correct 56 ms 63864 KB Output is correct
13 Correct 54 ms 63736 KB Output is correct
14 Correct 55 ms 63864 KB Output is correct
15 Correct 56 ms 63864 KB Output is correct
16 Correct 57 ms 63992 KB Output is correct
17 Correct 56 ms 63836 KB Output is correct
18 Correct 58 ms 63964 KB Output is correct
19 Correct 55 ms 63940 KB Output is correct
20 Correct 57 ms 63836 KB Output is correct
21 Correct 53 ms 63864 KB Output is correct
22 Correct 56 ms 64120 KB Output is correct
23 Correct 55 ms 64120 KB Output is correct
24 Correct 57 ms 63992 KB Output is correct
25 Correct 59 ms 63872 KB Output is correct
26 Correct 55 ms 63744 KB Output is correct
27 Correct 56 ms 63864 KB Output is correct
28 Correct 57 ms 63864 KB Output is correct
29 Correct 54 ms 63840 KB Output is correct
30 Correct 54 ms 63736 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63736 KB Output is correct
2 Correct 53 ms 63736 KB Output is correct
3 Correct 55 ms 63736 KB Output is correct
4 Correct 54 ms 63892 KB Output is correct
5 Correct 55 ms 63864 KB Output is correct
6 Correct 55 ms 63864 KB Output is correct
7 Correct 56 ms 63992 KB Output is correct
8 Correct 57 ms 64124 KB Output is correct
9 Correct 56 ms 64120 KB Output is correct
10 Correct 57 ms 63864 KB Output is correct
11 Correct 56 ms 63864 KB Output is correct
12 Correct 56 ms 63864 KB Output is correct
13 Correct 54 ms 63736 KB Output is correct
14 Correct 55 ms 63864 KB Output is correct
15 Correct 56 ms 63864 KB Output is correct
16 Correct 57 ms 63992 KB Output is correct
17 Correct 56 ms 63836 KB Output is correct
18 Correct 58 ms 63964 KB Output is correct
19 Correct 55 ms 63940 KB Output is correct
20 Correct 57 ms 63836 KB Output is correct
21 Correct 53 ms 63864 KB Output is correct
22 Correct 56 ms 64120 KB Output is correct
23 Correct 55 ms 64120 KB Output is correct
24 Correct 57 ms 63992 KB Output is correct
25 Correct 59 ms 63872 KB Output is correct
26 Correct 55 ms 63744 KB Output is correct
27 Correct 56 ms 63864 KB Output is correct
28 Correct 57 ms 63864 KB Output is correct
29 Correct 54 ms 63840 KB Output is correct
30 Correct 54 ms 63736 KB Output is correct
31 Correct 3553 ms 112928 KB Output is correct
32 Correct 2123 ms 82288 KB Output is correct
33 Correct 1128 ms 79468 KB Output is correct
34 Correct 3414 ms 89932 KB Output is correct
35 Correct 2633 ms 104296 KB Output is correct
36 Correct 1209 ms 86712 KB Output is correct
37 Correct 866 ms 73876 KB Output is correct
38 Correct 582 ms 72840 KB Output is correct
39 Correct 467 ms 71988 KB Output is correct
40 Correct 477 ms 72084 KB Output is correct
41 Correct 1337 ms 72692 KB Output is correct
42 Correct 1319 ms 72896 KB Output is correct
43 Correct 258 ms 70896 KB Output is correct
44 Correct 1287 ms 72600 KB Output is correct
45 Correct 981 ms 72248 KB Output is correct
46 Correct 691 ms 72256 KB Output is correct
47 Correct 429 ms 71568 KB Output is correct
48 Correct 385 ms 71552 KB Output is correct
49 Correct 530 ms 71764 KB Output is correct
50 Correct 893 ms 72468 KB Output is correct
51 Correct 526 ms 71868 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5108 ms 238252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5112 ms 197332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63736 KB Output is correct
2 Correct 53 ms 63736 KB Output is correct
3 Correct 55 ms 63736 KB Output is correct
4 Correct 54 ms 63892 KB Output is correct
5 Correct 55 ms 63864 KB Output is correct
6 Correct 55 ms 63864 KB Output is correct
7 Correct 56 ms 63992 KB Output is correct
8 Correct 57 ms 64124 KB Output is correct
9 Correct 56 ms 64120 KB Output is correct
10 Correct 57 ms 63864 KB Output is correct
11 Correct 56 ms 63864 KB Output is correct
12 Correct 56 ms 63864 KB Output is correct
13 Correct 54 ms 63736 KB Output is correct
14 Correct 55 ms 63864 KB Output is correct
15 Correct 56 ms 63864 KB Output is correct
16 Correct 57 ms 63992 KB Output is correct
17 Correct 56 ms 63836 KB Output is correct
18 Correct 58 ms 63964 KB Output is correct
19 Correct 55 ms 63940 KB Output is correct
20 Correct 57 ms 63836 KB Output is correct
21 Correct 53 ms 63864 KB Output is correct
22 Correct 56 ms 64120 KB Output is correct
23 Correct 55 ms 64120 KB Output is correct
24 Correct 57 ms 63992 KB Output is correct
25 Correct 59 ms 63872 KB Output is correct
26 Correct 55 ms 63744 KB Output is correct
27 Correct 56 ms 63864 KB Output is correct
28 Correct 57 ms 63864 KB Output is correct
29 Correct 54 ms 63840 KB Output is correct
30 Correct 54 ms 63736 KB Output is correct
31 Correct 3553 ms 112928 KB Output is correct
32 Correct 2123 ms 82288 KB Output is correct
33 Correct 1128 ms 79468 KB Output is correct
34 Correct 3414 ms 89932 KB Output is correct
35 Correct 2633 ms 104296 KB Output is correct
36 Correct 1209 ms 86712 KB Output is correct
37 Correct 866 ms 73876 KB Output is correct
38 Correct 582 ms 72840 KB Output is correct
39 Correct 467 ms 71988 KB Output is correct
40 Correct 477 ms 72084 KB Output is correct
41 Correct 1337 ms 72692 KB Output is correct
42 Correct 1319 ms 72896 KB Output is correct
43 Correct 258 ms 70896 KB Output is correct
44 Correct 1287 ms 72600 KB Output is correct
45 Correct 981 ms 72248 KB Output is correct
46 Correct 691 ms 72256 KB Output is correct
47 Correct 429 ms 71568 KB Output is correct
48 Correct 385 ms 71552 KB Output is correct
49 Correct 530 ms 71764 KB Output is correct
50 Correct 893 ms 72468 KB Output is correct
51 Correct 526 ms 71868 KB Output is correct
52 Correct 2651 ms 148088 KB Output is correct
53 Correct 2449 ms 123020 KB Output is correct
54 Correct 4301 ms 141604 KB Output is correct
55 Correct 2222 ms 98676 KB Output is correct
56 Correct 2278 ms 111476 KB Output is correct
57 Correct 1993 ms 80468 KB Output is correct
58 Correct 2402 ms 98928 KB Output is correct
59 Correct 2708 ms 111788 KB Output is correct
60 Correct 2106 ms 80716 KB Output is correct
61 Correct 851 ms 107124 KB Output is correct
62 Correct 2974 ms 147952 KB Output is correct
63 Correct 3609 ms 133404 KB Output is correct
64 Correct 4170 ms 120452 KB Output is correct
65 Correct 3982 ms 88404 KB Output is correct
66 Correct 1580 ms 73652 KB Output is correct
67 Execution timed out 5079 ms 84308 KB Time limit exceeded

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63736 KB Output is correct
2 Correct 53 ms 63736 KB Output is correct
3 Correct 55 ms 63736 KB Output is correct
4 Correct 54 ms 63892 KB Output is correct
5 Correct 55 ms 63864 KB Output is correct
6 Correct 55 ms 63864 KB Output is correct
7 Correct 56 ms 63992 KB Output is correct
8 Correct 57 ms 64124 KB Output is correct
9 Correct 56 ms 64120 KB Output is correct
10 Correct 57 ms 63864 KB Output is correct
11 Correct 56 ms 63864 KB Output is correct
12 Correct 56 ms 63864 KB Output is correct
13 Correct 54 ms 63736 KB Output is correct
14 Correct 55 ms 63864 KB Output is correct
15 Correct 56 ms 63864 KB Output is correct
16 Correct 57 ms 63992 KB Output is correct
17 Correct 56 ms 63836 KB Output is correct
18 Correct 58 ms 63964 KB Output is correct
19 Correct 55 ms 63940 KB Output is correct
20 Correct 57 ms 63836 KB Output is correct
21 Correct 53 ms 63864 KB Output is correct
22 Correct 56 ms 64120 KB Output is correct
23 Correct 55 ms 64120 KB Output is correct
24 Correct 57 ms 63992 KB Output is correct
25 Correct 59 ms 63872 KB Output is correct
26 Correct 55 ms 63744 KB Output is correct
27 Correct 56 ms 63864 KB Output is correct
28 Correct 57 ms 63864 KB Output is correct
29 Correct 54 ms 63840 KB Output is correct
30 Correct 54 ms 63736 KB Output is correct
31 Correct 3553 ms 112928 KB Output is correct
32 Correct 2123 ms 82288 KB Output is correct
33 Correct 1128 ms 79468 KB Output is correct
34 Correct 3414 ms 89932 KB Output is correct
35 Correct 2633 ms 104296 KB Output is correct
36 Correct 1209 ms 86712 KB Output is correct
37 Correct 866 ms 73876 KB Output is correct
38 Correct 582 ms 72840 KB Output is correct
39 Correct 467 ms 71988 KB Output is correct
40 Correct 477 ms 72084 KB Output is correct
41 Correct 1337 ms 72692 KB Output is correct
42 Correct 1319 ms 72896 KB Output is correct
43 Correct 258 ms 70896 KB Output is correct
44 Correct 1287 ms 72600 KB Output is correct
45 Correct 981 ms 72248 KB Output is correct
46 Correct 691 ms 72256 KB Output is correct
47 Correct 429 ms 71568 KB Output is correct
48 Correct 385 ms 71552 KB Output is correct
49 Correct 530 ms 71764 KB Output is correct
50 Correct 893 ms 72468 KB Output is correct
51 Correct 526 ms 71868 KB Output is correct
52 Execution timed out 5108 ms 238252 KB Time limit exceeded
53 Halted 0 ms 0 KB -