제출 #1166235

#제출 시각아이디문제언어결과실행 시간메모리
1166235tsengangCircle Passing (EGOI24_circlepassing)C++20
31 / 100
135 ms8244 KiB
#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'; } }
#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...