Submission #760809

#	Time	Username	Problem	Language	Result	Execution time	Memory
760809		azberjibiou	Double Attendance (CCO22_day1problem3)	C++17	5 / 25	4 ms	724 KiB

Main

#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];
      |         ^~

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