oj.uz

Submission #1071778

# Submission time Handle Problem Language Result Execution time Memory
1071778 2024-08-23T11:10:28 Z Tob New Home (APIO18_new_home) C++14
100 / 100
 4342 ms 811916 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 3e5 + 7, ofs = (1 << 20), inf = 2e9;

int n, k, q, cnt, cur, sad;
int a[N], b[N], g[N], ty[N], h[N], u[N], bb[2*N], res[N], fr[N], le[4*N];
int t[2][2*ofs], e[2][3*N];
pii gr[2][3*N];
vector <int> qu[ofs], addk[ofs], remk[ofs], dod[2*N], rem[2*N];
vector <pii> ev[2][2*ofs];
set <pii> s[N];

void walk(int x) {
	for (int ii = 0, o = 1; ii < 2; ii++, o = -o) {
		int cur = inf;
		for (auto it : ev[ii][x]) {
			int y = it.F;
			if (it.S) res[y] = max(res[y], o*h[y]-cur);
			else cur = min(cur, e[ii][y]*o);
		}
	}
	
	if (x >= ofs) {
		for (auto y : addk[x-ofs]) {fr[y]++; sad += (fr[y] == 1);}
		for (auto y : remk[x-ofs]) {fr[y]--; sad -= (!fr[y]);}
		for (auto y : qu[x-ofs]) if (sad != k) res[y] = -1;
	}
	else {
		walk(2*x);
		walk(2*x+1);
	}
}

void dodaj(int x, int a, int b, int o, pii y, int lo = 0, int hi = ofs-1) {
	if (b < lo || hi < a || a > b) return;
	if (a <= lo && hi <= b) {
		ev[o][x].pb(y);
		return;
	}
	int mid = (lo + hi) / 2;
	dodaj(2*x, a, b, o, y, lo, mid);
	dodaj(2*x+1, a, b, o, y, mid+1, hi);
}

int main () {
	FIO;
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2*ofs; j++) t[i][j] = inf;
	
	cin >> n >> k >> q;
	
	int nn2 = 1;
	for (int i = 0; i < n; i++) {
		cin >> g[i] >> ty[i] >> a[i] >> b[i]; b[i]++; ty[i]--;
		bb[nn2++] = a[i];
		bb[nn2++] = b[i];
	}
	for (int i = 0; i < q; i++) cin >> h[i] >> u[i];
	sort(bb, bb+nn2);
	int n2 = 1;
	for (int i = 1; i < nn2; i++) if (bb[i] != bb[n2-1]) bb[n2++] = bb[i];
	for (int i = 0; i < n; i++) {
		a[i] = upper_bound(bb, bb+n2, a[i])-bb-1;
		b[i] = upper_bound(bb, bb+n2, b[i])-bb-1;
		dod[a[i]].pb(i); rem[b[i]].pb(i);
		addk[a[i]].pb(ty[i]); remk[b[i]].pb(ty[i]);
	}
	for (int i = 0; i < q; i++) {u[i] = upper_bound(bb, bb+n2, u[i])-bb-1; qu[u[i]].pb(i);}
	
	int am = 0, bm = 0;
	vector <pair <pii, int> > va, vb;
	
	auto doo = [&](int x, int y, int i) {
		int mid = (y < n) ? (g[x]+g[y])/2 : inf, mid1 = (x < n) ? (g[x]+g[y]+1)/2 : 0;
		if (x < n) {
			va.pb({{mid, 1}, am});
			gr[0][am] = {le[x], i-1};
			e[0][am++] = g[x];
		}
		if (y < n) {
			vb.pb({{mid1, 0}, bm});
			gr[1][bm] = {le[x], i-1};
			e[1][bm++] = g[y];
		}
	};
	
	g[n+1] = inf;
	for (int i = 0; i < k; i++) {
		s[i].insert({0, n+2*i});
		s[i].insert({(g[n+1] = inf), n+2*i+1});
	}
	for (int i = 0; i < n2; i++) {
		for (auto it : dod[i]) {
			auto p = s[ty[it]].lower_bound({g[it], it});
			int y = p->S; --p; int x = p->S;
			doo(x, y, i);
			le[x] = le[it] = i;
			s[ty[it]].insert({g[it], it});
		}
		for (auto it : rem[i]) {
			s[ty[it]].erase({g[it], it});
			auto p = s[ty[it]].lower_bound({g[it], it});
			int y = p->S; --p; int x = p->S;
			int ob[2][2] = {{x, it}, {it, y}};
			for (int j = 0; j < 2; j++) doo(ob[j][0], ob[j][1], i);
			le[x] = i;
		}
	}
	
	for (int i = 0; i < q; i++) {
		va.pb({{h[i], 0}, i});
		vb.pb({{h[i], 1}, i});
	}
	
	sort(all(va)); reverse(all(va));
	sort(all(vb));
	for (auto x : va) {
		if (x.F.S) dodaj(1, gr[0][x.S].F, gr[0][x.S].S, 0, {x.S, 0});
		else {
			int y = u[x.S]+ofs;
			while (y) {ev[0][y].pb({x.S, 1}); y /= 2;}
		}
	}
	for (auto x : vb) {
		if (!x.F.S) dodaj(1, gr[1][x.S].F, gr[1][x.S].S, 1, {x.S, 0});
		else {
			int y = u[x.S]+ofs;
			while (y) {ev[1][y].pb({x.S, 1}); y /= 2;}
		}
	}
	
	walk(1);
	
	for (int i = 0; i < q; i++) {
		cout << res[i] << "\n";
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 232532 KB Output is correct
2 Correct 87 ms 232576 KB Output is correct
3 Correct 86 ms 232532 KB Output is correct
4 Correct 87 ms 232532 KB Output is correct
5 Correct 88 ms 232788 KB Output is correct
6 Correct 88 ms 232880 KB Output is correct
7 Correct 89 ms 233044 KB Output is correct
8 Correct 89 ms 233040 KB Output is correct
9 Correct 89 ms 233008 KB Output is correct
10 Correct 88 ms 233144 KB Output is correct
11 Correct 88 ms 232788 KB Output is correct
12 Correct 90 ms 232952 KB Output is correct
13 Correct 87 ms 232916 KB Output is correct
14 Correct 88 ms 232784 KB Output is correct
15 Correct 94 ms 232872 KB Output is correct
16 Correct 88 ms 232976 KB Output is correct
17 Correct 89 ms 233040 KB Output is correct
18 Correct 91 ms 233044 KB Output is correct
19 Correct 88 ms 233036 KB Output is correct
20 Correct 88 ms 233032 KB Output is correct
21 Correct 90 ms 232788 KB Output is correct
22 Correct 89 ms 233040 KB Output is correct
23 Correct 88 ms 233044 KB Output is correct
24 Correct 91 ms 233044 KB Output is correct
25 Correct 89 ms 233044 KB Output is correct
26 Correct 88 ms 232924 KB Output is correct
27 Correct 88 ms 232852 KB Output is correct
28 Correct 88 ms 232792 KB Output is correct
29 Correct 95 ms 232928 KB Output is correct
30 Correct 88 ms 232788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 232532 KB Output is correct
2 Correct 87 ms 232576 KB Output is correct
3 Correct 86 ms 232532 KB Output is correct
4 Correct 87 ms 232532 KB Output is correct
5 Correct 88 ms 232788 KB Output is correct
6 Correct 88 ms 232880 KB Output is correct
7 Correct 89 ms 233044 KB Output is correct
8 Correct 89 ms 233040 KB Output is correct
9 Correct 89 ms 233008 KB Output is correct
10 Correct 88 ms 233144 KB Output is correct
11 Correct 88 ms 232788 KB Output is correct
12 Correct 90 ms 232952 KB Output is correct
13 Correct 87 ms 232916 KB Output is correct
14 Correct 88 ms 232784 KB Output is correct
15 Correct 94 ms 232872 KB Output is correct
16 Correct 88 ms 232976 KB Output is correct
17 Correct 89 ms 233040 KB Output is correct
18 Correct 91 ms 233044 KB Output is correct
19 Correct 88 ms 233036 KB Output is correct
20 Correct 88 ms 233032 KB Output is correct
21 Correct 90 ms 232788 KB Output is correct
22 Correct 89 ms 233040 KB Output is correct
23 Correct 88 ms 233044 KB Output is correct
24 Correct 91 ms 233044 KB Output is correct
25 Correct 89 ms 233044 KB Output is correct
26 Correct 88 ms 232924 KB Output is correct
27 Correct 88 ms 232852 KB Output is correct
28 Correct 88 ms 232792 KB Output is correct
29 Correct 95 ms 232928 KB Output is correct
30 Correct 88 ms 232788 KB Output is correct
31 Correct 649 ms 338828 KB Output is correct
32 Correct 263 ms 271944 KB Output is correct
33 Correct 638 ms 331832 KB Output is correct
34 Correct 653 ms 330416 KB Output is correct
35 Correct 644 ms 338776 KB Output is correct
36 Correct 678 ms 338596 KB Output is correct
37 Correct 524 ms 324312 KB Output is correct
38 Correct 515 ms 324456 KB Output is correct
39 Correct 489 ms 312420 KB Output is correct
40 Correct 462 ms 315172 KB Output is correct
41 Correct 475 ms 309356 KB Output is correct
42 Correct 487 ms 309528 KB Output is correct
43 Correct 194 ms 268400 KB Output is correct
44 Correct 471 ms 307468 KB Output is correct
45 Correct 450 ms 303644 KB Output is correct
46 Correct 388 ms 295196 KB Output is correct
47 Correct 317 ms 294476 KB Output is correct
48 Correct 309 ms 292624 KB Output is correct
49 Correct 377 ms 298028 KB Output is correct
50 Correct 403 ms 305284 KB Output is correct
51 Correct 370 ms 295416 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 441476 KB Output is correct
2 Correct 1088 ms 466588 KB Output is correct
3 Correct 807 ms 470388 KB Output is correct
4 Correct 862 ms 460240 KB Output is correct
5 Correct 1080 ms 462016 KB Output is correct
6 Correct 1042 ms 459420 KB Output is correct
7 Correct 686 ms 470516 KB Output is correct
8 Correct 718 ms 459740 KB Output is correct
9 Correct 843 ms 460884 KB Output is correct
10 Correct 985 ms 470416 KB Output is correct
11 Correct 815 ms 458808 KB Output is correct
12 Correct 881 ms 465260 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3171 ms 695740 KB Output is correct
2 Correct 1089 ms 463292 KB Output is correct
3 Correct 2992 ms 702144 KB Output is correct
4 Correct 1816 ms 625748 KB Output is correct
5 Correct 2569 ms 672800 KB Output is correct
6 Correct 2492 ms 663284 KB Output is correct
7 Correct 2815 ms 704948 KB Output is correct
8 Correct 2811 ms 704832 KB Output is correct
9 Correct 1479 ms 621544 KB Output is correct
10 Correct 2236 ms 666536 KB Output is correct
11 Correct 2827 ms 690112 KB Output is correct
12 Correct 2893 ms 705556 KB Output is correct
13 Correct 1517 ms 657848 KB Output is correct
14 Correct 1460 ms 655628 KB Output is correct
15 Correct 1708 ms 671680 KB Output is correct
16 Correct 1854 ms 682936 KB Output is correct
17 Correct 1748 ms 676536 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 232532 KB Output is correct
2 Correct 87 ms 232576 KB Output is correct
3 Correct 86 ms 232532 KB Output is correct
4 Correct 87 ms 232532 KB Output is correct
5 Correct 88 ms 232788 KB Output is correct
6 Correct 88 ms 232880 KB Output is correct
7 Correct 89 ms 233044 KB Output is correct
8 Correct 89 ms 233040 KB Output is correct
9 Correct 89 ms 233008 KB Output is correct
10 Correct 88 ms 233144 KB Output is correct
11 Correct 88 ms 232788 KB Output is correct
12 Correct 90 ms 232952 KB Output is correct
13 Correct 87 ms 232916 KB Output is correct
14 Correct 88 ms 232784 KB Output is correct
15 Correct 94 ms 232872 KB Output is correct
16 Correct 88 ms 232976 KB Output is correct
17 Correct 89 ms 233040 KB Output is correct
18 Correct 91 ms 233044 KB Output is correct
19 Correct 88 ms 233036 KB Output is correct
20 Correct 88 ms 233032 KB Output is correct
21 Correct 90 ms 232788 KB Output is correct
22 Correct 89 ms 233040 KB Output is correct
23 Correct 88 ms 233044 KB Output is correct
24 Correct 91 ms 233044 KB Output is correct
25 Correct 89 ms 233044 KB Output is correct
26 Correct 88 ms 232924 KB Output is correct
27 Correct 88 ms 232852 KB Output is correct
28 Correct 88 ms 232792 KB Output is correct
29 Correct 95 ms 232928 KB Output is correct
30 Correct 88 ms 232788 KB Output is correct
31 Correct 649 ms 338828 KB Output is correct
32 Correct 263 ms 271944 KB Output is correct
33 Correct 638 ms 331832 KB Output is correct
34 Correct 653 ms 330416 KB Output is correct
35 Correct 644 ms 338776 KB Output is correct
36 Correct 678 ms 338596 KB Output is correct
37 Correct 524 ms 324312 KB Output is correct
38 Correct 515 ms 324456 KB Output is correct
39 Correct 489 ms 312420 KB Output is correct
40 Correct 462 ms 315172 KB Output is correct
41 Correct 475 ms 309356 KB Output is correct
42 Correct 487 ms 309528 KB Output is correct
43 Correct 194 ms 268400 KB Output is correct
44 Correct 471 ms 307468 KB Output is correct
45 Correct 450 ms 303644 KB Output is correct
46 Correct 388 ms 295196 KB Output is correct
47 Correct 317 ms 294476 KB Output is correct
48 Correct 309 ms 292624 KB Output is correct
49 Correct 377 ms 298028 KB Output is correct
50 Correct 403 ms 305284 KB Output is correct
51 Correct 370 ms 295416 KB Output is correct
52 Correct 438 ms 306224 KB Output is correct
53 Correct 426 ms 305204 KB Output is correct
54 Correct 542 ms 318636 KB Output is correct
55 Correct 470 ms 307268 KB Output is correct
56 Correct 462 ms 307556 KB Output is correct
57 Correct 493 ms 309284 KB Output is correct
58 Correct 492 ms 308908 KB Output is correct
59 Correct 494 ms 310184 KB Output is correct
60 Correct 503 ms 309784 KB Output is correct
61 Correct 186 ms 272060 KB Output is correct
62 Correct 411 ms 307060 KB Output is correct
63 Correct 511 ms 313452 KB Output is correct
64 Correct 523 ms 316332 KB Output is correct
65 Correct 544 ms 317356 KB Output is correct
66 Correct 547 ms 311668 KB Output is correct
67 Correct 242 ms 273472 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 232532 KB Output is correct
2 Correct 87 ms 232576 KB Output is correct
3 Correct 86 ms 232532 KB Output is correct
4 Correct 87 ms 232532 KB Output is correct
5 Correct 88 ms 232788 KB Output is correct
6 Correct 88 ms 232880 KB Output is correct
7 Correct 89 ms 233044 KB Output is correct
8 Correct 89 ms 233040 KB Output is correct
9 Correct 89 ms 233008 KB Output is correct
10 Correct 88 ms 233144 KB Output is correct
11 Correct 88 ms 232788 KB Output is correct
12 Correct 90 ms 232952 KB Output is correct
13 Correct 87 ms 232916 KB Output is correct
14 Correct 88 ms 232784 KB Output is correct
15 Correct 94 ms 232872 KB Output is correct
16 Correct 88 ms 232976 KB Output is correct
17 Correct 89 ms 233040 KB Output is correct
18 Correct 91 ms 233044 KB Output is correct
19 Correct 88 ms 233036 KB Output is correct
20 Correct 88 ms 233032 KB Output is correct
21 Correct 90 ms 232788 KB Output is correct
22 Correct 89 ms 233040 KB Output is correct
23 Correct 88 ms 233044 KB Output is correct
24 Correct 91 ms 233044 KB Output is correct
25 Correct 89 ms 233044 KB Output is correct
26 Correct 88 ms 232924 KB Output is correct
27 Correct 88 ms 232852 KB Output is correct
28 Correct 88 ms 232792 KB Output is correct
29 Correct 95 ms 232928 KB Output is correct
30 Correct 88 ms 232788 KB Output is correct
31 Correct 649 ms 338828 KB Output is correct
32 Correct 263 ms 271944 KB Output is correct
33 Correct 638 ms 331832 KB Output is correct
34 Correct 653 ms 330416 KB Output is correct
35 Correct 644 ms 338776 KB Output is correct
36 Correct 678 ms 338596 KB Output is correct
37 Correct 524 ms 324312 KB Output is correct
38 Correct 515 ms 324456 KB Output is correct
39 Correct 489 ms 312420 KB Output is correct
40 Correct 462 ms 315172 KB Output is correct
41 Correct 475 ms 309356 KB Output is correct
42 Correct 487 ms 309528 KB Output is correct
43 Correct 194 ms 268400 KB Output is correct
44 Correct 471 ms 307468 KB Output is correct
45 Correct 450 ms 303644 KB Output is correct
46 Correct 388 ms 295196 KB Output is correct
47 Correct 317 ms 294476 KB Output is correct
48 Correct 309 ms 292624 KB Output is correct
49 Correct 377 ms 298028 KB Output is correct
50 Correct 403 ms 305284 KB Output is correct
51 Correct 370 ms 295416 KB Output is correct
52 Correct 849 ms 441476 KB Output is correct
53 Correct 1088 ms 466588 KB Output is correct
54 Correct 807 ms 470388 KB Output is correct
55 Correct 862 ms 460240 KB Output is correct
56 Correct 1080 ms 462016 KB Output is correct
57 Correct 1042 ms 459420 KB Output is correct
58 Correct 686 ms 470516 KB Output is correct
59 Correct 718 ms 459740 KB Output is correct
60 Correct 843 ms 460884 KB Output is correct
61 Correct 985 ms 470416 KB Output is correct
62 Correct 815 ms 458808 KB Output is correct
63 Correct 881 ms 465260 KB Output is correct
64 Correct 3171 ms 695740 KB Output is correct
65 Correct 1089 ms 463292 KB Output is correct
66 Correct 2992 ms 702144 KB Output is correct
67 Correct 1816 ms 625748 KB Output is correct
68 Correct 2569 ms 672800 KB Output is correct
69 Correct 2492 ms 663284 KB Output is correct
70 Correct 2815 ms 704948 KB Output is correct
71 Correct 2811 ms 704832 KB Output is correct
72 Correct 1479 ms 621544 KB Output is correct
73 Correct 2236 ms 666536 KB Output is correct
74 Correct 2827 ms 690112 KB Output is correct
75 Correct 2893 ms 705556 KB Output is correct
76 Correct 1517 ms 657848 KB Output is correct
77 Correct 1460 ms 655628 KB Output is correct
78 Correct 1708 ms 671680 KB Output is correct
79 Correct 1854 ms 682936 KB Output is correct
80 Correct 1748 ms 676536 KB Output is correct
81 Correct 438 ms 306224 KB Output is correct
82 Correct 426 ms 305204 KB Output is correct
83 Correct 542 ms 318636 KB Output is correct
84 Correct 470 ms 307268 KB Output is correct
85 Correct 462 ms 307556 KB Output is correct
86 Correct 493 ms 309284 KB Output is correct
87 Correct 492 ms 308908 KB Output is correct
88 Correct 494 ms 310184 KB Output is correct
89 Correct 503 ms 309784 KB Output is correct
90 Correct 186 ms 272060 KB Output is correct
91 Correct 411 ms 307060 KB Output is correct
92 Correct 511 ms 313452 KB Output is correct
93 Correct 523 ms 316332 KB Output is correct
94 Correct 544 ms 317356 KB Output is correct
95 Correct 547 ms 311668 KB Output is correct
96 Correct 242 ms 273472 KB Output is correct
97 Correct 2501 ms 620276 KB Output is correct
98 Correct 1047 ms 460916 KB Output is correct
99 Correct 4297 ms 772200 KB Output is correct
100 Correct 2536 ms 611184 KB Output is correct
101 Correct 3340 ms 696616 KB Output is correct
102 Correct 4342 ms 811916 KB Output is correct
103 Correct 3030 ms 734420 KB Output is correct
104 Correct 3026 ms 734608 KB Output is correct
105 Correct 2456 ms 681784 KB Output is correct
106 Correct 2489 ms 693856 KB Output is correct
107 Correct 2696 ms 617508 KB Output is correct
108 Correct 2488 ms 623512 KB Output is correct
109 Correct 3071 ms 637016 KB Output is correct
110 Correct 2929 ms 632124 KB Output is correct
111 Correct 2928 ms 639672 KB Output is correct
112 Correct 3241 ms 640384 KB Output is correct
113 Correct 578 ms 468980 KB Output is correct
114 Correct 2292 ms 620528 KB Output is correct
115 Correct 3227 ms 661308 KB Output is correct
116 Correct 3289 ms 676980 KB Output is correct
117 Correct 3459 ms 683912 KB Output is correct
118 Correct 3398 ms 655092 KB Output is correct
119 Correct 901 ms 459892 KB Output is correct
120 Correct 1377 ms 527848 KB Output is correct
121 Correct 1608 ms 555852 KB Output is correct
122 Correct 1440 ms 543160 KB Output is correct
123 Correct 1815 ms 569292 KB Output is correct
124 Correct 2123 ms 609316 KB Output is correct
125 Correct 1737 ms 557840 KB Output is correct
126 Correct 2124 ms 629600 KB Output is correct