| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1102381 |
2024-10-18T03:35:29 Z |
ioane |
Nile (IOI24_nile) |
C++17 |
|
37 ms |
6852 KB |
#include <bits/stdc++.h>
#define LL long long
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define FF fflush(stdout)
#define d(C) C-'a'
const LL N = 100005;
const LL mod = 1000000007;
using namespace std;
int p[N], sz[N];
int get_p(int u){
if (p[u] == u) return u;
p[u] = get_p(p[u]);
return p[u];
}
int merge(int u, int v){
u = get_p(u);
v = get_p(v);
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return u;
}
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int n = W.size();
int q = E.size();
long long total_a = 0;
for (int i = 0; i < n; ++i){
p[i] = i;
sz[i] = 1;
}
vector<pair<int, int> > v, diff;
LL ans[n];
int mn[n];
for (int i = 0; i < n; ++i){
v.PB(MP(W[i], A[i] - B[i]));
total_a += A[i];
}
sort(v.begin(), v.end());
for (int i = 1; i < n; ++i){
diff.PB(MP(v[i].F - v[i-1].F, i));
mn[i] = v[i].S;
ans[i] = 0;
}
ans[0] = 0;
mn[0] = v[0].S;
sort(diff.begin(), diff.end());
int diff_i = 0;
vector<long long> result(q);
LL ans_profit = 0;
vector<pair<int, int> > queries;
for (int i = 0; i < q; ++i){
queries.PB(MP(E[i], i));
}
sort(queries.begin(), queries.end());
for (int i_E = 0; i_E < q; ++i_E){
int d = queries[i_E].F;
while (diff_i < n-1 && diff[diff_i].F <= d){
int ind = diff[diff_i].S;
int u = get_p(ind-1);
int v = get_p(ind);
int mxmn = max(mn[u], mn[v]);
ans_profit += (LL)mxmn;
int new_ans = ans[u] + ans[v] + (LL)mxmn;
int new_mn = min(mn[u], mn[v]);
int par = merge(u, v);
ans[par] = new_ans;
mn[par] = new_mn;
diff_i++;
}
LL answ = total_a - ans_profit;
result[queries[i_E].S] = answ;
}
return result;
}
// IIIIIIIII OOOOO A NN N EEEEEEEEEE
// I O O A A N N N E
// I O O A A N N N E
// I O O A A N N N E
// I O O AAAAAAAAA N N N EEEEEEEE
// I O O A A N N N E
// I O O A A N N N E
// I O O A A N N N E
// IIIIIIIII OOOOO A A N NN EEEEEEEEEE ___ KAPANADZE
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
6852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
6844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
6844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
