Submission #804869

#	Time	Username	Problem	Language	Result	Execution time	Memory
804869		79brue	Cultivation (JOI17_cultivation)	C++17	0 / 100	1 ms	468 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 2e9;

ll n, m; int k;
ll X[302], Y[302];
int rx[302], ry[302], sx, sy;
ll ans = LLONG_MAX;

struct Interval{
    ll l, r; /// 높이 구간
    ll ldist, rdist, mdist; /// 최소 길이
    Interval(){}
    Interval(ll l, ll r, ll ldist, ll rdist, ll mdist): l(l), r(r), ldist(ldist), rdist(rdist), mdist(mdist){}
    bool operator<(const Interval &nxt)const{
        return l<nxt.l;
    }
};

pair<ll, int> dqL[1002], dqR[1002], dqLen[1002];
int l1, l2, r1, r2, len1, len2;

vector<Interval> info;

ll udlength[500002], udsize;
ll A[302][302], B[302][302], C[302][302];
pair<ll, ll> arr[302];

pair<ll, ll> ableGroup(ll ud, int s, int e){
    ll L = max(X[e] - ud, s==1 ? -INF : X[s-1] + 1);
    ll R = min(X[s], e==k ? INF : X[e+1] - ud - 1);
    if(L>R) return make_pair(-INF, -INF);
    return make_pair(L, R);
}

int main(){
    scanf("%lld %lld %d", &n, &m, &k);
//    n=m=1000000000, k=300;
    for(int i=1; i<=k; i++){
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
//        X[i] = Y[i] = i*i+i+2;
    }
    sort(arr+1, arr+k+1);
    for(int i=1; i<=n; i++) X[i] = arr[i].first, Y[i] = arr[i].second;

    for(int i=1; i<=n; i++){
        vector<ll> vec (1, Y[i]);
        A[i][i] = Y[i] - 1;
        B[i][i] = m - Y[i];
        C[i][i] = 0;
        for(int j=i+1; j<=n; j++){
            auto it = lower_bound(vec.begin(), vec.end(), Y[j]);
            if(!(it != vec.end() && *it == Y[j])) vec.insert(it, Y[j]);
            A[i][j] = vec.front() - 1;
            B[i][j] = m - vec.back();
            C[i][j] = 0;
            for(int k=0; k<(int)vec.size()-1; k++) C[i][j] = max(C[i][j], vec[k+1] - vec[k] - 1);
        }
    }

    udlength[udsize++] = n-1;
    for(int i=1; i<=k; i++){
        udlength[udsize++] = X[i] - 1;
        udlength[udsize++] = n - X[i];
        for(int j=1; j<=k; j++){
            if(X[i] < X[j]) udlength[udsize++] = X[j] - X[i] - 1;
            udlength[udsize++] = X[i] + n - X[j] - 1;
        }
    }
    sort(udlength, udlength+udsize);
    udsize = unique(udlength, udlength+udsize) - udlength;

    for(int ui=0; ui<udsize; ui++){ /// 위 - 아래 간격
        ll ud = udlength[ui];
        if(ud<0) continue;

        bool bad = 0;
        for(int i=1; i<k; i++){
            if(X[i+1] - X[i] - 1 > ud) {bad = 1; break;}
        }
        if(bad) continue;

        info.clear();
        int e = 1;
        for(int s=1; s<=k; s++){
            while(ableGroup(ud, s, e) == make_pair(-INF, -INF)) e++;
            while(1){
                while(e<k && X[e]==X[e+1]) e++;
                pair<ll, ll> p = ableGroup(ud, s, e);
                info.push_back(Interval(p.first, p.second, A[s][e], B[s][e], C[s][e]));

                if(e<n && ableGroup(ud, s, e+1) != make_pair(-INF, -INF)) e++;
                else break;
            }
            while(s<k && X[s]==X[s+1]) s++;
            while(e<=s) e++;
        }

        int j = 0;
        l1 = l2 = r1 = r2 = len1 = len2 = 0;
        dqL[l2++] = make_pair(info[0].ldist, 0);
        dqR[r2++] = make_pair(info[0].rdist, 0);
        dqLen[len2++] = make_pair(info[0].mdist, 0);

        for(int i=0; i<(int)info.size(); i++){
            if(l1!=l2 && dqL[l1].second < i) l1++;
            if(r1!=r2 && dqR[r1].second < i) r1++;
            if(len1!=len2 && dqLen[len1].second < i) len1++;
            while(j < (int)info.size() && info[j].r - info[i].l + 1 < n){
                j++;
                while(l1!=l2 && dqL[l2-1].first <= info[j].ldist) l2--;
                dqL[l2++] = make_pair(info[j].ldist, j);
                while(r1!=r2 && dqR[r2-1].first <= info[j].rdist) r2--;
                dqR[r2++] = make_pair(info[j].rdist, j);
                while(len1!=len2 && dqLen[len2-1].first <= info[j].mdist) len2--;
                dqLen[len2++] = make_pair(info[j].mdist, j);
            }
            if(j == (int)info.size()) break;
            ll minL = dqL[l1].first, minR = dqR[r1].first, len = dqLen[len1].first;
            ans = min(ans, ud + max(len, minL+minR));
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%lld %lld %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld %lld", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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