| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 616987 |
2022-08-01T08:05:07 Z |
박상훈(#8502) |
Sweeping (JOI20_sweeping) |
C++17 |
|
18000 ms |
66544 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
namespace I{
vector<int> X, Y, T, A, B;
}
struct Seg{
int tree[4400400], lazy[4400400];
void propagate(int i, int l, int r){
tree[i] = max(tree[i], lazy[i]);
if (l!=r){
lazy[i<<1] = max(lazy[i<<1], lazy[i]);
lazy[i<<1|1] = max(lazy[i<<1|1], lazy[i]);
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x, bool flag = 0){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
if (flag) {tree[i] = x; return;}
lazy[i] = x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x, flag); update(i<<1|1, m+1, r, s, e, x, flag);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
int query(int i, int l, int r, int s){
propagate(i, l, r);
if (r<s || s<l) return 0;
if (l==r) return tree[i];
int m = (l+r)>>1;
return max(query(i<<1, l, m, s), query(i<<1|1, m+1, r, s));
}
int left_bound(int i, int l, int r, int x){
propagate(i, l, r);
if (tree[i] <= x) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int ret = left_bound(i<<1, l, m, x);
if (ret!=-1) return ret;
return left_bound(i<<1|1, m+1, r, x);
}
int right_bound(int i, int l, int r, int x){
propagate(i, l, r);
if (tree[i] <= x) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int ret = right_bound(i<<1|1, m+1, r, x);
if (ret!=-1) return ret;
return right_bound(i<<1, l, m, x);
}
}treex, treey;
struct Node{
int x, y, i;
Node(){}
Node(int _x, int _y, int _i): x(_x), y(_y), i(_i) {}
bool operator < (const Node &N) const{
return tie(y, x, i) < tie(N.y, N.x, N.i);
}
};
int n, q, pos[2002000];
vector<int> X, Y;
void compress(vector<int> &X){sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());}
int getidx(const vector<int> &a, int x) {return lower_bound(a.begin(), a.end(), x) - a.begin();}
void input(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
X.push_back(-2e9);
X.push_back(2e9);
Y.push_back(-2e9);
Y.push_back(2e9);
int d;
cin >> d >> n >> q;
I::X.resize(n+1);
I::Y.resize(n+1);
I::T.resize(q+1);
I::A.resize(q+1);
I::B.resize(q+1);
vector<Node> tmp;
for (int i=1;i<=n;i++){
cin >> I::X[i] >> I::Y[i];
X.push_back(I::X[i]);
Y.push_back(I::Y[i]);
tmp.emplace_back(I::X[i], I::Y[i], i);
}
for (int i=1;i<=q;i++){
cin >> I::T[i] >> I::A[i];
if (I::T[i]==4){
cin >> I::B[i];
++n;
tmp.emplace_back(I::A[i], I::B[i], n);
}
else if (I::T[i]==2){
I::B[i] = I::A[i];
I::A[i] = d-I::A[i];
}
else if (I::T[i]==3){
I::B[i] = d-I::A[i];
}
if (I::T[i]>=2){
X.push_back(I::A[i]);
Y.push_back(I::B[i]);
}
}
compress(X); compress(Y);
for (int i=1;i<=(int)I::X.size()-1;i++){
I::X[i] = getidx(X, I::X[i]);
I::Y[i] = getidx(Y, I::Y[i]);
}
for (int i=1;i<=q;i++){
if (I::T[i]>=2){
I::A[i] = getidx(X, I::A[i]);
I::B[i] = getidx(Y, I::B[i]);
}
}
///
/*for (int i=1;i<=n;i++){
treex.update(1, 1, n, i, i, I::X[i]);
treey.update(1, 1, n, i, i, I::Y[i]);
}*/
sort(tmp.begin(), tmp.end());
for (int i=0;i<n;i++){
tmp[i].x = getidx(X, tmp[i].x);
tmp[i].y = getidx(Y, tmp[i].y);
treex.update(1, 1, n, i+1, i+1, tmp[i].x);
treey.update(1, 1, n, i+1, i+1, tmp[i].y);
pos[tmp[i].i] = i+1;
//printf(" init %d -> %d %d\n", i+1, X[tmp[i].x], Y[tmp[i].y]);
}
}
int main(){
input();
int cnt = I::X.size();
for (int i=1;i<=q;i++){
int t = I::T[i], u = I::A[i], v = I::B[i];
if (t==1){
printf("%d %d\n", X[treex.query(1, 1, n, pos[u])], Y[treey.query(1, 1, n, pos[u])]);
continue;
}
else if (t==4){
treex.update(1, 1, n, pos[cnt], pos[cnt], u, 1);
treey.update(1, 1, n, pos[cnt], pos[cnt], v, 1);
//printf(" %d(%d) -> %d\n", cnt, pos[cnt], X[treex.query(1, 1, n, pos[cnt])]);
++cnt;
continue;
}
for (int j=1;j<=n;j++) if (treex.query(1, 1, n, j) <= u && treey.query(1, 1, n, j) <= v){
if (t==2) treex.update(1, 1, n, j, j, u);
else treey.update(1, 1, n, j, j, v);
}
/*int l = 1;
int r = treey.left_bound(1, 1, n, v)-1;
if (r==-2) r = n;
treex.update(1, 1, n, l, r, u);
//printf("l = %d, r = %d\n", l, r);
/*if (l>r) continue;
if (t==2){
treex.update(1, 1, n, l, r, u);
}
if (t==3){
treey.update(1, 1, n, l, r, v);
}*/
}
return 0;
}
Compilation message
sweeping.cpp:185:9: warning: "/*" within comment [-Wcomment]
185 | /*if (l>r) continue;
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
631 ms |
844 KB |
Output is correct |
| 2 |
Correct |
278 ms |
600 KB |
Output is correct |
| 3 |
Correct |
7 ms |
788 KB |
Output is correct |
| 4 |
Correct |
543 ms |
916 KB |
Output is correct |
| 5 |
Correct |
2539 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1072 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18028 ms |
66544 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18093 ms |
48492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18093 ms |
48492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
631 ms |
844 KB |
Output is correct |
| 2 |
Correct |
278 ms |
600 KB |
Output is correct |
| 3 |
Correct |
7 ms |
788 KB |
Output is correct |
| 4 |
Correct |
543 ms |
916 KB |
Output is correct |
| 5 |
Correct |
2539 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1072 ms |
612 KB |
Output is correct |
| 7 |
Execution timed out |
18028 ms |
66544 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
