QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#106372 | #3554. Sweeping | bashkort# | 0 | 879ms | 60704kb | C++20 | 4.6kb | 2023-05-17 15:37:48 | 2024-05-31 13:39:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int inf = 1e9 + 7;
mt19937 rnd(228);
void ckmax(int &x, int y) {
if (x < y) {
x = y;
}
}
struct Node {
int prior = 0, sz = 0;
int x = 0, y = 0, mxy = 0, mny = inf;
int pushx = -1, pushy = -1;
int L = 0, R = 0, par = 0;
Node() = default;
Node(int prior, int x, int y, int siz) : prior(prior), x(x), y(y), sz(siz), mxy(y), mny(inf) {}
};
vector<Node> t{{}};
int create(Node b = Node()) {
t.emplace_back(b);
return t.size() - 1;
}
void apply(int p, int pushx, int pushy) {
if (p == 0) {
return;
}
ckmax(t[p].x, pushx);
ckmax(t[p].pushx, pushx);
ckmax(t[p].y, pushy);
ckmax(t[p].pushy, pushy);
ckmax(t[p].mxy, t[p].y);
ckmax(t[p].mny, pushy);
}
void push(int x) {
for (int p : {t[x].L, t[x].R}) {
apply(p, t[x].pushx, t[x].pushy);
}
t[x].pushx = t[x].pushy = -1;
}
void pull(int x) {
t[x].sz = 1 + t[t[x].L].sz + t[t[x].R].sz;
t[x].mxy = max({t[x].y, t[t[x].L].y, t[t[x].R].y});
t[x].mny = min({t[x].y, t[t[x].L].y, t[t[x].R].y});
for (int p : {t[x].L, t[x].R}) {
if (p) {
t[p].par = x;
}
}
}
int merge(int l, int r) {
if (!l || !r) {
return l ^ r;
}
push(l), push(r);
if (t[l].prior > t[r].prior) {
t[l].R = merge(t[l].R, r);
pull(l);
return l;
} else {
t[r].L = merge(l, t[r].L);
pull(r);
return r;
}
}
//key <= k
pair<int, int> split_x(int x, int k) {
if (!x) {
return {};
}
t[x].par = 0;
push(x);
if (t[x].x > k) {
auto se = split_x(t[x].L, k);
t[x].L = se.second;
pull(x);
return {se.first, x};
} else {
auto se = split_x(t[x].R, k);
t[x].R = se.first;
pull(x);
return {x, se.second};
}
}
int super_merge(int x, int y) {
t[x].par = t[y].par = 0;
if (!x || !y) {
return x ^ y;
}
push(x), push(y);
if (t[x].prior < t[y].prior) {
swap(x, y);
}
auto [l, r] = split_x(y, t[x].x);
t[x].L = super_merge(t[x].L, l);
t[x].R = super_merge(t[x].R, r);
pull(x);
return x;
}
//left.y <= k
pair<int, int> split_y(int x, int k) {
t[x].par = 0;
if (!x || t[x].mxy <= k) {
return {x, 0};
} else if (t[x].mny > k) {
return {0, x};
}
push(x);
auto [ly, lx] = split_y(t[x].L, k);
auto [ry, rx] = split_y(t[x].R, k);
if (t[x].y <= k) {
t[x].L = ly, t[x].R = ry;
pull(x);
return {x, merge(lx, rx)};
} else {
t[x].L = lx, t[x].R = rx;
pull(x);
return {merge(ly, ry), x};
}
}
pair<int, int> getValue(int x) {
int px = t[x].x, py = t[x].y;
while (x > 0) {
ckmax(px, t[x].pushx);
ckmax(py, t[x].pushy);
x = t[x].par;
}
return {px, py};
}
void debug_node(int x, string pref = "") {
if (!x) {
return;
}
pref += "->" + to_string(x);
debug_node(t[x].L, pref);
cout << pref << endl;
debug_node(t[x].R, pref);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> pos(m + q);
int root = 0;
vector<int> X(m), Y(m), ord(m);
for (int i = 0; i < m; ++i) {
cin >> X[i] >> Y[i];
}
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return X[i] < X[j];
});
for (int i : ord) {
int x = X[i], y = Y[i];
pos[i] = create(Node(rnd(), x, y, 1));
root = merge(root, pos[i]);
}
for (int qwq = 1; qwq <= q; ++qwq) {
int T;
cin >> T;
if (T == 1) {
int p;
cin >> p;
auto [x, y] = getValue(pos[p - 1]);
cout << x << " " << y << '\n';
} else if (T == 2) {
int H;
cin >> H;
auto [l, r] = split_y(root, H);
apply(l, n - H, 0);
root = super_merge(l, r);
} else if (T == 3) {
int V;
cin >> V;
auto [l, r] = split_x(root, V);
apply(l, 0, n - V);
root = merge(l, r);
} else {
int x, y;
cin >> x >> y;
pos[m] = create(Node(rnd(), x, y, 1));
auto [l, r] = split_x(root, x);
root = merge(l, merge(pos[m], r));
m += 1;
}
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 1
Accepted
time: 4ms
memory: 3756kb
input:
999999999 2000 5000 406191928 499382196 562579162 405324970 758918451 226610082 56425557 481714604 280111172 204083332 178122667 423322594 656895843 125933171 283229448 255332800 375268656 368221716 287124150 218833686 67804037 252992256 736660159 61831334 50624783 762562411 127286172 739867871 2174...
output:
703152954 155393653 568874648 274309686 58956946 596540151 199070534 583395188 373137208 583395188 196862582 704927063 601883225 329807019 487677860 204843014 661256159 204843014 751624518 204843014 174003214 771291775 770471768 204843014 256547879 588907149 36478325 753856112 175794127 588907149 25...
result:
ok 3000 lines
Test #2:
score: -1
Wrong Answer
time: 2ms
memory: 3972kb
input:
934679943 1 5000 2451044 877564810 1 1 1 1 1 1 1 1 1 1 4 120526175 461368727 1 1 1 2 3 450149653 3 620864342 2 178195071 1 1 1 2 1 2 3 413010769 1 2 1 2 1 2 1 2 1 1 2 725221136 3 691448934 3 276663052 1 1 3 930831455 2 815181543 2 623177099 1 2 2 514825170 1 2 3 747856152 1 2 3 402313938 1 2 1 2 1 2...
output:
2451044 877564810 2451044 877564810 2451044 877564810 2451044 877564810 2451044 877564810 2451044 877564810 120526175 461368727 2451044 877564810 120526175 484530290 120526175 484530290 120526175 521669174 120526175 521669174 120526175 521669174 120526175 521669174 2451044 877564810 2451044 87756481...
result:
wrong answer 33rd lines differ - expected: '34758954 877564810', found: '70935022 877564810'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 879ms
memory: 60704kb
input:
1000000000 500000 1000000 565671866 434313351 151160620 848839277 759673958 240326022 747919325 251939968 652216454 341792707 697972826 302025968 437943290 562056699 963595717 25130832 833492450 163447023 453783218 546216655 852488265 147511733 364464144 334147914 493873353 504061372 104992045 86556...
output:
993267240 6732751 500002500 684811456 500002500 922437952 500002500 512724930 500002500 836886041 572132261 427866716 500002500 65762937 500002500 77683574 500002500 792051536 500002500 656177426 727111507 272888421 706937632 293061330 885997292 113491348 625002500 346017967 500002500 50191019 50000...
result:
wrong answer 2nd lines differ - expected: '315188472 684811456', found: '500002500 684811456'
Subtask #3:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 749ms
memory: 37464kb
input:
1000000000 499999 1000000 1603 999995752 1621 999984188 3408 999983654 3743 999979285 3830 999978594 5050 999974201 7426 999970241 13957 999962424 14611 999962335 16341 999954169 20684 999953545 21401 999952737 25492 999948443 25736 999946928 26128 999941492 29341 999937495 29753 999929827 33929 999...
output:
311900542 626076836 353587097 582311003 135154605 823201952 88429068 879554432 716432267 229484324 157875583 797283755 190850826 758913803 902622474 90110001 364184898 571623281 653250000 299154784 765108248 185504610 673610863 281598001 842597328 118664505 70986711 901272703 451418581 481766999 431...
result:
wrong answer 7th lines differ - expected: '196566000 758913803', found: '190850826 758913803'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%