| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1046929 |
2024-08-07T06:24:31 Z |
정민찬(#11024) |
Sweeping (JOI20_sweeping) |
C++17 |
|
9269 ms |
1797428 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
struct Node{
int l, r, val;
};
struct SegmentTree{
vector<Node> tree;
void init() {
tree.clear();
tree.push_back({-1, -1, -1});
}
void update(int node, int s, int e, int l, int r, int val) {
if (l > e || s > r) return;
if (l <= s && e <= r) {
tree[node].val = max(val, tree[node].val);
return;
}
int mid = s + e >> 1;
if (tree[node].l == -1) {
tree[node].l = tree.size();
tree.push_back({-1, -1, -1});
}
if (tree[node].r == -1) {
tree[node].r = tree.size();
tree.push_back({-1, -1, -1});
}
update(tree[node].l, s, mid, l, r, val);
update(tree[node].r, mid+1, e, l, r, val);
}
int query(int node, int s, int e, int tar) {
if (node == -1) return -1;
if (s == e) return tree[node].val;
int mid = s + e >> 1;
if (tar <= mid) return max(tree[node].val, query(tree[node].l, s, mid, tar));
return max(tree[node].val, query(tree[node].r, mid+1, e, tar));
}
};
struct SegmentTree_2D{
vector<SegmentTree> tree;
int _N, _M;
void init(int n, int m) {
int sz = 1 << __lg(n-1) + 2;
tree.resize(sz);
for (int i=1; i<sz; i++) {
tree[i].init();
}
_N = n;
_M = m;
};
void update(int node, int s, int e, int tar, int l, int r, int val) {
tree[node].update(0, 1, _M, l, r, val);
if (s == e) return;
int mid = s + e >> 1;
if (tar <= mid) update(node*2, s, mid, tar, l, r, val);
else update(node*2+1, mid+1, e, tar, l, r, val);
}
int query(int node, int s, int e, int l, int r, int k) {
if (l > e || s > r) return 0;
if (l <= s && e <= r) return tree[node].query(0, 1, _M, k);
int mid = s + e >> 1;
return max(query(node*2, s, mid, l, r, k), query(node*2+1, mid+1, e, l, r, k));
}
};
SegmentTree_2D segX, segY;
SegmentTree segX2, segY2;
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
int N, M, Q;
cin >> N >> M >> Q;
vector<pair<int,int>> a(M);
vector<int> X, Y;
for (int i=0; i<M; i++) {
cin >> a[i].first >> a[i].second;
X.push_back(a[i].first);
Y.push_back(a[i].second);
}
vector<array<int,3>> qrs(Q);
vector<int> X2, Y2;
for (int i=0; i<Q; i++) {
cin >> qrs[i][0] >> qrs[i][1];
if (qrs[i][0] == 4) {
cin >> qrs[i][2];
X.push_back(qrs[i][1]);
Y.push_back(qrs[i][2]);
}
else if (qrs[i][0] == 2) {
X2.push_back(N-qrs[i][1]);
}
else if (qrs[i][0] == 3) {
Y2.push_back(N-qrs[i][1]);
}
}
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
sort(Y.begin(), Y.end());
Y.erase(unique(Y.begin(), Y.end()), Y.end());
sort(X2.begin(), X2.end());
X2.erase(unique(X2.begin(), X2.end()), X2.end());
sort(Y2.begin(), Y2.end());
Y2.erase(unique(Y2.begin(), Y2.end()), Y2.end());
int MX = X.size(), MY = Y.size();
segX.init(MY, MX);
segY.init(MX, MY);
segX2.init();
segY2.init();
for (int i=0; i<Q; i++) {
if (qrs[i][0] == 1) {
int p = qrs[i][1];
p --;
int xi = lower_bound(X.begin(), X.end(), a[p].first) - X.begin() + 1;
int yi = lower_bound(Y.begin(), Y.end(), a[p].second) - Y.begin() + 1;
int x = segX.query(1, 1, MY, yi, MY, xi);
int y = segY.query(1, 1, MX, xi, MX, yi);
cout << max(a[p].first, x) << ' ' << max(a[p].second, y) << '\n';
}
else if (qrs[i][0] == 2) { // H
int L = qrs[i][1];
int idx = lower_bound(X2.begin(), X2.end(), N-L) - X2.begin() + 1;
int lval = segX2.query(0, 1, X2.size(), idx);
int yi = upper_bound(Y.begin(), Y.end(), L) - Y.begin();
int li = upper_bound(X.begin(), X.end(), lval) - X.begin() + 1;
int ri = upper_bound(X.begin(), X.end(), N-L) - X.begin();
if (yi && li <= ri)
segX.update(1, 1, MY, yi, li, ri, N-L);
int li2 = upper_bound(Y2.begin(), Y2.end(), L) - Y2.begin() + 1;
int ri2 = upper_bound(Y2.begin(), Y2.end(), N-(lval+1)) - Y2.begin();
if (li2 <= ri2) {
segY2.update(0, 1, Y2.size(), li2, ri2, L);
}
}
else if (qrs[i][0] == 3) { // V
int L = qrs[i][1];
int idx = lower_bound(Y2.begin(), Y2.end(), N-L) - Y2.begin() + 1;
int lval = segY2.query(0, 1, Y2.size(), idx);
int xi = upper_bound(X.begin(), X.end(), L) - X.begin();
int li = upper_bound(Y.begin(), Y.end(), lval) - Y.begin() + 1;
int ri = upper_bound(Y.begin(), Y.end(), N-L) - Y.begin();
if (xi && li <= ri)
segY.update(1, 1, MX, xi, li, ri, N-L);
int li2 = upper_bound(X2.begin(), X2.end(), L) - X2.begin() + 1;
int ri2 = upper_bound(X2.begin(), X2.end(), N-(lval+1)) - X2.begin();
if (li2 <= ri2) {
segX2.update(0, 1, X2.size(), li2, ri2, L);
}
}
else {
a.push_back({qrs[i][1], qrs[i][2]});
}
}
}
Compilation message
sweeping.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
sweeping.cpp:24:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int mid = s + e >> 1;
| ~~^~~
sweeping.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
sweeping.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = s + e >> 1;
| ~~^~~
sweeping.cpp: In member function 'void SegmentTree_2D::init(int, int)':
sweeping.cpp:49:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
49 | int sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
sweeping.cpp: In member function 'void SegmentTree_2D::update(int, int, int, int, int, int, int)':
sweeping.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = s + e >> 1;
| ~~^~~
sweeping.cpp: In member function 'int SegmentTree_2D::query(int, int, int, int, int, int)':
sweeping.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6748 ms |
1110972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8721 ms |
1309288 KB |
Output is correct |
| 2 |
Correct |
8613 ms |
1359488 KB |
Output is correct |
| 3 |
Correct |
4874 ms |
1787356 KB |
Output is correct |
| 4 |
Correct |
3189 ms |
890700 KB |
Output is correct |
| 5 |
Correct |
7864 ms |
1082736 KB |
Output is correct |
| 6 |
Correct |
8353 ms |
1221636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8721 ms |
1309288 KB |
Output is correct |
| 2 |
Correct |
8613 ms |
1359488 KB |
Output is correct |
| 3 |
Correct |
4874 ms |
1787356 KB |
Output is correct |
| 4 |
Correct |
3189 ms |
890700 KB |
Output is correct |
| 5 |
Correct |
7864 ms |
1082736 KB |
Output is correct |
| 6 |
Correct |
8353 ms |
1221636 KB |
Output is correct |
| 7 |
Correct |
9269 ms |
1357652 KB |
Output is correct |
| 8 |
Correct |
9246 ms |
1375476 KB |
Output is correct |
| 9 |
Correct |
9043 ms |
1377572 KB |
Output is correct |
| 10 |
Correct |
4941 ms |
1797428 KB |
Output is correct |
| 11 |
Correct |
3405 ms |
910296 KB |
Output is correct |
| 12 |
Correct |
8115 ms |
1097280 KB |
Output is correct |
| 13 |
Correct |
7695 ms |
1087092 KB |
Output is correct |
| 14 |
Correct |
92 ms |
20152 KB |
Output is correct |
| 15 |
Correct |
1272 ms |
74248 KB |
Output is correct |
| 16 |
Correct |
8887 ms |
1201508 KB |
Output is correct |
| 17 |
Correct |
8556 ms |
1243904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
