Submission #1166235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166235		tsengang	Circle Passing (EGOI24_circlepassing)	C++20	31 / 100	135 ms	8244 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb  push_back
#define ertunt return
#define vodka void
#define sleepearly ertunt
using namespace std;
struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    vodka build(ll v,ll l,ll r){
        if(l == r){
            d[v] = 0;
        }
        ll m = (l+r)/2;
        build(v*2,l,m);
        build(v*2+1,m+1,r);
    }
    vodka update(ll v, ll l, ll r, ll pos, ll val){
        if(pos < l or pos > r)ertunt;
        ll m = (l+r)/2;
        update(v*2,l,m,pos,val);
        update(v*2+1,m+1,r,pos,val);
        d[v] = d[v*2] + d[v*2+1];
    }
    ll query(ll v,ll l, ll r, ll L, ll R){
        if(R < L or R < l or r < L) ertunt 0ll;
        if(L <= l and r <= R)ertunt d[v];
        ll m = (l+r)/2;
        ertunt query(v*2,l,m,L,R) + query(v*2+1,m+1,r,L,R);
    }
};
ll n,m;
ll dist(ll a,ll b){
    ll res = max(a,b)-min(a,b);
    res = min(res,2*n-res);
    sleepearly res;
}
int main(){
    cin >> n >> m;
    ll q;
    cin >> q;
    vector<ll> a(2*m);
    for(ll i = 0; i < m; i++){
        cin >> a[i];
        a[i+m] = a[i] + n;
    }
    while(q--){
        ll x,y;
        cin >> x >> y;
        ll ans = dist(x,y);
        auto it = lower_bound(all(a),x);
        if(it == a.end()){
            it--;
            ll j = *it;
            ans = min(ans,dist(x,j) + 1 + dist(j-n,y));
            auto t = a.begin();
            j = *t;
            ans = min(ans,dist(x,j) + 1 + dist(j+n,y));
            cout << ans << '\n';
            continue;
        }
        if(it == a.begin()){
            ll j = *it;
            ans = min(ans,dist(x,j) + 1 + dist(j+n,y));
            auto t = a.end() - 1;
            j = *t;
            ans = min(ans,dist(x,j) + 1 + dist(j-n,y));
            cout << ans << '\n';
            continue;
        }
        ll j = *it;
        ans = min(ans,dist(x,j) + 1 + dist(j-n,y));
        it--;
        j = *it;
        ans = min(ans,dist(x,j) + 1 + dist(j-n,y));
        cout << ans << '\n';
    }
}

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