Submission #1077338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077338		ainta	Cultivation (JOI17_cultivation)	C++17	100 / 100	1612 ms	5816 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
 
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
 
ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}
 
 
template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;
template<> const Mint Mint::G = Mint(3);
 
using t4 = tuple<int,int,int,int>;
 
int H, W, n;
int res=2e9;
 
void Solve(){
    scanf("%d%d",&H,&W);
    scanf("%d",&n);
    vc<pii>w(n);
    set<int>SX, SY;
    rep(i,n){
        scanf("%d%d",&w[i].fi,&w[i].se);
        SX.insert(w[i].fi);SX.insert(w[i].fi+H);
        SY.insert(w[i].se);SY.insert(w[i].se+W);
    }
    vi X, Y;
    for(auto &t: SX)X.pb(t);
    for(auto &t: SY)Y.pb(t);
 
    rep(i,n){
        w[i].fi = lower_bound(all(X), w[i].fi) - X.begin();
        w[i].se = lower_bound(all(Y), w[i].se) - Y.begin();
    }
    vi DX, DY;
    rep(i,si(X)){
        rng(j,i+1,si(X)-1)DX.pb(X[j]-X[i]);
    }
    rep(i,si(Y)){
        rng(j,i+1,si(Y)-1)DY.pb(Y[j]-Y[i]);
    }
    sort(all(DX));
    DX.resize(unique(all(DX)) - DX.begin());
    sort(all(DY));
    DY.resize(unique(all(DY)) - DY.begin());
 
    int nX = si(X), nY = si(Y);
    vi PX(n), PY(n);
    vc<vi> S(nX,vi(nY));
    rep(i,n){
        PX[i] = w[i].fi;
        PY[i] = nY-1;
    }
    vc<priority_queue<int>>PQ1(nX), PQ2(nX);
 
    int mY = lower_bound(all(Y),W+1) - Y.begin();
 
    auto add0 = [&](int x, int y){
        if(y<=mY) PQ1[x].push(y);
        else PQ2[x].push(-y);
    };
 
    auto getLeft = [&](int x){
        while(!PQ1[x].empty()){
            int y = PQ1[x].top();
            if(!S[x][y])return y;
            PQ1[x].pop();
        }
        return 0;
    };
    auto getRight = [&](int x){
        while(!PQ2[x].empty()){
            int y = -PQ2[x].top();
            if(!S[x][y])return y;
            PQ2[x].pop();
        }
        return nY;
    };
    ll ans = 1e10;
    rng(i,1,nX-1){
        rng(j,1,nY-1){
            add0(i,j);
        }
    }
    vi LL(nX), RR(nX), dL(nX), dR(nX);
    int pdy = si(DY)-1, dy = DY.back();
    for(auto &dx : DX){
        rep(i,n){
            int bx = w[i].fi;
            int by = w[i].se;
            while(PX[i] < nX - 1 && X[PX[i]+1] - X[bx] <= dx){
                PX[i]++;
                rng(j,by+1,PY[i]){
                    S[PX[i]][j]++;
                }
            }
        }
        while(1){
            /*printf("! %d %d\n",dx,dy);
            rng(i,1,nX-1){
                rng(j,1,nY-1){
                    printf("%d",S[i][j]);
                }
                puts("");
            }*/
            rng(i,1,nX-1){
                LL[i] = getLeft(i);
                RR[i] = getRight(i);
                if(LL[i]==mY)RR[i]=mY;
                RR[i]--;
                //printf("%d %d %d\n",LL[i],mY,RR[i]);
                //printf("%d: %d %d\n",X[i],Y[LL[i]],Y[RR[i]]);
            }
            int hL=1, tL=0;
            int hR=1, tR=0, CK=0;
            rng(i,1,nX-1){
                while(hL <= tL && X[i] - X[dL[hL]] >= H)hL++;
                while(hL <= tL && LL[dL[tL]] <= LL[i])tL--;
                dL[++tL] = i;
                int l = LL[dL[hL]];
 
                while(hR <= tR && X[i] - X[dR[hR]] >= H)hR++;
                while(hR <= tR && RR[dR[tR]] >= RR[i])tR--;
                dR[++tR] = i;
                int r = RR[dR[hR]];
 
                //printf("%d %d %d %d\n",X[i],X[0],Y[r],Y[l]);
 
                if(X[i]-X[0] >= H && Y[r]-Y[l] >= W){
                    //printf("%d %d %d %d\n",dx,dy,Y[l],Y[r]);
                    ans = min(ans, (ll)dx+dy-2);
                    CK=1;
                    break;
                }
            }
            if(!CK)break;
            pdy--;
            if(pdy<0)break;
            dy = DY[pdy];
            rep(i,n){
                int bx = w[i].fi;
                int by = w[i].se;
                while(Y[PY[i]] - Y[by] > dy){
                    rng(j,bx+1,PX[i]){
                        S[j][PY[i]]--;
                        if(!S[j][PY[i]])add0(j,PY[i]);
                    }
                    PY[i]--;
                }
            }
        }
        if(pdy<0)break;
    }
    printf("%lld\n",ans);
}
 
int main(){
	int TC=1;
	while(TC--){
		Solve();
	}
}

Compilation message (stderr)

cultivation.cpp: In function 'void Solve()':
cultivation.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d%d",&H,&W);
      |     ~~~~~^~~~~~~~~~~~~~
cultivation.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
cultivation.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d%d",&w[i].fi,&w[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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