제출 #204203

#제출 시각아이디문제언어결과실행 시간메모리
204203kig9981Cultivation (JOI17_cultivation)C++17
0 / 100
8 ms380 KiB
#include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; const int SZ=1<<10; int X, Y, tree[2*SZ], lazy[2*SZ]; vector<pair<int,int>> P; vector<tuple<int,int,int>> Q; vector<int> x; void lazy_propagation(int bit, int s, int e) { if(lazy[bit]>-1) { tree[bit]=lazy[bit]; if(s<e) lazy[2*bit]=lazy[2*bit+1]=lazy[bit]; lazy[bit]=-1; } } void set_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1) { int m=(s+e)>>1; lazy_propagation(bit,s,e); if(n2<n1 || n2<s || e<n1) return; if(n1<=s && e<=n2) { lazy[bit]=v; return; } set_tree(n1,n2,v,2*bit,s,m); set_tree(n1,n2,v,2*bit+1,m+1,e); tree[bit]=min(tree[2*bit],tree[2*bit+1]); } int get_min(int n1, int n2, int bit=1, int s=0, int e=SZ-1) { int m=(s+e)>>1; lazy_propagation(bit,s,e); if(n2<n1 || n2<s || e<n1) return 0x7fffffff; if(n1<=s && e<=n2) return tree[bit]; return min(get_min(n1,n2,2*bit,s,m),get_min(n1,n2,2*bit+1,m+1,e)); } long long solve(int dl, int dr) { int M=0; x.clear(); for(auto[a,b]: P) { x.push_back(max(a-dl,1)); x.push_back(min(a+dr,X)+1); } sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin()); Q.clear(); for(auto[a,b]: P) { int l=lower_bound(x.begin(),x.end(),max(a-dl,1))-x.begin(), r=lower_bound(x.begin(),x.end(),min(a+dr,X)+1)-x.begin()-1; Q.emplace_back(b,l,r); } sort(Q.begin(),Q.end()); Q.emplace_back(Y,0,x.size()-1); lazy[1]=1; for(auto[v,l,r]: Q) { M=max(M,v-get_min(l,r)-1); set_tree(l,r,v); } return dl+dr+M; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); TEST(freopen("input.txt","r",stdin)); TEST(freopen("output.txt","w",stdout)); TEST(freopen("debug.txt","w",stderr)); int N, M; long long ans=0x7fffffffffffffffLL; cin>>X>>Y>>N; P.resize(N); for(auto &[a,b]: P) cin>>a>>b; sort(P.begin(),P.end()); M=max(P[0].first-1,X-P[N-1].first); for(int i=1;i<N;i++) M=max(M,P[i].first-P[i-1].first-1); for(int i=0;i<N;i++) for(int j=0;j<N;j++) { int dl=P[i].first-1, dr=X-P[j].first; ans=min(ans,solve(dl,max(dr,M-dl))); ans=min(ans,solve(max(dl,M-dr),dr)); } cout<<ans<<'\n'; return 0; }

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

cultivation.cpp: In function 'long long int solve(int, int)':
cultivation.cpp:55:14: warning: unused variable 'b' [-Wunused-variable]
  for(auto[a,b]: P) {
              ^
#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...