oj.uz

답안 #767764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767764 2023-06-27T07:03:38 Z 79brue 섬 항해 (CEOI13_adriatic) C++17
60 / 100
 2000 ms 18904 KB 
#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;
    }
    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<=upN; i++) upIdx[up[i]] = i;
    for(int i=1; i<=downN; i++) downIdx[down[i]] = i;
}

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;
    }
    upS[0] = upN+1, upE[0] = 0;
    downS[0] = downN+1, downE[0] = 0;
}

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[MID], upS[j]) <= min(upR[MID], upE[j])) ||
                       (max(downL[MID], downS[j]) <= min(downR[MID], downE[j]))){
                        KEY = MID;
                        R = MID - 1;
                    }
                    else L = MID + 1;
                }
                ans += KEY + 1;
            }
        }
        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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6108 KB Output is correct
4 Correct 4 ms 6100 KB Output is correct
5 Correct 5 ms 6228 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 6280 KB Output is correct
2 Correct 46 ms 6276 KB Output is correct
3 Correct 132 ms 6284 KB Output is correct
4 Correct 47 ms 6300 KB Output is correct
5 Correct 51 ms 6300 KB Output is correct
6 Correct 144 ms 6448 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1499 ms 6468 KB Output is correct
2 Correct 506 ms 6624 KB Output is correct
3 Correct 1555 ms 6732 KB Output is correct
4 Correct 508 ms 6484 KB Output is correct
5 Correct 541 ms 6628 KB Output is correct
6 Correct 1848 ms 6668 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2081 ms 7492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2055 ms 18904 KB Time limit exceeded
2 Halted 0 ms 0 KB -