| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 352660 |
2021-01-21T03:41:40 Z |
arnold518 |
Kosta (COI14_kosta) |
C++14 |
|
1600 ms |
24144 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define x first
#define y second
const int MAXN = 2e5;
const int INF = 2e8;
int N, K;
pii A[MAXN+10];
int D;
int ans1, ans2;
int XL[MAXN+10], XR[MAXN+10], YL[MAXN+10], YR[MAXN+10], C[MAXN+10];
struct BIT
{
int tree[4000010];
void init()
{
memset(tree, 0, sizeof(tree));
}
void update(int i)
{
for(i+=2000001; i<=4000001; i+=(i&-i)) tree[i]++;
}
int query(int i)
{
int ret=0;
for(i+=2000001; i>0; i-=(i&-i)) ret+=tree[i];
return ret;
}
}bit;
bool solve(int _D)
{
D=_D;
//printf("SOLVE %d\n", D);
for(int i=1; i<=N; i++)
{
XL[i]=INF;
XR[i]=-INF;
YL[i]=INF;
YR[i]=-INF;
}
{
vector<pii> V, V2;
for(int i=1; i<=N; i++) V.push_back({A[i].x-D, i});
for(int i=1; i<=N; i++) V2.push_back(A[i]);
sort(V.begin(), V.end());
sort(V2.begin(), V2.end());
int xl, xr, yl, yr;
xl=INF; xr=-INF; yl=INF; yr=-INF;
for(int i=0, j=0; i<V.size(); i++)
{
for(; j<V2.size() && V2[j].x<V[i].x; j++)
{
xl=min(xl, V2[j].x);
xr=max(xr, V2[j].x);
yl=min(yl, V2[j].y);
yr=max(yr, V2[j].y);
}
int it=V[i].second;
XL[it]=min(XL[it], xl);
XR[it]=max(XR[it], xr);
YL[it]=min(YL[it], yl);
YR[it]=max(YR[it], yr);
}
}
{
vector<pii> V, V2;
for(int i=1; i<=N; i++) V.push_back({A[i].x+D, i});
for(int i=1; i<=N; i++) V2.push_back(A[i]);
sort(V.begin(), V.end(), greater<pii>());
sort(V2.begin(), V2.end(), greater<pii>());
int xl, xr, yl, yr;
xl=INF; xr=-INF; yl=INF; yr=-INF;
for(int i=0, j=0; i<V.size(); i++)
{
for(; j<V2.size() && V2[j].x>V[i].x; j++)
{
xl=min(xl, V2[j].x);
xr=max(xr, V2[j].x);
yl=min(yl, V2[j].y);
yr=max(yr, V2[j].y);
}
int it=V[i].second;
XL[it]=min(XL[it], xl);
XR[it]=max(XR[it], xr);
YL[it]=min(YL[it], yl);
YR[it]=max(YR[it], yr);
}
}
{
vector<pii> V, V2;
for(int i=1; i<=N; i++) V.push_back({A[i].y-D, i});
for(int i=1; i<=N; i++) V2.push_back({A[i].y, A[i].x});
sort(V.begin(), V.end());
sort(V2.begin(), V2.end());
int xl, xr, yl, yr;
xl=INF; xr=-INF; yl=INF; yr=-INF;
for(int i=0, j=0; i<V.size(); i++)
{
for(; j<V2.size() && V2[j].x<V[i].x; j++)
{
xl=min(xl, V2[j].y);
xr=max(xr, V2[j].y);
yl=min(yl, V2[j].x);
yr=max(yr, V2[j].x);
}
int it=V[i].second;
XL[it]=min(XL[it], xl);
XR[it]=max(XR[it], xr);
YL[it]=min(YL[it], yl);
YR[it]=max(YR[it], yr);
}
}
{
vector<pii> V, V2;
for(int i=1; i<=N; i++) V.push_back({A[i].y+D, i});
for(int i=1; i<=N; i++) V2.push_back({A[i].y, A[i].x});
sort(V.begin(), V.end(), greater<pii>());
sort(V2.begin(), V2.end(), greater<pii>());
int xl, xr, yl, yr;
xl=INF; xr=-INF; yl=INF; yr=-INF;
for(int i=0, j=0; i<V.size(); i++)
{
for(; j<V2.size() && V2[j].x>V[i].x; j++)
{
xl=min(xl, V2[j].y);
xr=max(xr, V2[j].y);
yl=min(yl, V2[j].x);
yr=max(yr, V2[j].x);
}
int it=V[i].second;
XL[it]=min(XL[it], xl);
XR[it]=max(XR[it], xr);
YL[it]=min(YL[it], yl);
YR[it]=max(YR[it], yr);
}
}
vector<pair<pii, int>> VV;
vector<pii> V2;
for(int i=1; i<=N; i++) V2.push_back(A[i]);
sort(V2.begin(), V2.end());
for(int i=1; i<=N; i++)
{
if(XL[i]==INF)
{
ans1=i; ans2=i;
return true;
}
int xl, xr, yl, yr;
xl=XR[i]-D; xr=XL[i]+D;
yl=YR[i]-D; yr=YL[i]+D;
if(xl>xr) continue;
if(yl>yr) continue;
//printf("%d : %d %d %d %d\n", i, xl, xr, yl, yr);
VV.push_back({{xr, yr}, i});
VV.push_back({{xl-1, yr}, -i});
VV.push_back({{xr, yl-1}, -i});
VV.push_back({{xl-1, yl-1}, i});
}
sort(VV.begin(), VV.end());
bit.init();
for(int i=1; i<=N; i++) C[i]=0;
for(int i=0, j=0; i<VV.size(); i++)
{
for(; j<V2.size() && V2[j].x<=VV[i].first.x; j++)
{
bit.update(V2[j].y);
}
int t=VV[i].second;
if(t>0) C[t]+=bit.query(VV[i].first.y);
else C[-t]-=bit.query(VV[i].first.y);
}
//for(int j=1; j<=N; j++) printf("%d ", C[j]); printf("\n");
//printf("HI\n");
for(int j=1; j<=N; j++)
{
if(C[j]==0) continue;
//printf("WOW %d %d\n", j, C[j]);
int xl, xr, yl, yr;
xl=INF; xr=-INF; yl=INF; yr=-INF;
for(int i=1; i<=N; i++)
{
if(max({A[j].x-A[i].x, A[i].x-A[j].x, A[j].y-A[i].y, A[i].y-A[j].y})<=D) continue;
xl=min(xl, A[i].x);
xr=max(xr, A[i].x);
yl=min(yl, A[i].y);
yr=max(yr, A[i].y);
}
if(xl==INF)
{
ans1=ans2=j;
return true;
}
for(int i=1; i<=N; i++)
{
int t=max({xr-A[i].x, A[i].x-xl, yr-A[i].y, A[i].y-yl});
if(t<=D)
{
ans1=j; ans2=i;
return true;
}
}
assert(0);
}
return false;
}
int main()
{
scanf("%d%d", &K, &N);
for(int i=1; i<=N; i++)
{
scanf("%d%d", &A[i].x, &A[i].y);
int x2=A[i].x+A[i].y;
int y2=A[i].x-A[i].y;
A[i]={x2, y2};
}
if(K==1)
{
int xl, xr, yl, yr;
xl=INF; xr=-INF; yl=INF; yr=-INF;
for(int i=1; i<=N; i++)
{
xl=min(xl, A[i].x);
xr=max(xr, A[i].x);
yl=min(yl, A[i].y);
yr=max(yr, A[i].y);
}
int D=INF, ans=-1;
for(int i=1; i<=N; i++)
{
int t=max({xr-A[i].x, A[i].x-xl, yr-A[i].y, A[i].y-yl});
if(D>=t) D=t, ans=i;
}
printf("%d\n%d\n", D, ans);
}
else
{
int lo=0, hi=INF;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(solve(mid)) hi=mid;
else lo=mid;
}
solve(hi);
printf("%d\n%d %d\n", hi, ans1, ans2);
}
}
Compilation message
kosta.cpp: In function 'bool solve(int)':
kosta.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0, j=0; i<V.size(); i++)
| ~^~~~~~~~~
kosta.cpp:65:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(; j<V2.size() && V2[j].x<V[i].x; j++)
| ~^~~~~~~~~~
kosta.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0, j=0; i<V.size(); i++)
| ~^~~~~~~~~
kosta.cpp:90:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(; j<V2.size() && V2[j].x>V[i].x; j++)
| ~^~~~~~~~~~
kosta.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i=0, j=0; i<V.size(); i++)
| ~^~~~~~~~~
kosta.cpp:115:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(; j<V2.size() && V2[j].x<V[i].x; j++)
| ~^~~~~~~~~~
kosta.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0, j=0; i<V.size(); i++)
| ~^~~~~~~~~
kosta.cpp:140:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(; j<V2.size() && V2[j].x>V[i].x; j++)
| ~^~~~~~~~~~
kosta.cpp:184:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int i=0, j=0; i<VV.size(); i++)
| ~^~~~~~~~~~
kosta.cpp:186:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(; j<V2.size() && V2[j].x<=VV[i].first.x; j++)
| ~^~~~~~~~~~
kosta.cpp: In function 'int main()':
kosta.cpp:267:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
267 | int mid=lo+hi>>1;
| ~~^~~
kosta.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
234 | scanf("%d%d", &K, &N);
| ~~~~~^~~~~~~~~~~~~~~~
kosta.cpp:237:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
237 | scanf("%d%d", &A[i].x, &A[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
47 ms |
1900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
15980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
16084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
16236 KB |
Output is correct |
| 2 |
Correct |
104 ms |
16452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
16280 KB |
Output is correct |
| 2 |
Correct |
101 ms |
16364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1157 ms |
20236 KB |
Output is correct |
| 2 |
Correct |
1204 ms |
20824 KB |
Output is correct |
| 3 |
Correct |
1217 ms |
20916 KB |
Output is correct |
| 4 |
Correct |
1320 ms |
22964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1377 ms |
18672 KB |
Output is correct |
| 2 |
Correct |
1453 ms |
23460 KB |
Output is correct |
| 3 |
Correct |
1593 ms |
23896 KB |
Output is correct |
| 4 |
Correct |
1600 ms |
24144 KB |
Output is correct |
