Submission #1170332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170332		imarn	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	1745 ms	157676 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<double>
using namespace std;
const int mxn=1e6+5;
vector<pll>v;
vector<ll>vv;
vector<t3>qr;
struct seg{
    ll t[4*mxn]{0};
    void build(){
        for(int i=0;i<2*mxn;i++)t[i]=2e9;
    }
    void upd(int i,int sz,ll amt){
        i+=sz;t[i]=min(t[i],amt);
        for(i>>=1;i;i>>=1)t[i]=min(t[2*i],t[2*i+1]);
    }
    ll qr(int l,int r,int sz,ll rs=2e9){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)rs=min(rs,t[l++]);
            if(r&1)rs=min(rs,t[--r]);
        }return rs;
    }
}sg[8];
ll ans[mxn]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int x;cin>>x;v.pb({x,x+n});v.pb({x+n,x});
        vv.pb(x);vv.pb(x+n);
    }
    sort(all(v));v.erase(unique(all(v)),v.end());
    sort(all(vv));vv.erase(unique(all(vv)),vv.end());int x=vv.size();
    for(int i=0;i<q;i++){
        ll l,r;cin>>l>>r;
        qr.pb({min(l,r),max(l,r),i});
        ans[i] = min(2*n-abs(l-r),abs(l-r));
    }sort(all(qr));int idx=0;
    for(int i=0;i<8;i++)sg[i].build();
    for(auto [l,r,i] : qr){
        while(idx<v.size()&&v[idx].f<=l){
            sg[0].upd(lb(vv,v[idx].s),x,-v[idx].f-v[idx].s);
            sg[1].upd(lb(vv,v[idx].s),x,2*n+v[idx].f-v[idx].s);
            sg[2].upd(lb(vv,v[idx].s),x,2*n+v[idx].f+2*n+v[idx].s);
            sg[3].upd(lb(vv,v[idx].s),x,-v[idx].f+2*n+v[idx].s);
            sg[4].upd(lb(vv,v[idx].s),x,-v[idx].f+v[idx].s);
            sg[5].upd(lb(vv,v[idx].s),x,-v[idx].f+2*n-v[idx].s);
            sg[6].upd(lb(vv,v[idx].s),x,2*n+v[idx].f+2*n-v[idx].s);
            sg[7].upd(lb(vv,v[idx].s),x,2*n+v[idx].f+v[idx].s);
            idx++;
        }
        ans[i]=min(ans[i],1+l+r+min(sg[0].qr(0,ub(vv,r),x),sg[5].qr(lb(vv,r),x,x)));
        ans[i]=min(ans[i],1+l-r+min(sg[3].qr(0,ub(vv,r),x),sg[4].qr(lb(vv,r),x,x)));
        ans[i]=min(ans[i],1-l+r+min(sg[1].qr(0,ub(vv,r),x),sg[6].qr(lb(vv,r),x,x)));
        ans[i]=min(ans[i],1-l-r+min(sg[2].qr(0,ub(vv,r),x),sg[7].qr(lb(vv,r),x,x)));
    }for(int i=0;i<8;i++)sg[i].build();
    reverse(all(qr));idx=v.size()-1;
    for(auto [l,r,i] : qr){
        while(idx>=0&&v[idx].f>=l){
            sg[0].upd(lb(vv,v[idx].s),x,v[idx].f-v[idx].s);
            sg[1].upd(lb(vv,v[idx].s),x,2*n-v[idx].f-v[idx].s);
            sg[2].upd(lb(vv,v[idx].s),x,2*n-v[idx].f+2*n+v[idx].s);
            sg[3].upd(lb(vv,v[idx].s),x,v[idx].f+2*n+v[idx].s);
            sg[4].upd(lb(vv,v[idx].s),x,v[idx].f+v[idx].s);
            sg[5].upd(lb(vv,v[idx].s),x,v[idx].f+2*n-v[idx].s);
            sg[6].upd(lb(vv,v[idx].s),x,2*n-v[idx].f+2*n-v[idx].s);
            sg[7].upd(lb(vv,v[idx].s),x,2*n-v[idx].f+v[idx].s);
            idx--;
        }
        ans[i]=min(ans[i],1-l+r+min(sg[0].qr(0,ub(vv,r),x),sg[5].qr(lb(vv,r),x,x)));
        ans[i]=min(ans[i],1-l-r+min(sg[3].qr(0,ub(vv,r),x),sg[4].qr(lb(vv,r),x,x)));
        ans[i]=min(ans[i],1+l+r+min(sg[1].qr(0,ub(vv,r),v.size()),sg[6].qr(lb(vv,r),x,x)));
        ans[i]=min(ans[i],1+l-r+min(sg[2].qr(0,ub(vv,r),v.size()),sg[7].qr(lb(vv,r),x,x)));
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 27 / 27