oj.uz

Submission #767758

# Submission time Handle Problem Language Result Execution time Memory
767758 2023-06-27T06:48:57 Z 79brue Adriatic (CEOI13_adriatic) C++17
0 / 100
 2000 ms 18824 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;
    }
}

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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 4 ms 6180 KB Output is correct
4 Incorrect 4 ms 6180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 6280 KB Output is correct
2 Correct 45 ms 6228 KB Output is correct
3 Incorrect 133 ms 6292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1518 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 7468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 18824 KB Time limit exceeded
2 Halted 0 ms 0 KB -