제출 #520292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520292		79brue	Cultivation (JOI17_cultivation)	C++14	5 / 100	2069 ms	332 KiB

cultivation

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

//    printf("diff %lld\n", d);
    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);
        }
    }
    for(int i=1; i<=k; i++){
        for(int j=i; j<=k; j++){
            testInterval(arr[i].x - 1 + n - arr[j].x);
        }
    }

    for(int i=1; i<=k; i++) arr[i].x = n+1-arr[i].x, arr[i].y = m+1-arr[i].y;
    reverse(arr+1, arr+k+1);
    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);
        }
    }
    for(int i=1; i<=k; i++){
        for(int j=i; j<=k; j++){
            testInterval(arr[i].x - 1 + n - arr[j].x);
        }
    }

    printf("%lld", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20