| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 787440 |
2023-07-19T07:49:27 Z |
반딧불(#10031) |
Hamburg Steak (JOI20_hamburg) |
C++17 |
|
350 ms |
48032 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void input();
bool check1();
bool check2();
bool check3();
bool check4();
void output();
int main(){
input();
if(!check1()) if(!check2()) if(!check3()) check4();
output();
}
int n, k;
vector<int> xCoord(1), yCoord(1);
int L[200002], R[200002], D[200002], U[200002], X, Y;
vector<pair<int, int> > ans;
void input(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
xCoord.push_back(L[i]); xCoord.push_back(R[i]);
yCoord.push_back(D[i]); yCoord.push_back(U[i]);
}
sort(xCoord.begin(), xCoord.end()); xCoord.erase(unique(xCoord.begin(), xCoord.end()), xCoord.end());
sort(yCoord.begin(), yCoord.end()); yCoord.erase(unique(yCoord.begin(), yCoord.end()), yCoord.end());
for(int i=1; i<=n; i++){
L[i] = lower_bound(xCoord.begin(), xCoord.end(), L[i]) - xCoord.begin();
R[i] = lower_bound(xCoord.begin(), xCoord.end(), R[i]) - xCoord.begin();
D[i] = lower_bound(yCoord.begin(), yCoord.end(), D[i]) - yCoord.begin();
U[i] = lower_bound(yCoord.begin(), yCoord.end(), U[i]) - yCoord.begin();
}
X = (int)xCoord.size()-1, Y = (int)yCoord.size()-1;
}
bool check1(){
int maxX = 0, maxY = 0;
for(int i=1; i<=n; i++) maxX = max(maxX, L[i]), maxY = max(maxY, D[i]);
for(int i=1; i<=n; i++){
if(maxX > R[i] || maxY > U[i]) return false;
}
ans.push_back(make_pair(maxX, maxY));
return true;
}
struct namespace2{
struct segTree{
int n;
ll a[400002], b[400002];
void init(int _n){
n = _n;
for(int i=1; i<=n; i++) a[i] = b[i] = 0;
}
void addin(int x, ll va, ll vb){
while(x<=n){
a[x]+=va, b[x]+=vb;
x+=x&-x;
}
}
void add(int l, int r, ll v){
addin(l, v, -v*(l-1));
addin(r+1, -v, v*r);
}
ll sum(int x){
int tx = x;
ll va = 0, vb = 0;
while(x){
va+=a[x], vb+=b[x];
x-=x&-x;
}
return va*tx+vb;
}
ll sum(int l, int r){
return sum(r) - sum(l-1);
}
} treeA, treeB;
struct Range{
int L, R, D, U;
Range(){
L = D = 1;
R = U = 1e9;
}
Range(int L, int R, int D, int U): L(L), R(R), D(D), U(U){}
Range operator+(const Range &r)const{
return Range(max(L,r.L), min(R,r.R), max(D,r.D), min(U,r.U));
}
bool valid(){
return L<=R && D<=U;
}
} arr[200002];
Range xLeft[400002], xRight[400002];
Range yLeft[400002], yRight[400002];
struct dat{
int where, type, val;
int l, r;
dat(){}
dat(int where, int type, int val, int l, int r): where(where), type(type), val(val), l(l), r(r){}
bool operator<(const dat &nxt)const{
if(val != nxt.val) return val<nxt.val;
return type<nxt.type;
}
};
vector<dat> vec;
bool check2(){
for(int i=1; i<=n; i++) arr[i] = Range(L[i], R[i], D[i], U[i]);
for(int i=1; i<=n; i++){
xRight[L[i]] = xRight[L[i]] + arr[i];
xLeft[R[i]] = xLeft[R[i]] + arr[i];
yRight[D[i]] = yRight[D[i]] + arr[i];
yLeft[U[i]] = yLeft[U[i]] + arr[i];
}
xLeft[0] = xRight[X+1] = yLeft[0] = yRight[Y+1] = Range(1, X, 1, Y);
for(int i=1; i<=X+1; i++) xLeft[i] = xLeft[i] + xLeft[i-1];
for(int i=1; i<=Y+1; i++) yLeft[i] = yLeft[i] + yLeft[i-1];
for(int i=X; i>=0; i--) xRight[i] = xRight[i] + xRight[i+1];
for(int i=Y; i>=0; i--) yRight[i] = yRight[i] + yRight[i+1];
for(int i=1; i<=X; i++){
Range tmp = xLeft[i-1] + xRight[i+1];
if(tmp.valid()) vec.push_back(dat(0, 0, tmp.D, tmp.L, tmp.R)), vec.push_back(dat(0, 1, tmp.U, tmp.L, tmp.R));
}
for(int i=1; i<=Y; i++){
Range tmp = yLeft[i-1] + yRight[i+1];
if(tmp.valid()) vec.push_back(dat(1, 0, tmp.D, tmp.L, tmp.R)), vec.push_back(dat(1, 1, tmp.U, tmp.L, tmp.R));
}
sort(vec.begin(), vec.end());
int X1 = -1, Y1 = -1;
treeA.init(X), treeB.init(X);
for(dat p: vec){
// printf("p: %d %d %d %d %d\n", p.type, p.where, p.val, p.l, p.r);
if(p.type == 0){
if(p.where == 0) treeA.add(p.l, p.r, 1);
else treeB.add(p.l, p.r, 1);
}
else{
if(p.where == 0){
if(treeB.sum(p.l, p.r)){
Y1 = p.val;
for(int i=p.l; i<=p.r; i++) if(treeB.sum(i, i)) {X1 = i; break; }
assert(X1 != -1);
break;
}
treeA.add(p.l, p.r, -1);
}
else{
if(treeA.sum(p.l, p.r)){
Y1 = p.val;
for(int i=p.l; i<=p.r; i++) if(treeA.sum(i, i)) {X1 = i; break; }
assert(X1 != -1);
break;
}
treeB.add(p.l, p.r, -1);
}
}
}
if(Y1 == -1) return false;
ans.push_back(make_pair(X1, Y1));
Range p = xLeft[X1-1] + xRight[X1+1];
Range q = yLeft[Y1-1] + yRight[Y1+1];
p = p+q;
ans.push_back(make_pair(p.L, p.D));
return true;
}
} p2;
bool check2(){
return p2.check2();
}
bool check3(){
return false;
}
bool check4(){
return false;
}
void output(){
if(ans.empty()) exit(1);
while((int)ans.size() < k) ans.push_back(ans.back());
for(auto p: ans) printf("%d %d\n", xCoord[p.first], yCoord[p.second]);
}
Compilation message
hamburg.cpp: In function 'void input()':
hamburg.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28600 KB |
Output is correct |
| 3 |
Correct |
15 ms |
28636 KB |
Output is correct |
| 4 |
Correct |
17 ms |
28712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28744 KB |
Output is correct |
| 2 |
Correct |
16 ms |
28704 KB |
Output is correct |
| 3 |
Correct |
16 ms |
28764 KB |
Output is correct |
| 4 |
Correct |
15 ms |
28756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
28760 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
28676 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28600 KB |
Output is correct |
| 3 |
Correct |
15 ms |
28636 KB |
Output is correct |
| 4 |
Correct |
17 ms |
28712 KB |
Output is correct |
| 5 |
Correct |
256 ms |
35412 KB |
Output is correct |
| 6 |
Correct |
257 ms |
35472 KB |
Output is correct |
| 7 |
Correct |
350 ms |
35524 KB |
Output is correct |
| 8 |
Correct |
258 ms |
35472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28744 KB |
Output is correct |
| 2 |
Correct |
16 ms |
28704 KB |
Output is correct |
| 3 |
Correct |
16 ms |
28764 KB |
Output is correct |
| 4 |
Correct |
15 ms |
28756 KB |
Output is correct |
| 5 |
Correct |
283 ms |
47764 KB |
Output is correct |
| 6 |
Correct |
286 ms |
48032 KB |
Output is correct |
| 7 |
Correct |
287 ms |
48012 KB |
Output is correct |
| 8 |
Correct |
287 ms |
48012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
28760 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
28676 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
