oj.uz

답안 #520280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520280 2022-01-29T05:51:05 Z 79brue Cultivation (JOI17_cultivation) C++14
5 / 100
 2000 ms 324 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

    bool operator<(const Point &r)const{
        return make_pair(x, y) < make_pair(r.x, r.y);
    }
};

struct Query{
    ll x, y; bool in;
    Query(){}
    Query(ll x, ll y, bool in): x(x), y(y), in(in){}

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

struct State{
    ll x, l, r, mid;
    State(){}
    State(ll x, ll l, ll r, ll mid): x(x), l(l), r(r), mid(mid){}
};

ll n, m; int k;
Point arr[302];
ll ans = LLONG_MAX;
ll maxDiff;

void testInterval(ll d){
    if(d<maxDiff) return;

    multiset<ll> mst;
    multiset<ll> diff;
    mst.insert(0);
    mst.insert(m+1);
    diff.insert(m+1);

    vector<Query> vec;
    for(int i=1; i<=k; i++){
        vec.push_back(Query(arr[i].x, arr[i].y, 1));
        vec.push_back(Query(arr[i].x+d+1, arr[i].y, 0));
    }
    sort(vec.begin(), vec.end());

    vector<State> st;
    for(int i=0; i<(int)vec.size(); i++){
        if(vec[i].in == 1){
            auto it = mst.lower_bound(vec[i].y);
            diff.erase(diff.find(*it - *prev(it)));
            diff.insert(*it - vec[i].y);
            diff.insert(vec[i].y - *prev(it));
            mst.insert(vec[i].y);
        }
        else{
            auto it = mst.lower_bound(vec[i].y);
            diff.erase(diff.find(*next(it) - vec[i].y));
            diff.erase(diff.find(vec[i].y - *prev(it)));
            diff.insert(*next(it) - *prev(it));
            mst.erase(it);
        }

        if(i+1 == (int)vec.size() || vec[i].x != vec[i+1].x){
            if(*diff.rbegin() == m+1) st.push_back(State(vec[i].x, 1e10, 1e10, 1e10));
            else st.push_back(State(vec[i].x, *next(mst.begin()) - 1, m - *prev(prev(mst.end())),
                               *diff.rbegin() - 1));
        }
    }

    for(int i=0; i<(int)st.size(); i++){
//        printf("%lld: %lld %lld %lld\n", st[i].x, st[i].l, st[i].r, st[i].mid);
        if(arr[1].x + d < vec[i].x) break;

        int j = i;
        while(j < (int)st.size()-1 && st[j+1].x - st[i].x < n) j++;

        ll maxL = 0, maxR = 0, maxD = 0;
        for(int u=i; u<=j; u++){
            maxL = max(maxL, st[u].l);
            maxR = max(maxR, st[u].r);
            maxD = max(maxD, st[u].mid);
        }
        ans = min(ans, d + maxL + maxR + max(0LL, maxD - maxL - maxR));
    }
}

int main(){
    scanf("%lld %lld %d", &n, &m, &k);
    for(int i=1; i<=k; i++){
        scanf("%d %d", &arr[i].x, &arr[i].y);
    }

    sort(arr+1, arr+k+1);
    arr[k+1].x = n+1;
    for(int i=1; i<=k+1; i++) maxDiff = max(maxDiff, arr[i].x - arr[i-1].x);
    maxDiff--;

    testInterval(maxDiff);
    for(int i=0; i<=k+1; i++){
        for(int j=i+1; j<=k+1; j++){
            testInterval(arr[j].x - arr[i].x - 1);
            testInterval(arr[j].x - arr[i].x - 2);
        }
    }

    printf("%lld", ans);
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:99:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   99 |         scanf("%d %d", &arr[i].x, &arr[i].y);
      |                ~^      ~~~~~~~~~
      |                 |      |
      |                 int*   ll* {aka long long int*}
      |                %lld
cultivation.cpp:99:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   99 |         scanf("%d %d", &arr[i].x, &arr[i].y);
      |                   ~^              ~~~~~~~~~
      |                    |              |
      |                    int*           ll* {aka long long int*}
      |                   %lld
cultivation.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%lld %lld %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %d", &arr[i].x, &arr[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 276 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 276 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 204 KB Output is correct
18 Correct 168 ms 292 KB Output is correct
19 Correct 12 ms 204 KB Output is correct
20 Correct 3 ms 296 KB Output is correct
21 Correct 72 ms 292 KB Output is correct
22 Correct 1120 ms 316 KB Output is correct
23 Correct 2 ms 204 KB Output is correct
24 Execution timed out 2080 ms 324 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 276 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 204 KB Output is correct
18 Correct 168 ms 292 KB Output is correct
19 Correct 12 ms 204 KB Output is correct
20 Correct 3 ms 296 KB Output is correct
21 Correct 72 ms 292 KB Output is correct
22 Correct 1120 ms 316 KB Output is correct
23 Correct 2 ms 204 KB Output is correct
24 Execution timed out 2080 ms 324 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 276 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 204 KB Output is correct
18 Correct 168 ms 292 KB Output is correct
19 Correct 12 ms 204 KB Output is correct
20 Correct 3 ms 296 KB Output is correct
21 Correct 72 ms 292 KB Output is correct
22 Correct 1120 ms 316 KB Output is correct
23 Correct 2 ms 204 KB Output is correct
24 Execution timed out 2080 ms 324 KB Time limit exceeded
25 Halted 0 ms 0 KB -