Submission #1102381

#TimeUsernameProblemLanguageResultExecution timeMemory
1102381ioaneNile (IOI24_nile)C++17
0 / 100
37 ms6852 KiB
#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 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...