oj.uz

Submission #1071720

# Submission time Handle Problem Language Result Execution time Memory
1071720 2024-08-23T10:26:57 Z Tob New Home (APIO18_new_home) C++14
0 / 100
 2465 ms 561304 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[2*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 nn1 = 1, 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 z, 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});
		s[i].insert({(g[n+1] = inf), n+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, it, 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], it, 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 dodaj(1, u[x.S], u[x.S], 0, {x.S, 1});
	}
	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 dodaj(1, u[x.S], u[x.S], 1, {x.S, 1});
	}
	
	walk(1);
	
	for (int i = 0; i < q; i++) {
		cout << res[i] << "\n";
	}

	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:62:6: warning: unused variable 'nn1' [-Wunused-variable]
   62 |  int nn1 = 1, nn2 = 1;
      |      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 232528 KB Output is correct
2 Correct 91 ms 232400 KB Output is correct
3 Correct 96 ms 232528 KB Output is correct
4 Incorrect 100 ms 232488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 232528 KB Output is correct
2 Correct 91 ms 232400 KB Output is correct
3 Correct 96 ms 232528 KB Output is correct
4 Incorrect 100 ms 232488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 232528 KB Output is correct
2 Correct 91 ms 232400 KB Output is correct
3 Correct 96 ms 232528 KB Output is correct
4 Incorrect 100 ms 232488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 232528 KB Output is correct
2 Correct 91 ms 232400 KB Output is correct
3 Correct 96 ms 232528 KB Output is correct
4 Incorrect 100 ms 232488 KB Output isn't correct
5 Halted 0 ms 0 KB -