Submission #447673

#	Time	Username	Problem	Language	Result	Execution time	Memory
447673		Haruto810198	Cultivation (JOI17_cultivation)	C++17	30 / 100	33 ms	532 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = 1e18;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 310;

int n;
int R, C;
pii pt[MAX];

int res;

int interesting = 0;

int check(int dxr){

    //cerr<<"check("<<dxr<<") : "<<endl;

    multiset<int> st;
    vector<vi> ev;
    /// insert : time,  1, pos
    /// erase  : time, -1, pos

    vector<vi> seg; /// Lpos, Rpos, minSum, [L, R]

    FOR(i, 1, n, 1){
        ev.pb({pt[i].F, 1, pt[i].S});
        ev.pb({pt[i].F + dxr + 1, -1, pt[i].S});
    }

    sort(ev.begin(), ev.end());

    int pv_time = -LNF;
    int Ldis = LNF, Rdis = LNF;
    multiset<int> sums;

    for(auto E : ev){

        int Time = E[0];
        int type = E[1];
        int pos = E[2];

        if(pv_time < Time){
            if(!sums.empty()){
                seg.pb({Ldis, Rdis, *prev(sums.end()), pv_time, Time - 1});
            }
            else{
                seg.pb({Ldis, Rdis, 0, pv_time, Time - 1});
            }
        }

        pv_time = Time;

        if(type == 1){

            st.insert(pos);

            auto it = st.find(pos);
            auto pit = prev(it);
            auto nit = next(it);

            if(it != st.begin() and it != prev(st.end()) ){
                sums.erase( sums.find(*nit - *pit - 1) );
                sums.insert(*nit - *it - 1);
                sums.insert(*it - *pit - 1);
            }
            else if(it == st.begin() and it != prev(st.end()) ){
                sums.insert(*nit - *it - 1);
            }
            else if(it != st.begin() and it == prev(st.end()) ){
                sums.insert(*it - *pit - 1);
            }

        }
        else{

            auto it = st.find(pos);
            auto pit = prev(it);
            auto nit = next(it);

            if(it != st.begin() and it != prev(st.end()) ){
                sums.insert(*nit - *pit - 1);
                sums.erase( sums.find(*nit - *it - 1) );
                sums.erase( sums.find(*it - *pit - 1) );
            }
            else if(it == st.begin() and it != prev(st.end()) ){
                sums.erase( sums.find(*nit - *it - 1) );
            }
            else if(it != st.begin() and it == prev(st.end()) ){
                sums.erase( sums.find(*it - *pit - 1) );
            }

            st.erase(it);

        }

        if(st.empty()){
            Ldis = LNF;
            Rdis = LNF;
        }
        else{
            Ldis = *st.begin() - 1;
            Rdis = C - *prev(st.end());
        }

    }

    seg.pb({LNF, LNF, LNF, pv_time, LNF});

    /*******************************************************/

    int ret = LNF;

    int lptr = 0, rptr = 0;
    multiset<int> Ls, Rs, Sums;

    Ls.insert(seg[0][0]);
    Rs.insert(seg[0][1]);
    Sums.insert(seg[0][2]);

    while(1){

        /// move rptr
        while( (seg[rptr][4] - seg[lptr][3] < R - 1) or (seg[rptr][4] < R) ){
            rptr++;
            Ls.insert(seg[rptr][0]);
            Rs.insert(seg[rptr][1]);
            Sums.insert(seg[rptr][2]);

            //cerr<<"["<<seg[lptr][3]<<", "<<seg[rptr][4]<<"] "<<endl;
        }

        /// update ret
        //cerr<<"["<<lptr<<", "<<rptr<<"], ans = "<<max(*prev(Ls.end()) + *prev(Rs.end()), *prev(Sums.end()) )<<endl;
        ret = min(ret, max(*prev(Ls.end()) + *prev(Rs.end()), *prev(Sums.end()) ) );

        /// move lptr
        Ls.erase( Ls.find(seg[lptr][0]) );
        Rs.erase( Rs.find(seg[lptr][1]) );
        Sums.erase( Sums.find(seg[lptr][2]) );
        lptr++;

        if(seg[lptr][3] > 1 + dxr){
            break;
        }

    }

    int shortest = LNF;
    for(auto I : seg){
        shortest = min(shortest, I[4] - I[3] + 1);
    }
    interesting += shortest;

    return dxr + ret;

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>R>>C;
    cin>>n;
    FOR(i, 1, n, 1){
        cin>>pt[i].F>>pt[i].S;
    }

    res = LNF;

    while(interesting <= 2*R){
        int tmp = check(interesting);
        res = min(res, tmp);
        //cerr<<"check("<<interesting<<") = "<<tmp<<endl;
    }

    cout<<res<<'\n';

    return 0;

}

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