| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 218042 |
2020-03-31T17:20:03 Z |
Akashi |
Sweeping (JOI20_sweeping) |
C++14 |
|
18000 ms |
97108 KB |
#include <bits/stdc++.h>
using namespace std;
struct query{
int tip, x, y;
};
query a[1500005];
int where[1500005];
struct min_max{
vector <int> label;
vector <vector <int> > arb;
int parent[1500005];
void init(){
label.clear();
arb.clear();
}
void create(int x, int ind){
label.push_back(x);
arb.emplace_back();
if(ind != -1){
arb.back().push_back(ind);
parent[ind] = label.size() - 1;
}
}
void push(int x, int ind){
arb[x].push_back(ind);
parent[ind] = x;
}
int merge(int x, int y){
if(arb[x].size() < arb[y].size()) swap(x, y);
for(auto ind : arb[y]){
if(where[ind]) continue ;
push(x, ind);
}
label[x] = max(label[x], label[y]);
return x;
}
int find(int ind){
return label[parent[ind]];
}
};
min_max xCords, yCords;
int n, m, q;
pair <int, int> ans[1500005];
priority_queue <pair <int, int>, vector <pair <int, int> > , greater <pair <int, int> > > pqX, pqY;
void solve(int x, int y, vector <int> op){
int dif = n - x - y;
if(dif == 0){
for(auto i : op)
if(a[i].tip == 1)
ans[i] = {x, y};
return ;
}
int X = x + (dif + 1) / 2, Y = y + dif / 2 + 1;
vector <int> opX, opY;
sort(op.begin(), op.end());
xCords.init(); yCords.init();
for(auto i : op){
if(a[i].tip == 1){
if(where[a[i].x]){
if(where[a[i].x] == 1) opX.push_back(i);
else opY.push_back(i);
}
else ans[i] = {xCords.find(a[i].x), yCords.find(a[i].x)};
}
else if(a[i].tip == 4){
if(a[i].x >= X){
where[i] = 1;
opX.push_back(i);
}
else if(a[i].y >= Y){
where[i] = 2;
opY.push_back(i);
}
else{
where[i] = 0;
xCords.create(a[i].x, i);
yCords.create(a[i].y, i);
pqX.push({a[i].x, xCords.parent[i]});
pqY.push({a[i].y, yCords.parent[i]});
}
}
else if(a[i].tip == 2){
if(n - a[i].x < X){
opY.push_back(i);
xCords.create(n - a[i].x, -1);
int ind = xCords.label.size() - 1;
while(!pqX.empty() && pqX.top().first <= n - a[i].x){
int ind2 = pqX.top().second;
pqX.pop();
ind = xCords.merge(ind, ind2);
}
pqX.push({n - a[i].x, ind});
}
else{
opX.push_back(i);
while(!pqY.empty() && pqY.top().first <= a[i].x){
int ind = pqY.top().second;
pqY.pop();
for(auto it : yCords.arb[ind]){
if(where[it]) continue ;
where[it] = 1;
opX.push_back(it);
}
}
}
}
else if(a[i].tip == 3){
if(n - a[i].x < Y){
opX.push_back(i);
yCords.create(n - a[i].x, -1);
int ind = yCords.label.size() - 1;
while(!pqY.empty() && pqY.top().first <= n - a[i].x){
int ind2 = pqY.top().second;
pqY.pop();
ind = yCords.merge(ind, ind2);
}
pqY.push({n - a[i].x, ind});
}
else{
opY.push_back(i);
while(!pqX.empty() && pqX.top().first <= a[i].x){
int ind = pqX.top().second;
pqX.pop();
for(auto it : xCords.arb[ind]){
if(where[it]) continue ;
where[it] = 2;
opY.push_back(it);
}
}
}
}
}
while(!pqX.empty()) pqX.pop();
while(!pqY.empty()) pqY.pop();
solve(X, y, opX);
solve(x, Y, opY);
}
int get_ind[1500005];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= m ; ++i){
a[i].tip = 4;
scanf("%d%d", &a[i].x, &a[i].y);
get_ind[i] = i;
}
int NR = m;
for(int i = m + 1; i <= q + m ; ++i){
scanf("%d", &a[i].tip);
scanf("%d", &a[i].x);
if(a[i].tip == 1) a[i].x = get_ind[a[i].x];
if(a[i].tip == 4){
scanf("%d", &a[i].y);
get_ind[++NR] = i;
}
}
vector <int> op;
for(int i = 1; i <= m + q ; ++i) op.push_back(i);
solve(0, 0, op);
for(int i = 1; i <= q + m ; ++i)
if(a[i].tip == 1) printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i].x, &a[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i].tip);
~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i].x);
~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:183:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i].y);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18014 ms |
1148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18101 ms |
97108 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18058 ms |
85284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18058 ms |
85284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18014 ms |
1148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
