| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1103754 | VinhLuu | Nile (IOI24_nile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define all(vin) vin.begin(), vin.end()
using namespace std;
typedef tuple<ll,ll,ll> tp;
const int N = 2e5 + 5;
const int oo = 2e9;
ll n, q, W[N], a[N], b[N], d[N], c[N], s[N], le[N], ri[N], w[2][N], kq[N], idx[N];
int fin_left(int u){
return le[u] == u ? u : le[u] = fin_left(le[u]);
}
int fin_right(int u){
return ri[u] == u ? u : ri[u] = fin_right(ri[u]);
}
vector<int> open[N], bridge[N];
struct ST{
ll st[N << 1];
void re(int sz){
for(int i = 1; i <= 2 * sz; i ++) st[i] = oo;
}
void update(int i,ll x){
i += n - 1;
st[i] = x;
while(i > 1){
i /= 2;
st[i] = min(st[i << 1], st[i << 1|1]);
}
}
ll get(int l,int r){
if(l > r) return oo;
r++;
ll ret = oo;
for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
if(l & 1) ret = min(ret, st[l ++]);
if(r & 1) ret = min(ret, st[-- r]);
}
return ret;
}
} T[2], tree[2];
vector<long long> calculate_costs(
vector<int> _W, vector<int> A,
vector<int> B, vector<int> E){
n = (int)_W.size();
T[0].re(n);
T[1].re(n);
tree[0].re(n);
tree[1].re(n);
for(int i = 1; i <= n; i ++){
W[i] = _W[i - 1];
a[i] = A[i - 1];
b[i] = B[i - 1];
idx[i] = i;
}
sort(idx + 1, idx + n + 1, [&](int x,int y){return W[x] > W[y];});
ll ans = 0;
for(int id = 1; id <= n; id ++){
int i = idx[id];
tree[id % 2].update(id, a[i] - b[i]);
ans += a[i];
s[id] = s[id - 1] + b[i];
w[0][id] = w[1][id] = a[i];
le[id] = id, ri[id] = id;
}
q = (int)E.size();
for(int i = 1; i <= q; i ++){
d[i] = E[i - 1];
c[i] = i;
}
sort(c + 1, c + q + 1, [&](int x,int y){return d[x] < d[y];});
for(int id = 1; id < n; id ++){
int i = idx[id], nxt = idx[id + 1];
int l = 1, r = q, mid, pos = q + 1;
while(l <= r){
mid = (l + r) / 2;
if(d[c[mid]] >= W[i] - W[nxt]){
pos = mid;
r = mid - 1;
}else l = mid + 1;
}
if(pos != q + 1){
open[pos].push_back(id);
}
}
for(int id = 2; id < n; id ++){
int _left = idx[id - 1], _right = idx[id + 1];
int l = 1, r = q, mid, pos = q + 1;
while(l <= r){
mid = (l + r) / 2;
if(d[c[mid]] >= W[_left] - W[_right]){
pos = mid;
r = mid - 1;
}else l = mid + 1;
}
if(pos != q + 1){
bridge[pos].push_back(id);
}
}
for(int k = 1; k <= q; k ++){
for(auto id : bridge[k]){
int j = idx[id];
T[id % 2].update(id, a[j] - b[j]);
int _left = fin_left(id);
int _right = fin_right(id);
ans = ans - w[0][_left];
ll val = 0;
if((_right - _left + 1) % 2){
int tc = _left % 2;
val = s[_right] - s[_left - 1] + min(tree[tc].get(_left, _right), T[tc ^ 1].get(_left, _right));
}else val = s[_right] - s[_left - 1];
ans += val;
w[0][_left] = w[1][_right] = val;
}
for(auto j : open[k]){
int _right = fin_right(j + 1);
int _left = fin_left(j);
ans = ans - w[0][j + 1] - w[1][j];
ll val = 0;
int tc = _left % 2;
if((_right - _left + 1) % 2){
val = s[_right] - s[_left - 1] + min(tree[tc].get(_left, _right), T[tc ^ 1].get(_left, _right));;
}else val = s[_right] - s[_left - 1];
ans += val;
w[1][_right] = w[0][_left] = val;
ri[j] = j + 1;
le[j + 1] = j;
}
kq[c[k]] = ans;
}
vector<int> _ans;
for(int i = 1; i <= q; i ++) _ans.push_back(kq[i]);
return _ans;
}
//
//signed main(){
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #define task "v"
// if(fopen(task ".inp","r")){
// freopen(task ".inp","r",stdin);
// freopen(task ".ans","w",stdout);
// }
//
// vector<int> _W, _A, _B;
//
// cin >> n;
//
// for(int i = 1; i <= n; i ++){
// int x, y, z; cin >> x >> y >> z;
// _W.push_back(x);
// _A.push_back(y);
// _B.push_back(z);
// }
// vector<int> _E;
// int q; cin >> q;
// for(int i = 1; i <= q; i ++){
// int x; cin >> x;
// _E.push_back(x);
// }
// vector<long long> _ans = calculate_costs(_W, _A, _B, _E);
// for(auto j : _ans) cout << j << "\n";
//
//}