#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point{
int x, y, idx;
Point(){}
Point(int x, int y, int idx): x(x), y(y), idx(idx){}
};
void input();
void getChain();
void getInterval();
void getAnswer();
int n;
Point arr[250002];
vector<int> link[250002];
int up[2502], upN; /// 위쪽 체인 번호
int down[2502], downN; /// 아래쪽 체인 번호
int upIdx[250002], downIdx[250002];
int main(){
input();
getChain();
getInterval();
getAnswer();
}
void input(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
arr[i].idx = i;
}
}
void getChain(){
vector<Point> vec (arr+1, arr+n+1);
sort(vec.begin(), vec.end(), [&](Point &a, Point &b){
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
for(Point p: vec){
if(upN && p.y >= arr[up[upN]].y) continue;
up[++upN] = p.idx;
upIdx[up[upN]] = upN;
}
sort(vec.begin(), vec.end(), [&](Point &a, Point &b){
if(a.x != b.x) return a.x > b.x;
return a.y > b.y;
});
for(Point p: vec){
if(downN && p.y <= arr[down[downN]].y) continue;
down[++downN] = p.idx;
}
reverse(down+1, down+downN+1);
for(int i=1; i<=downN; i++) downIdx[down[downN]] = downN;
}
int upS[250002], upE[250002];
int downS[250002], downE[250002];
void getInterval(){
for(int i=1; i<=n; i++){
upS[i] = upper_bound(up+1, up+upN+1, i, [&](int X, int Y){
return arr[X].y > arr[Y].y;
}) - up;
upE[i] = lower_bound(up+1, up+upN+1, i, [&](int X, int Y){
return arr[X].x < arr[Y].x;
}) - up - 1;
downS[i] = upper_bound(down+1, down+downN+1, i, [&](int X, int Y){
return arr[X].x < arr[Y].x;
}) - down;
downE[i] = lower_bound(down+1, down+downN+1, i, [&](int X, int Y){
return arr[X].y > arr[Y].y;
}) - down - 1;
}
}
void getAnswer(){
for(int i=1; i<=n; i++){
vector<int> upL (n+1), upR (n+1), downL (n+1), downR (n+1);
upL[0] = upN+1, upR[0] = 0, downL[0] = downN+1, downR[0] = 0;
if(upIdx[i]) upL[0] = upR[0] = upIdx[i];
if(downIdx[i]) downL[0] = downR[0] = downIdx[i];
upL[1] = min(upL[0], upS[i]), upR[1] = max(upR[0], upE[i]);
downL[1] = min(downL[0], downS[i]), downR[1] = max(downR[0], downE[i]);
for(int j=2; j<=n; j++){
upL[j] = min(upL[j-1], upS[down[downL[j-1]]]);
upR[j] = max(upR[j-1], upE[down[downR[j-1]]]);
downL[j] = min(downL[j-1], downS[up[upL[j-1]]]);
downR[j] = max(downR[j-1], downE[up[upR[j-1]]]);
}
ll ans = 0;
for(int j=1; j<=n; j++){
if(i==j) continue;
if((arr[i].x < arr[j].x && arr[i].y < arr[j].y) || (arr[i].x > arr[j].x && arr[i].y > arr[j].y)){
ans++;
continue;
}
/// 거리가 최소 2
if(upIdx[j]){ /// 위쪽 부분일 때
int L = 0, R = n, KEY = n;
while(L<=R){
int M = (L+R)/2;
if(upL[M] <= upIdx[j] && upIdx[j] <= upR[M]) KEY = M, R = M-1;
else L = M+1;
}
ans += KEY;
}
else if(downIdx[j]){
int L = 0, R = n, KEY = n;
while(L<=R){
int M = (L+R)/2;
if(downL[M] <= downIdx[j] && downIdx[j] <= downR[M]) KEY = M, R = M-1;
else L = M+1;
}
ans += KEY;
}
else{
int L = 0, R = n, KEY = n;
while(L <= R){
int MID = (L+R)/2;
if((max(upL[KEY], upS[j]) <= min(upR[KEY], upE[j])) ||
(max(downL[KEY], downS[j]) <= min(downR[KEY], downE[j]))){
KEY = MID;
R = MID - 1;
}
else L = MID + 1;
}
ans += KEY + 2;
}
}
printf("%lld\n", ans);
}
}
Compilation message
adriatic.cpp: In function 'void input()':
adriatic.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
adriatic.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
6228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1046 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2075 ms |
7620 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
20056 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
