| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1102235 |
2024-10-17T16:56:17 Z |
nhphuc |
Nile (IOI24_nile) |
C++17 |
|
2000 ms |
20284 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
void init (vector<int32_t> &a, vector<pair<int, int>> &b){
vector<int32_t> tmp = a;
for (int i = 0; i < b.size(); ++i)
a[i] = tmp[b[i].second];
return;
}
const int N = 100007;
const int inf = 1e12;
vector<int> par(N), lef(N), rig(N), sum(N), sz(N), val(N), t(N * 4, inf);
void upd (int id, int l, int r, int k, int x){
if (l == r){
t[id] = x;
return;
}
int m = l + r >> 1;
upd(id * 2 + 1, l, m, k, x);
upd(id * 2 + 2, m + 1, r, k, x);
t[id] = min(t[id * 2], t[id * 2 + 1]);
}
int get (int id, int l, int r, int u, int v){
if (l > v || r < u)
return inf;
if (l >= u && r <= v)
return t[id];
int m = l + r >> 1;
return min(get(id * 2 + 1, l, m, u, v), get(id * 2 + 2, m + 1, r, u, v));
}
int acs (int u){
return (u == par[u] ? u : par[u] = acs(par[u]));
}
vector<int> calculate_costs (
vector<int32_t> w, vector<int32_t> a,
vector<int32_t> b, vector<int32_t> e
){
int n = a.size(), q = e.size();
vector<int> ans(q), c(n);
vector<pair<int, int>> d(q), x(n);
vector<array<int, 3>> events;
for (int i = 0; i < n; ++i)
x[i] = {w[i], i};
for (int i = 0; i < q; ++i)
d[i] = {e[i], i};
sort(d.begin(), d.end());
sort(x.begin(), x.end());
init(a, x);
init(b, x);
init(w, x);
int res = 0;
for (int i = 0; i < n; ++i){
res += 1ll * a[i];
par[i] = i;
lef[i] = i;
rig[i] = i;
sz[i] = 1;
c[i] = a[i] - b[i];
sum[i] = b[i];
val[i] = a[i];
}
for (int i = 0; i < n; ++i){
if (i + 1 < n)
events.push_back({w[i + 1] - w[i], i, 1});
if (i + 2 < n)
events.push_back({w[i + 2] - w[i], i, 0});
}
sort(events.begin(), events.end());
int j = 0;
for (auto [x, y] : d){
while (j < events.size() && events[j][0] <= x){
if (events[j][2] == 0){
int i = events[j][1], u = acs(i);
upd(0, 0, n - 1, i + 1, c[i + 1]);
res -= val[u];
int rg = (lef[u] + 1 < rig[u] ? get(0, 0, n - 1, lef[u] + 1, rig[u] - 1) : inf);
int mn = min({c[lef[u]], c[rig[u]], rg});
val[u] = sum[u] + (sz[u] % 2ll) * mn;
res += val[u];
++j;
continue;
}
int i = events[j][1];
int u = acs(i);
int v = acs(i + 1);
res -= (val[u] + val[v]);
if (sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
lef[u] = min(lef[u], lef[v]);
rig[u] = max(rig[u], rig[v]);
sum[u] += sum[v];
int rg = (lef[u] + 1 < rig[u] ? get(0, 0, n - 1, lef[u] + 1, rig[u] - 1) : inf);
int mn = min({c[lef[u]], c[rig[u]], rg});
val[u] = sum[u] + (sz[u] % 2ll) * mn;
res += val[u];
++j;
}
ans[y] = res;
}
return ans;
}
// int32_t main (){
// #define task "test"
// if (fopen(task".inp", "r")){
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
// }
// int n, q; cin >> n >> q;
// vector<int32_t> w(n), a(n), b(n), e(q);
// for (int32_t &x : w) cin >> x;
// for (int32_t &x : a) cin >> x;
// for (int32_t &x : b) cin >> x;
// for (int32_t &x : e) cin >> x;
// vector<int> ans = calculate_costs(w, a, b, e);
// for (int x : ans)
// cout << x << " ";
// }
Compilation message
nile.cpp: In function 'void init(std::vector<int>&, std::vector<std::pair<long long int, long long int> >&)':
nile.cpp:9:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = 0; i < b.size(); ++i)
| ~~^~~~~~~~~~
nile.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
nile.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int m = l + r >> 1;
| ~~^~~
nile.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
nile.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = l + r >> 1;
| ~~^~~
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:80:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while (j < events.size() && events[j][0] <= x){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
8528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2021 ms |
20284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
20284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
8528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
8528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
20284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8272 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
8528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
