Submission #802645

#	Time	Username	Problem	Language	Result	Execution time	Memory
802645		79brue	IOI Fever (JOI21_fever)	C++17	100 / 100	672 ms	19872 KiB

fever

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Point{
    ll x, y;
    int idx;
    Point(){}
    Point(ll x, ll y): x(x), y(y){}
    Point(ll x, ll y, int idx): x(x), y(y), idx(idx){}

    bool operator<(const Point &r)const{
        if(x != r.x) return x < r.x;
        return y < r.y;
    }
};

int n;
Point arr[100002];
int ans;

void makeTrees();
void init();
void solve(int);

int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%lld %lld", &arr[i].x, &arr[i].y);
        arr[i].x*=2, arr[i].y*=2, arr[i].idx = i;
    }
    makeTrees();
    for(int d=0; d<4; d++){
        init();
        solve(d);
    }
    printf("%d", ans);
}

const ll INF = 3e18;
vector<Point> order[4];
int idx[4][100002];
int L[4][100002], R[4][100002];

ll tarr[100002];

struct Edge{
    int x, dir; ll d;
    Edge(){}
    Edge(int x, int dir, ll d): x(x), dir(dir), d(d){}
};

void makeTrees(){
    for(int i=0; i<n; i++){
        for(int j=0; j<4; j++) order[j].push_back(arr[i]);
    }

    sort(order[0].begin(), order[0].end(), [&](Point &a, Point &b){return a.y != b.y ? a.y < b.y : a.x < b.x;});
    sort(order[1].begin(), order[1].end(), [&](Point &a, Point &b){return a.x != b.x ? a.x < b.x : a.y < b.y;});
    sort(order[2].begin(), order[2].end(), [&](Point &a, Point &b){return a.y-a.x != b.y-b.x ? a.y-a.x<b.y-b.x : a.x<b.x;});
    sort(order[3].begin(), order[3].end(), [&](Point &a, Point &b){return a.y+a.x != b.y+b.x ? a.y+a.x<b.y+b.x : a.x<b.x;});

    for(int d=0; d<4; d++) for(int i=0; i<n; i++) idx[d][order[d][i].idx] = i;

    /// 0 구분기준: y
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && order[0][i].y == order[0][j+1].y) j++;
        for(int s=i; s<=j; s++) L[0][s] = i, R[0][s] = j;
        i=j;
    }
    /// 1 구분기준: x
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && order[1][i].x == order[1][j+1].x) j++;
        for(int s=i; s<=j; s++) L[1][s] = i, R[1][s] = j;
        i=j;
    }
    /// 2 구분기준: y-x
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && order[2][i].y-order[2][i].x == order[2][j+1].y-order[2][j+1].x) j++;
        for(int s=i; s<=j; s++) L[2][s] = i, R[2][s] = j;
        i=j;
    }
    /// 3 구분기준: y+x
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && order[3][i].y+order[3][i].x == order[3][j+1].y+order[3][j+1].x) j++;
        for(int s=i; s<=j; s++) L[3][s] = i, R[3][s] = j;
        i=j;
    }
}

bool visited[500002][2];

void init(){
    for(int i=0; i<=n; i++) visited[i][0] = visited[i][1] = 0;
}

struct dat{
    int x, dir; ll d; int w;
    dat(){}
    dat(int x, int dir, ll d): x(x), dir(dir), d(d){w=0;}
    dat(int x, int dir, ll d, int w): x(x), dir(dir), d(d), w(w){}
    bool operator<(const dat &r)const{
        return d>r.d;
    }
};

priority_queue<dat> pq;

inline ll dist(int x, int y){
    return max(abs(arr[x].x-arr[y].x), abs(arr[x].y-arr[y].y));
}

void pickup(int x, int d, ll t){
    if(d == 0){ /// 오른쪽 방향
        int l, r, i;

        /// 1과 만남: tree[2]에서 자기보다 오른쪽
        i = idx[2][x];
        r = R[2][i], l = lower_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x+t, INF)) - order[2].begin();
        if(l<=r && t <= dist(x, order[2][l].idx)) pq.push(dat(2*n + order[2][l].idx, 1, dist(x, order[2][l].idx), 1));

        /// 3과 만남: tree[3]에서 자기보다 오른쪽
        i = idx[3][x];
        r = R[3][i], l = lower_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x+t, INF)) - order[3].begin();
        if(l<=r && t <= dist(x, order[3][l].idx)) pq.push(dat(3*n + order[3][l].idx, 3, dist(x, order[3][l].idx), 1));

        /// 2와 만남: tree[0]에서 자기보다 오른쪽
        i = idx[0][x];
        r = R[0][i], l = lower_bound(order[0].begin()+L[0][i], order[0].begin()+R[0][i]+1, Point(arr[x].x+t+t, INF)) - order[0].begin();
        if(l<=r && t <= dist(x, order[0][l].idx) / 2) pq.push(dat(order[0][l].idx, 2, dist(x, order[0][l].idx) / 2, 1));
    }

    else if(d == 1){ /// 아래쪽 방향
        int l, r, i;

        /// 0과 만남: tree[2]에서 자기보다 왼쪽
        i = idx[2][x];
        l = L[2][i], r = upper_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x-t, -INF)) - order[2].begin() - 1;
        if(l<=r && t <= dist(x, order[2][r].idx)) pq.push(dat(2*n + order[2][r].idx, 0, dist(x, order[2][r].idx), -1));

        /// 2과 만남: tree[3]에서 자기보다 오른쪽
        i = idx[3][x];
        r = R[3][i], l = lower_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x+t, INF)) - order[3].begin();
        if(l<=r && t <= dist(x, order[3][l].idx)) pq.push(dat(3*n + order[3][l].idx, 2, dist(x, order[3][l].idx), 1));

        /// 3과 만남: tree[1]에서 자기보다 왼쪽
        i = idx[1][x];
        l = L[1][i], r = upper_bound(order[1].begin()+L[1][i], order[1].begin()+R[1][i]+1, Point(arr[x].x, arr[x].y-t-t)) - order[1].begin() - 1;
        if(l<=r && t <= dist(x, order[1][r].idx) / 2) pq.push(dat(n + order[1][r].idx, 3, dist(x, order[1][r].idx) / 2, -1));
    }

    else if(d == 2){ /// 왼쪽 방향
        int l, r, i;

        /// 3과 만남: tree[2]에서 자기보다 왼쪽
        i = idx[2][x];
        l = L[2][i], r = upper_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x-t, -INF)) - order[2].begin() - 1;
        if(l<=r && t <= dist(x, order[2][r].idx)) pq.push(dat(2*n + order[2][r].idx, 3, dist(x, order[2][r].idx), -1));

        /// 1과 만남: tree[3]에서 자기보다 왼쪽
        i = idx[3][x];
        l = L[3][i], r = upper_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x-t, INF)) - order[3].begin() - 1;
        if(l<=r && t <= dist(x, order[3][r].idx)) pq.push(dat(3*n + order[3][r].idx, 1, dist(x, order[3][r].idx), -1));

        /// 0과 만남: tree[0]에서 자기보다 왼쪽
        i = idx[0][x];
        l = L[0][i], r = upper_bound(order[0].begin()+L[0][i], order[0].begin()+R[0][i]+1, Point(arr[x].x-t-t, arr[x].y)) - order[0].begin() - 1;
        if(l<=r && t <= dist(x, order[0][r].idx) / 2) pq.push(dat(order[0][r].idx, 0, dist(x, order[0][r].idx) / 2, -1));
    }

    else if(d == 3){ /// 위쪽 방향
        int l, r, i;

        /// 0과 만남: tree[3]에서 자기보다 왼쪽
        i = idx[3][x];
        l = L[3][i], r = upper_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x-t, -INF)) - order[3].begin() - 1;
        if(l<=r && t <= dist(x, order[3][r].idx)) pq.push(dat(3*n + order[3][r].idx, 0, dist(x, order[3][r].idx), -1));

        /// 2과 만남: tree[2]에서 자기보다 오른쪽
        i = idx[2][x];
        r = R[2][i], l = lower_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x+t, INF)) - order[2].begin();
        if(l<=r && t <= dist(x, order[2][l].idx)) pq.push(dat(2*n + order[2][l].idx, 2, dist(x, order[2][l].idx), 1));

        /// 1과 만남: tree[1]에서 자기보다 오른쪽
        i = idx[1][x];
        r = R[1][i], l = lower_bound(order[1].begin()+L[1][i], order[1].begin()+R[1][i]+1, Point(arr[x].x, arr[x].y+t+t)) - order[1].begin();
        if(l<=r && t <= dist(x, order[1][l].idx) / 2) pq.push(dat(n + order[1][l].idx, 1, dist(x, order[1][l].idx) / 2, 1));
    }
}

void solve(int d){
//    printf("d: %d\n", d);

    int cnt = 0;
    for(int i=0; i<n*5; i++) visited[i][0] = visited[i][1] = 0;
    pq.push(dat(4*n, d, 0));
    while(!pq.empty()){
        dat tmp = pq.top(); pq.pop();
        if(visited[tmp.x][tmp.w>=0]) continue;
        visited[tmp.x][tmp.w>=0] = 1;

        int group = tmp.x / n;
        int x = tmp.x % n;

//        printf("%d %d dir %d - %lld\n", group, x, tmp.dir, tmp.d);

        if(group == 4){
            if(visited[tmp.x][tmp.w<0]) continue;
            cnt++;
            pickup(x, tmp.dir, tmp.d);
        }
        else{
            if(!visited[x + n*4][0]){
                pq.push(dat(x + n*4, tmp.dir, tmp.d, 0));
            }
            /// 다음 것도 가능한지 확인
            int i = idx[group][x], w = tmp.w;
            if(0 <= i + w && i + w < n && L[group][i] == L[group][i+w] && !visited[group*n + order[group][i+w].idx][w>=0]){
                int X = x, Y = order[group][i+w].idx;
                pq.push(dat(group*n + Y, tmp.dir, tmp.d + dist(X, Y) / (group < 2 ? 2 : 1), tmp.w));
            }
        }
    }
    ans = max(ans, cnt);
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fever.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld %lld", &arr[i].x, &arr[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31