oj.uz

Submission #801972

# Submission time Handle Problem Language Result Execution time Memory
801972 2023-08-02T08:50:06 Z 반딧불(#10089) IOI Fever (JOI21_fever) C++17
6 / 100
 5000 ms 756 KB 
#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;
struct segTree{
    ll plusMin[400002], plusLazy[400002], plusVal[400002]; int plusIdx[400002];
    ll minusMin[400002], minusLazy[400002], minusVal[400002]; int minusIdx[400002];
    ll val[400002];

    void merge(int i){
        val[i] = min(val[i*2], val[i*2+1]);
        plusMin[i] = min(plusMin[i*2], plusMin[i*2+1]);
        plusVal[i] = min(plusVal[i*2], plusVal[i*2+1]);
        minusMin[i] = min(minusMin[i*2], minusMin[i*2+1]);
        minusVal[i] = min(minusVal[i*2], minusVal[i*2+1]);
        plusIdx[i] = (plusVal[i*2] <= plusVal[i*2+1]) ? plusIdx[i*2] : plusIdx[i*2+1];
        minusIdx[i] = (minusVal[i*2] <= minusVal[i*2+1]) ? minusIdx[i*2] : minusIdx[i*2+1];
    }

    void init(int i, int l, int r, ll *arr){
        plusMin[i] = minusMin[i] = plusLazy[i] = minusLazy[i] = INF;
        if(l==r){
            val[i] = arr[l];
            plusVal[i] = val[i] + plusMin[i];
            minusVal[i] = -val[i] + minusMin[i];
            plusIdx[i] = minusIdx[i] = l;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        merge(i);
    }

    void propagate(int i, int l, int r){
        if(plusLazy[i] != INF){
            plusMin[i] = min(plusMin[i], plusLazy[i]);
            plusVal[i] = min(plusVal[i], val[i] + plusMin[i]);
            if(l!=r) plusLazy[i*2] = min(plusLazy[i*2], plusLazy[i]), plusLazy[i*2+1] = min(plusLazy[i*2+1], plusLazy[i]);
            plusLazy[i] = INF;
        }
        if(minusLazy[i] != INF){
            minusMin[i] = min(minusMin[i], minusLazy[i]);
            minusVal[i] = min(minusVal[i], -val[i] + minusMin[i]);
            if(l!=r) minusLazy[i*2] = min(minusLazy[i*2], minusLazy[i]), minusLazy[i*2+1] = min(minusLazy[i*2+1], minusLazy[i]);
            minusLazy[i] = INF;
        }
    }

    void updatePlus(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            plusLazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        updatePlus(i*2, l, m, s, e, v);
        updatePlus(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    void updateMinus(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            minusLazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        updateMinus(i*2, l, m, s, e, v);
        updateMinus(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    pair<ll, int> query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return make_pair(INF, -1);
        if(s<=l && r<=e) return make_pair(min(plusVal[i], minusVal[i]), plusVal[i]<minusVal[i]?plusIdx[i]:minusIdx[i]);
        int m = (l+r)>>1;
        return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }

    void updateOne(int i, int l, int r, int x){
        propagate(i, l, r);
        if(l==r){
            val[i] = plusVal[i] = minusVal[i] = INF;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) updateOne(i*2, l, m, x), propagate(i*2+1, m+1, r);
        else updateOne(i*2+1, m+1, r, x), propagate(i*2, l, m);
        merge(i);
    }
} tree[4];
vector<Point> order[4];
int idx[4][100002];
int L[4][100002], R[4][100002];

ll tarr[100002];

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;
    }
}

void init(){
    /// Ʈ�� ����
    /// 0: ���� 1/2 arr[i].x
    for(int i=0; i<n; i++){
        tarr[i] = order[0][i].x / 2;
    }
    tree[0].init(1, 0, n-1, tarr);
    /// 1: ���� 1/2 arr[i].y
    for(int i=0; i<n; i++){
        tarr[i] = order[1][i].y / 2;
    }
    tree[1].init(1, 0, n-1, tarr);
    /// 2: ���� arr[i].x
    for(int i=0; i<n; i++){
        tarr[i] = order[2][i].x;
    }
    tree[2].init(1, 0, n-1, tarr);
    /// 3: ���� arr[i].x
    for(int i=0; i<n; i++){
        tarr[i] = order[3][i].x;
    }
    tree[3].init(1, 0, n-1, tarr);
}

bool visited[100002];

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

void pickup(int x, int d, ll t){
    /// ���� ��� Ʈ������ ��������
    for(int d=0; d<4; d++){
        tree[d].updateOne(1, 0, n-1, idx[d][x]);
    }

    /// �״����� Ʈ���� ������ ������
    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) tree[2].updatePlus(1, 0, n-1, l, r, -arr[x].x);

        /// 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) tree[3].updatePlus(1, 0, n-1, l, r, -arr[x].x);

        /// 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) tree[0].updatePlus(1, 0, n-1, l, r, -arr[x].x/2);
    }

    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) tree[2].updateMinus(1, 0, n-1, l, r, arr[x].x);

        /// 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) tree[3].updatePlus(1, 0, n-1, l, r, -arr[x].x);

        /// 3�� ����: tree[1]���� �ڱ⺸�� ����
        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, arr[x].y-t-t)) - order[0].begin() - 1;
        if(l<=r) tree[0].updatePlus(1, 0, n-1, l, r, arr[x].y/2);
    }

    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) tree[2].updateMinus(1, 0, n-1, l, r, arr[x].x);

        /// 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) tree[3].updatePlus(1, 0, n-1, l, r, arr[x].x);

        /// 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) tree[0].updatePlus(1, 0, n-1, l, r, arr[x].x/2);
    }

    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) tree[3].updateMinus(1, 0, n-1, l, r, arr[x].x);

        /// 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) tree[2].updatePlus(1, 0, n-1, l, r, -arr[x].x);

        /// 1�� ����: tree[1]���� �ڱ⺸�� ������
        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, arr[x].y+t+t)) - order[0].begin();
        if(l<=r) tree[0].updatePlus(1, 0, n-1, l, r, -arr[x].y/2);
    }
}

void solve(int d){
    int cnt = 1;
    pickup(0, d, 0);
    while(1){
        pair<ll, int> mn[4];
        for(int d=0; d<4; d++){
            mn[d] = tree[d].query(1, 0, n-1, 0, n-1);
            mn[d].second = order[d][mn[d].second].idx;
        }
        int idx = min_element(mn, mn+4) - mn;
        if(mn[idx].first >= 1e18) break;
        pickup(mn[idx].second, idx, mn[idx].first);
        cnt++;
    }
    ans = max(ans, cnt);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 628 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 568 KB Output is correct
26 Execution timed out 5039 ms 596 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 628 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 568 KB Output is correct
26 Execution timed out 5039 ms 596 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 756 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 628 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 568 KB Output is correct
26 Execution timed out 5039 ms 596 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 628 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 568 KB Output is correct
26 Execution timed out 5039 ms 596 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 628 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 568 KB Output is correct
26 Execution timed out 5039 ms 596 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 628 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 568 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 568 KB Output is correct
26 Execution timed out 5039 ms 596 KB Time limit exceeded
27 Halted 0 ms 0 KB -