제출 #1117210

#제출 시각아이디문제언어결과실행 시간메모리
1117210thelegendary08나일강 (IOI24_nile)C++17
100 / 100
148 ms51776 KiB
#include "nile.h" #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define ll long long #define vi vector<ll> #define pb push_back #define f0r(i,n) for(int i = 0; i<n;i++) #define pii pair<ll,ll> using namespace std; //using namespace __gnu_pbds; const int mxn = 100005; vector<vi> tree(mxn*4, vi(4, 4e18)); //good, odd //good, even //bad, odd //bad, even int n; void upd(int k, ll x, int t){ k += n; tree[k][t] = x; for(k /= 2; k>=1; k/=2){ tree[k][t] = min(tree[k*2][t], tree[k*2+1][t]); } } ll quer(int l, int r, int t){ l += n; r += n; ll ret = 4e18; while(l <= r){ if(l % 2 == 1){ if(ret > tree[l][t]){ ret = tree[l][t]; } l++; } if(r % 2 == 0){ if(ret > tree[r][t]){ ret = tree[r][t]; } r--; } l/=2; r/=2; } return ret; } vi sz(mxn, 1); vi par(mxn, 0); vector<pair<ll,ll>>rng(mxn); vi anst(mxn); ll ca = 0; int get(int x){ while(par[x] != x)x = par[x]; return x; } pair<ll,ll> mrg(pii a, pii b){ if(a > b)swap(a, b); return {a.first, b.second}; } void unite(int a, int b){ //cout<<a<<' '<<b<<'\n'; a = get(a); b = get(b); if(sz[a] < sz[b])swap(a, b); par[b] = a; sz[a] += sz[b]; ca -= anst[a]; ca -= anst[b]; //cout<<anst[a]<<' '<<anst[b]<<'\n'; rng[a] = mrg(rng[a], rng[b]); //cout<<rng[a].first<<' '<<rng[a].second<<'\n'; //ca += (sz[a] % 2); int l = rng[a].first; int r = rng[a].second; if((r - l + 1) % 2 == 0)anst[a] = 0; else{ if(l % 2 == 1){ anst[a] = min(quer(l, r, 0), quer(l, r, 3)); } else anst[a] = min(quer(l, r, 1), quer(l, r, 2)); } //cout<<anst[a]<<'\n'; ca += anst[a]; //cout<<ans[a]<<' '<<ans[b]<<' '<<(sz[a] % 2)<<'\n'; //ans[a] = (sz[a] % 2); //cout<<a<<' '<<ans[a]<<'\n'; //cout<<'\n'; } std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) { int q = e.size(); n = w.size(); f0r(i, n){ par[i] = i; rng[i] = {i,i}; } vi ans(q, 0); vector<pair<ll,ll>>quers; f0r(i, q)quers.pb({e[i], i}); sort(quers.begin(), quers.end()); ll s=0; f0r(i,n)s += b[i]; vi c(n); f0r(i, n){ c[i] = a[i] - b[i]; } ca = 0; f0r(i, n)ca += c[i]; //cout<<ca<<'\n'; vector<pair<ll,ll>>tmp; f0r(i,n){ tmp.pb({w[i], c[i]}); } sort(tmp.begin(), tmp.end()); f0r(i, n){ w[i] = tmp[i].first; c[i] = tmp[i].second; } f0r(i, n)anst[i] = c[i]; //for(auto u : c)cout<<u<<' '; //cout<<'\n'; vector<pair<ll,ll>>connectors; f0r(i, n-1){ connectors.pb({w[i+1] - w[i], i}); } sort(connectors.begin(), connectors.end()); vector<pair<ll,ll>>mids; for(int i = 1; i<n-1; i++){ mids.pb({w[i+1] - w[i-1], i}); } sort(mids.begin(), mids.end()); vector<pair<pair<int,int>,int>>ranges; f0r(i,n)ranges.pb({{i,i}, c[i]}); int p1 = 0; int p2 = 0; f0r(i, n){ if(i % 2 == 1){ upd(i, c[i], 0); } else upd(i, c[i], 1); } f0r(tt, q){ ll k = quers[tt].first; //cout<<k<<'\n'; while(p2 < n-2 && k >= mids[p2].first){ int dex = mids[p2].second; if(dex % 2 == 1){ upd(dex, c[dex], 2); } else{ upd(dex, c[dex], 3); } int parr = get(dex); if(anst[parr] > c[dex]){ ca -= anst[parr]; ca += c[dex]; anst[parr] = c[dex]; } p2++; } while(p1 < n-1 && k >= connectors[p1].first){ int dex = connectors[p1].second; /* int l = 0; int r = ranges.size(); while(l < r){ int mid = (l + r)/2; if(ranges[mid].first.first < ) } */ unite(dex, dex + 1); p1++; } //cout<<ca<<'\n'; /* ll curans = 0; ll cs = 0; vector<pair<int,int>>ranges; f0r(j, n-1){ if(w[j+1] - w[j] > k){ ranges.pb({cs, j}); cs = j+1; } } ranges.pb({cs, n-1}); //for(auto u : ranges)cout<<u.first<<' '<<u.second<<'\n'; f0r(i, ranges.size()){ int l = ranges[i].first; int r = ranges[i].second; if((r - l + 1) % 2 == 1){ ll cur = 4e18; for(int j = l; j<=r; j++){ if((j - l) % 2 == 0)cur = min(cur, c[j]); else{ if(w[j+1] - w[j-1] <= k)cur = min(cur, c[j]); } } //cout<<cur<<"cur"<<'\n'; curans += cur; } } */ ans[tt] = s + ca; //cout<<ca<<'\n'; //cout<<'\n'; } vi anss(q); f0r(i,q){ anss[quers[i].second] = ans[i]; } return anss; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...