제출 #66124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66124		Benq	Cultivation (JOI17_cultivation)	C++11	30 / 100	2072 ms	2036 KiB

cultivation

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int R,C,N;
ll ans = INF;
vpi p;
vi totest;

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> R >> C >> N; p.resize(N);
    F0R(i,N) {
        cin >> p[i].f >> p[i].s;
        p[i].f --, p[i].s --;
    }
    F0R(i,N) F0R(j,N) totest.pb(p[i].f+R-1-p[j].f);
    F0R(i,N) F0R(j,N) totest.pb(max(p[i].f-p[j].f-1,0));
    sort(all(totest)); totest.erase(unique(all(totest)),totest.end());
}

struct MaxDeque {
    deque<pi> d;
    void ad(int ind, int val) {
        while (sz(d) && d.back().f <= val) d.pop_back();
        d.pb({val,ind});
    }
    void rem(int ind) {
        if (d.front().s == ind) d.pop_front();
    }
    int get() { return d.front().f; }
};

multiset<int> cur, cdif;

array<int,3> get() {
    if (!sz(cur)) return {MOD,MOD,MOD};
    int dif = sz(cdif)?*cdif.rbegin():0;
    dif = max(dif,max(*cur.begin(),C-1-*cur.rbegin()));
    return {*cur.begin(),C-1-*cur.rbegin(),dif};
}

void process(array<int,3> x) {
    if (x[1] == 1) {
        auto it = cur.insert(x[2]);
        if (it != cur.begin() && next(it) != cur.end()) cdif.erase(cdif.find(*next(it)-*prev(it)-1));
        if (it != cur.begin()) cdif.insert(*it-*prev(it)-1);
        if (next(it) != cur.end()) cdif.insert(*next(it)-*it-1);
    } else {
        auto it = cur.find(x[2]);
        if (it != cur.begin()) cdif.erase(cdif.find(*it-*prev(it)-1));
        if (next(it) != cur.end()) cdif.erase(cdif.find(*next(it)-*it-1));
        if (it != cur.begin() && next(it) != cur.end()) cdif.insert(*next(it)-*prev(it)-1);
        cur.erase(it);
    }
}

void tri(int r) {
    vector<array<int,3>> change;
    F0R(i,N) {
        change.pb({p[i].f,1,p[i].s});
        change.pb({p[i].f+r+1,-1,p[i].s});
    }
    sort(all(change));
    
    vector<pair<int,array<int,3>>> dat;
    for (int i = 0; i < sz(change); ) {
        int I = i;
        while (i < sz(change) && change[i][0] == change[I][0]) process(change[i++]);
        dat.pb({change[I][0],get()});
    }
    
    MaxDeque D[3];
    int nex = 0;
    F0R(i,sz(dat)) if (dat[i].f <= r) {
        while (nex < sz(dat) && dat[nex].f < dat[i].f+R) {
            F0R(j,3) D[j].ad(nex,dat[nex].s[j]);
            nex ++;
        }
        if (D[0].get() < MOD) ans = min(ans,(ll)r+max(D[0].get()+D[1].get(),D[2].get()));
        F0R(j,3) D[j].rem(i);
    }
    // cout << r << " " << ans << "\n";
    // 0 <= x <= r
    // consider x to x+R-1
}

int main() {
    init();
    for (int i: totest) tri(i);
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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