Submission #760809

#TimeUsernameProblemLanguageResultExecution timeMemory
760809azberjibiouDouble Attendance (CCO22_day1problem3)C++17
5 / 25
4 ms724 KiB
#include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define gibon ios::sync_with_stdio(false); cin.tie(0); #define fi first #define se second #define pdd pair<long double, long double> #define pii pair<int, int> #define pll pair<ll, ll> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") typedef long long ll; using namespace std; const int mxN=300020; const int mxK=14; const int MOD=1000000007; const ll INF=1e18; int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1}; ll N[2], K, M; pll A[2][mxN]; vector <pll> coor; ll dp[2][mxN]; ll ans; bool add_zero; pll seg1[2][4*mxN]; ll seg2[2][4*mxN]; void upd2(int idx, int s, int e, int pos, int val, int i) { if(s==e) { seg2[i][idx]=val; return; } int mid=(s+e)/2; if(pos<=mid) upd2(2*idx, s, mid, pos, val, i); else upd2(2*idx+1, mid+1, e, pos, val, i); seg2[i][idx]=max(seg2[i][2*idx], seg2[i][2*idx+1]); } int solv2(int idx, int s1, int e1, int s2, int e2, int i) { if(s2<=s1 && e1<=e2) return seg2[i][idx]; if(s2>e1 || s1>e2) return 0; int mid=(s1+e1)/2; return max(solv2(2*idx, s1, mid, s2, e2, i), solv2(2*idx+1, mid+1, e1, s2, e2, i)); } void init1(int idx, int s, int e) { if(s==e) seg1[0][idx]=pll(A[0][s].fi-2*K*s, A[0][s].se-2*K*s), seg1[1][idx]=pll(A[1][s].fi-2*K*s, A[1][s].se-2*K*s); else { int mid=(s+e)/2; init1(2*idx, s, mid); init1(2*idx+1, mid+1, e); for(int i=0;i<2;i++) { seg1[i][idx].fi=max(seg1[i][2*idx].fi, seg1[i][2*idx+1].fi); seg1[i][idx].se=min(seg1[i][2*idx].se, seg1[i][2*idx+1].se); } } } pll solv1(int idx, int s1, int e1, int s2, int e2, int i) { if(s2<=s1 && e1<=e2) return seg1[i][idx]; if(s2>e1 || s1>e2) return pll(-INF, INF); int mid=(s1+e1)/2; pll r1=solv1(2*idx, s1, mid, s2, e2, i), r2=solv1(2*idx+1, mid+1, e1, s2, e2, i); return pll(max(r1.fi, r2.fi), min(r1.se, r2.se)); } void input() { cin >> N[0] >> N[1] >> K; for(int i=0;i<N[0];i++) cin >> A[0][i].fi >> A[0][i].se, A[0][i].se--; for(int i=0;i<N[1];i++) cin >> A[1][i].fi >> A[1][i].se, A[1][i].se--; sort(A[0], A[0]+N[0]); sort(A[1], A[1]+N[1]); if(A[0][0].fi!=0) { add_zero=true; for(int i=N[0];i>=1;i--) A[0][i]=A[0][i-1]; A[0][0]=pii(0, 0); N[0]++; } M=max(N[0], N[1]); } void make_coor() { for(int i=0;i<2;i++) for(int j=0;j<N[i];j++) coor.emplace_back(i, j); sort(all(coor), [](pii a, pii b){return A[a.fi][a.se].fi>A[b.fi][b.se].fi;}); } ll f(int idx, int s, int lim) { if(s==N[idx]) return 0; if(A[idx][s].fi>lim-K) return dp[idx][s]; int e1=lower_bound(A[idx], A[idx]+N[idx], pll(lim-K+1, 0), [](pll a, pll b){return a.fi<b.fi;})-A[idx]; int e2=lower_bound(A[1-idx], A[1-idx]+N[1-idx], pll(lim+1, 0), [](pll a, pll b){return a.fi<b.fi;})-A[1-idx]; ll res=0; res=max(res, e1-s+dp[idx][e1]); res=max(res, e1-s-2+dp[idx][e1-1]); return res; } int bin_search1(int idx, int s1, int e1, int s2, int e2, ll val, int i) { if(s2>e1 || s1>e2) return e1+1; if(s2<=s1 && e1<=e2) { if(seg1[i][idx].fi<=val && seg1[i][idx].se>=val) return e1+1; if(s1==e1) return s1; } int mid=(s1+e1)/2; int res1=bin_search1(2*idx, s1, mid, s2, e2, val, i); if(res1!=mid+1) return res1; return bin_search1(2*idx+1, mid+1, e1, s2, e2, val, i); } int bin_search1(int idx, ll val, int s, int e) { pll tmp=solv1(1, 0, M-1, s, e, idx); if(val<=tmp.se && val>=tmp.fi) return e; return bin_search1(1, 0, M-1, s, e, val, idx)-1; /* while(s!=e) { int mid=(s+e)/2; tmp=solv1(1, 0, M-1, s, mid, idx); if(val<=tmp.se && val>=tmp.fi) s=mid+1; else e=mid; } return s-1;*/ } void mx(ll &a, ll b){a=max(a, b);} int main() { gibon input(); make_coor(); init1(1, 0, M-1); upd2(1, 0, M, N[0], 2*N[0], 0); upd2(1, 0, M, N[1], 2*N[1], 1); for(auto [idx, now] : coor) { ll nc=A[idx][now].fi; dp[idx][now]=dp[idx][now+1]+1; ll s1=now, s2=lower_bound(A[1-idx], A[1-idx]+N[1-idx], pll(nc+K, nc+K), [](pll a, pll b){return a.se<b.se;})-A[1-idx]; if(s2==N[1-idx]) { upd2(1, 0, M-1, now, dp[idx][now]+2*now, idx); continue; } if(A[1-idx][s2].fi>nc+K) { mx(dp[idx][now], f(1-idx, s2, A[idx][now].se)+1); upd2(1, 0, M-1, now, dp[idx][now]+2*now, idx); continue; } ll c1=bin_search1(idx, nc-2*K*s1, s1, N[idx]-1), c2=bin_search1(1-idx, nc+K-2*K*s2, s2, N[1-idx]-1); //ll c1=bin_search1(1, 0, M-1, s1, N[idx]-1, nc-2*K*s1, idx)-1, c2=bin_search1(1, 0, M-1, s2, N[1-idx]-1, nc+K-2*K*s2, 1-idx)-1; /* ll c1=s1, c2=s2; while(c1+1<N[idx] && nc+2*K*(c1+1-s1)<=A[idx][c1+1].se && nc+2*K*(c1+1-s1)>=A[idx][c1+1].fi) c1++; while(c2+1<N[1-idx] && nc+2*K*(c2+1-s2)+K<=A[1-idx][c2+1].se && nc+2*K*(c2+1-s2)+K>=A[1-idx][c2+1].fi) c2++; */ if(c2-s2<c1-s1-1) c1=c2-s2+s1+1; if(c2-s2>c1-s1) c2=c1-s1+s2; if(c2-s2==c1-s1) { mx(dp[idx][now], solv2(1, 0, M, s1+1, c1+1, idx)-2*s1-1); if(s2<=c2-1) mx(dp[idx][now], solv2(1, 0, M, s2+1, c2, 1-idx)-2*s2); /* for(int i=s1;i<=c1;i++) mx(dp[idx][now], dp[idx][i+1]+2*(i-s1)+1); for(int i=s2;i<c2;i++) mx(dp[idx][now], dp[1-idx][i+1]+2*(i-s2)+2); */ mx(dp[idx][now], f(1-idx, c2+1, A[idx][c1].se)+c1-s1+c2-s2+2); ll nxt=nc+2*K*(c1-s1+1); if(c1+1<N[idx] && nxt<A[idx][c1+1].fi) mx(dp[idx][now], f(idx, c1+1, A[1-idx][c2].se)+2*(c1-s1+1)); } else { if(s1<=c1-1) mx(dp[idx][now], solv2(1, 0, M, s1+1, c1, idx)-2*s1-1); mx(dp[idx][now], solv2(1, 0, M, s2+1, c2+1, 1-idx)-2*s2); /* for(int i=s1;i<c1;i++) mx(dp[idx][now], dp[idx][i+1]+2*(i-s1)+1); for(int i=s2;i<=c2;i++) mx(dp[idx][now], dp[1-idx][i+1]+2*(i-s2)+2); */ mx(dp[idx][now], f(idx, c1+1, A[1-idx][c2].se)+2*(c1-s1)+1); ll nxt=nc+2*K*(c1-s1)+K; if(c2+1<N[1-idx] && nxt<A[1-idx][c2+1].fi) mx(dp[idx][now], f(1-idx, c2+1, A[idx][c1].se)+2*(c1-s1)+1); } upd2(1, 0, M, now, dp[idx][now]+2*now, idx); } cout << dp[0][0]-(add_zero ? 1 : 0); } /* 3 3 10 1 30 31 60 61 90 15 45 45 90 90 120 */

Compilation message (stderr)

Main.cpp: In function 'll f(int, int, int)':
Main.cpp:96:9: warning: unused variable 'e2' [-Wunused-variable]
   96 |     int e2=lower_bound(A[1-idx], A[1-idx]+N[1-idx], pll(lim+1, 0), [](pll a, pll b){return a.fi<b.fi;})-A[1-idx];
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...