| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1046881 |
2024-08-07T05:41:09 Z |
정민찬(#11024) |
Sweeping (JOI20_sweeping) |
C++17 |
|
10462 ms |
2097152 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, 0});
}
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, 0});
}
if (tree[node].r == -1) {
tree[node].r = tree.size();
tree.push_back({-1, -1, 0});
}
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 0;
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;
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);
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) {
X.push_back(N - qrs[i][1]);
Y.push_back(qrs[i][1]);
}
else if (qrs[i][0] == 3) {
Y.push_back(N - qrs[i][1]);
X.push_back(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());
int MX = X.size(), MY = Y.size();
set<int> sX, sY;
sX.insert(-1);
sY.insert(-1);
segX.init(MY, MX);
segY.init(MX, MY);
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];
auto it = sX.lower_bound(N-L);
it --;
int yi = lower_bound(Y.begin(), Y.end(), L) - Y.begin() + 1;
int li = upper_bound(X.begin(), X.end(), *it) - X.begin() + 1;
int ri = lower_bound(X.begin(), X.end(), N-L) - X.begin() + 1;
segX.update(1, 1, MY, yi, li, ri, N-L);
sY.insert(L);
}
else if (qrs[i][0] == 3) { // V
int L = qrs[i][1];
auto it = sY.lower_bound(N-L);
it --;
int xi = lower_bound(X.begin(), X.end(), L) - X.begin() + 1;
int li = upper_bound(Y.begin(), Y.end(), *it) - Y.begin() + 1;
int ri = lower_bound(Y.begin(), Y.end(), N-L) - Y.begin() + 1;
segY.update(1, 1, MX, xi, li, ri, N-L);
sX.insert(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 |
7 ms |
3676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8582 ms |
1539704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10462 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10462 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
