제출 #1075210

#제출 시각아이디문제언어결과실행 시간메모리
1075210aintaCultivation (JOI17_cultivation)C++17
65 / 100
2099 ms7888 KiB
#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; const int SZ = 1024; struct Tree{ int Mn[SZ+SZ], K[SZ+SZ]; void UDT(int nd){ Mn[nd] = min(Mn[nd*2],Mn[nd*2+1]); } void Add2(int nd, int k){ Mn[nd] += k; K[nd] += k; } void Spread(int nd){ Add2(nd*2, K[nd]); Add2(nd*2+1, K[nd]); K[nd]=0; } void init(int nd, int b, int e){ K[nd]=0; if(b==e){ Mn[nd]=0; return; } int m = (b+e)>>1; init(nd*2,b,m); init(nd*2+1,m+1,e); UDT(nd); } void Add(int nd, int b, int e, int s, int l, int x){ if(s>l)return; if(s<=b&&e<=l){ Add2(nd,x); return; } Spread(nd); int m = (b+e)>>1; if(s<=m)Add(nd*2,b,m,s,l,x); if(l>m)Add(nd*2+1,m+1,e,s,l,x); UDT(nd); } int getLeft(int nd, int b, int e, int x){ if(Mn[nd])return SZ; if(b==e)return b; Spread(nd); int m = (b+e)>>1; if(x<=m)return getLeft(nd*2,b,m,x); int r = getLeft(nd*2+1,m+1,e,x); if(r==SZ)r = getLeft(nd*2,b,m,x); return r; } int getRight(int nd, int b, int e, int x){ if(Mn[nd])return -1; if(b==e)return b; Spread(nd); int m = (b+e)>>1; if(x>m)return getRight(nd*2+1,m+1,e,x); int r = getRight(nd*2,b,m,x); if(r==-1)r = getRight(nd*2+1,m+1,e,x); return r; } }IT; struct IdxTree{ int IT[SZ+SZ]; void Put(int a, int b){ a+=SZ; IT[a]=b; while(a!=1){ a>>=1; IT[a]=max(IT[a*2],IT[a*2+1]); } } int Max(int b, int e){ b+=SZ,e+=SZ; int r=-1e9; while(b<=e){ r=max(r,IT[b]); r=max(r,IT[e]); b=(b+1)>>1,e=(e-1)>>1; } return r; } }LL, RR; bool Pos(int x, int y, vc<pii> &w){ vc<t4>S; vc<pii> Y; rep(i,n){ Y.pb({w[i].se-y, i}); Y.pb({w[i].se, i+n}); } Y.pb({0,2*n}); sort(all(Y)); vi RY(n*2+1), OY(n*2+2); int cy=0; rep(i,si(Y)){ if(i==0 || Y[i].fi!=Y[i-1].fi){ cy++; OY[cy] = Y[i].fi; } RY[Y[i].se] = cy; } rep(i,n){ S.pb({w[i].fi - x, 1, RY[i], RY[i+n]}); S.pb({w[i].fi, -1, RY[i], RY[i+n]}); } int my = RY[n*2]; sort(all(S)); IT.init(1,0,SZ-1); vi U; rep(i,si(S)){ auto [x, d, by, ey] = S[i]; IT.Add(1,0,SZ-1,by,ey-1,d); if(i==si(S)-1 || x != get<0>(S[i+1])){ int l = IT.getLeft(1,0,SZ-1,my); l++; int r = IT.getRight(1,0,SZ-1,my); LL.Put(si(U),l); RR.Put(si(U),-r); U.pb(x); } } int pv = 0; rep(i,si(U)){ while(pv<si(U) && (ll)U[pv] - U[i] < H)pv++; if(pv==si(U))return false; int l2 = LL.Max(i,pv-1); int r2 = -RR.Max(i,pv-1); if(l2<r2 && (ll)OY[r2] - OY[l2] >= W)return true; } return false; } void Solve(){ scanf("%d%d",&H,&W); scanf("%d",&n); vc<pii>w(n); rep(i,n){ scanf("%d%d",&w[i].fi,&w[i].se); } set<int>SX, SY; rep(i,n){ rep(j,n){ SX.insert(abs(w[i].fi-w[j].fi)); SY.insert(abs(w[i].se-w[j].se)); SX.insert(w[i].fi + H-w[j].fi); SY.insert(w[i].se + W-w[j].se); } } SX.erase(0);SY.erase(0); SX.insert(H);SY.insert(W); vi X, Y; for(auto &t: SX)X.pb(t); for(auto &t: SY)Y.pb(t); int p1 = 0, p2 = si(Y)-1; ll res=2e9; /* for(auto &x : X)printf("%d ",x); puts(""); for(auto &y : Y)printf("%d ",y); puts("");*/ while(p1 < si(X) && p2 >= 0){ //printf("%d %d\n",X[p1],Y[p2]); if(Pos(X[p1],Y[p2],w)){ //printf("%d %d\n",X[p1],Y[p2]); res = min(res, (ll)X[p1]+Y[p2]-2); p2--; } else p1++; } printf("%lld\n",res); } int main(){ int TC=1; while(TC--){ Solve(); } }

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

cultivation.cpp: In function 'void Solve()':
cultivation.cpp:211:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |     scanf("%d%d",&H,&W);
      |     ~~~~~^~~~~~~~~~~~~~
cultivation.cpp:212:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
cultivation.cpp:215:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         scanf("%d%d",&w[i].fi,&w[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...