Submission #233013

#TimeUsernameProblemLanguageResultExecution timeMemory
233013amoo_safarSvjetlost (COI18_svjetlost)C++14
26 / 100
18 ms640 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef long long ll; typedef double ld; typedef string str; typedef pair<ll, ll> pll; const ll Mod = 1000000007LL; const int N = 1e5 + 10; const ll Inf = 2242545357980376863LL; const ll Log = 30; ld seg[N << 2]; ld lz[N << 2]; void Add(int id, int l, int r, ld x, int L, int R){ if((r <= L) || (R <= l)) return ; if((l <= L) && (R <= r)){ lz[id] += x; seg[id] += x; return ; } int mid = (L + R) >> 1; Add(id << 1, l, r, x, L, mid); Add(id << 1 | 1, l, r, x, mid, R); seg[id] = max(seg[id << 1], seg[id << 1 | 1]) + lz[id]; } pll operator - (pll a, pll b){ return {a.F - b.F, a.S - b.S}; } pll operator + (pll a, pll b){ return {a.F - b.F, a.S - b.S}; } ll operator * (pll a, pll b){ return a.F * b.S - a.S * b.F; } typedef pair<pll, ll> nd; struct CMP { bool operator() (nd A, nd B) const { pll a = A.F, b = B.F; if(a == b) return A.S < B.S; int fa = a < pll(0, 0); int fb = b < pll(0, 0); if(fa != fb) return fa > fb; return a*b > 0; } }; multiset<nd, CMP> ms; ll n; ll nx[N], bf[N]; pll p[N]; int Match(int x){ pll e = p[x] - p[nx[x]]; auto it = ms.lower_bound({e, -1}); if(it == ms.begin()) it = --ms.end(); else it --; return it -> S; } int RevMatch(int x){ int res = bf[bf[x]]; while((p[bf[x]] - p[x]) * (p[res] - p[nx[res]]) < 0) res = bf[res]; return nx[res]; } ld Len(pll x){ return sqrt(x.F*x.F + x.S*x.S); } void Add(int l, int r, ld ln){ if(l <= r){ Add(1, l, r + 1, ln, 0, n); } else { Add(1, l, n, ln, 0, n); Add(1, 0, r + 1, ln, 0, n); } } void Apply(int x, ld z){ Add(nx[x], Match(x), z*Len(p[nx[x]] - p[x])); } void Rem(int x){ int L, R; Apply(bf[x], -1); Apply(x, -1); L = RevMatch(x); R = RevMatch(nx[x]); ms.erase(ms.find({p[nx[x]] - p[x], nx[x]})); ms.erase(ms.find({p[x] - p[bf[x]], x})); bf[nx[x]] = bf[x]; nx[bf[x]] = nx[x]; ms.insert({p[nx[x]] - p[bf[x]], nx[x]}); Apply(bf[x], 1); Add(1, x, x + 1, -1e15, 0, n); ld sm = 0; //assert(L == R); //cerr << L << ' ' << R << '\n'; while(L != R){ /*debug(L); debug(((p[nx[L]] - p[L]) * (p[nx[x]] - p[bf[x]]))); debug((p[nx[L]] - p[L]).F); debug((p[nx[L]] - p[L]).S); debug((p[nx[x]] - p[bf[x]]).F); debug((p[nx[x]] - p[bf[x]]).S); */ if( ((p[nx[L]] - p[L]) * (p[nx[x]] - p[bf[x]])) > 0) sm += Len(p[L] - p[nx[L]]); L = nx[L]; } //assert(sm == 0); //assert(sm < 1); //cerr << sm << '\n'; Add(1, nx[x], nx[x] + 1, sm, 0, n); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; assert(n <= 2000); for(int i = 0; i < n; i++) cin >> p[i]. F >> p[i].S; for(int i = 0; i < n; i++) nx[i] = (i + 1) % n; for(int i = 0; i < n; i++) bf[nx[i]] = i; for(int i = 0; i < n; i++) ms.insert({ p[i] - p[bf[i]], i }); for(int i = 0; i < n; i++) Apply(i, 1); cout << fixed << setprecision(6) << seg[1] << '\n'; //for(int i = 0; i < n; i++) cerr << i << ' ' << RevMatch(i) << ' ' << Match(i) << '\n'; ll Q; cin >> Q; int rm; for(int i = 0; i < Q; i++){ cin >> rm; rm --; Rem(rm); cout << fixed << setprecision(6) << seg[1] << '\n'; } return 0; } /* 3 0 0 1 0 0 1 0 4 0 0 2 0 2 2 0 2 1 1 */
#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...