| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1070899 |
2024-08-22T20:33:22 Z |
Tob |
New Home (APIO18_new_home) |
C++14 |
|
5000 ms |
597932 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), C = 5e7, inf = 2e9;
int n, k, q, cnt, cur, sad;
int a[N], b[N], g[N], ty[N], h[N], u[N], aa[N], bb[2*N], res[N], bl[4*N], fr[N], le[2*N];
int t[2][2*ofs], ch[C][2];
vector <int> qu[ofs], addk[ofs], remk[ofs], dod[2*N], rem[2*N];
set <pii> s[N];
struct node {
int l, r, d, type;
};
vector <node> ad[2*ofs];
void change(int x, int o, int val) {
ch[cnt][0] = 2*x+o;
ch[cnt][1] = t[o][x];
t[o][x] = val;
cnt++;
}
int add(int x, int a, int b, int o, int val, int lo = 0, int hi = ofs-1) {
if (b < lo || hi < a) return 0;
int mid = (lo + hi) / 2, ha = o*((hi-lo)/2+1);
if (a <= lo && hi <= b) {
if (t[o][x] >= val) {
change(x, o, val);
return 0;
}
if (lo == hi) return 1;
if (add(2*x^o^1, a, b, o, val, mid+1-ha, hi-ha)) return 1;
add(2*x^o, a, b, o, val, lo+ha, mid+ha);
return 1;
}
if (add(2*x^o^1, a, b, o, val, mid+1-ha, hi-ha)) return 1;
if (add(2*x^o, a, b, o, val, lo+ha, mid+ha)) return 1;
change(x, o, min(t[o][2*x], t[o][2*x+1]));
return 0;
}
int query(int x, int a, int o, int val = -inf, int lo = 0, int hi = ofs-1) {
if (t[o][x] != inf) val = max(val, t[o][x]);
if (lo == hi) return val;
int mid = (lo + hi) / 2;
if (a <= mid) return query(2*x, a, o, val, lo, mid);
return query(2*x+1, a, o, val, mid+1, hi);
}
void walk(int x) {
for (auto it : ad[x]) {
int ccnt = cnt;
if (it.l <= it.r) add(1, it.l, it.r, it.type, it.d);
ccnt = cnt-ccnt;
bl[cur++] = ccnt;
}
if (x-ofs > 2*n);
else 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]) {
int pos = aa[h[y]];
if (sad != k) res[y] = -1;
else res[y] = max(pos-query(1, h[y], 0), -query(1, h[y], 1)-pos);
}
}
else {
walk(2*x);
walk(2*x+1);
}
for (int i = ad[x].size(); i; i--, cur--)
for (int j = 0; j < bl[cur-1]; j++, cnt--)
t[ch[cnt-1][0]&1][ch[cnt-1][0]>>1] = ch[cnt-1][1];
}
void dodaj(int x, int a, int b, node nn, int lo = 0, int hi = ofs-1) {
if (b < lo || hi < a || a > b) return;
if (a <= lo && hi <= b) {
ad[x].pb(nn);
return;
}
int mid = (lo + hi) / 2;
dodaj(2*x, a, b, nn, lo, mid);
dodaj(2*x+1, a, b, nn, 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]--;
aa[nn1++] = g[i];
bb[nn2++] = a[i];
bb[nn2++] = b[i];
}
for (int i = 0; i < q; i++) {
cin >> h[i] >> u[i];
aa[nn1++] = h[i];
}
sort(aa, aa+nn1);
sort(bb, bb+nn2);
int n1 = 1, n2 = 1;
for (int i = 1; i < nn1; i++) if (aa[i] != aa[n1-1]) aa[n1++] = aa[i];
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++) {
h[i] = upper_bound(aa, aa+n1, h[i])-aa-1;
u[i] = upper_bound(bb, bb+n2, u[i])-bb-1;
qu[u[i]].pb(i);
}
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) {
mid = upper_bound(aa, aa+n1, mid)-aa-1;
node na = {0, mid, g[x], 0};
dodaj(1, le[x], i-1, na);
}
if (y < n) {
mid1 = lower_bound(aa, aa+n1, mid1)-aa;
node nb = {mid1, ofs-1, -g[y], 1};
dodaj(1, le[x], i-1, nb);
}
};
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;
}
}
walk(1);
for (int i = 0; i < q; i++) {
cout << res[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
183308 KB |
Output is correct |
| 2 |
Correct |
58 ms |
183124 KB |
Output is correct |
| 3 |
Correct |
52 ms |
183120 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
183136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
183308 KB |
Output is correct |
| 2 |
Correct |
58 ms |
183124 KB |
Output is correct |
| 3 |
Correct |
52 ms |
183120 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
183136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
696 ms |
246552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5041 ms |
597932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
183308 KB |
Output is correct |
| 2 |
Correct |
58 ms |
183124 KB |
Output is correct |
| 3 |
Correct |
52 ms |
183120 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
183136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
183308 KB |
Output is correct |
| 2 |
Correct |
58 ms |
183124 KB |
Output is correct |
| 3 |
Correct |
52 ms |
183120 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
183136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
