Submission #1100075

#TimeUsernameProblemLanguageResultExecution timeMemory
1100075fve5Nile (IOI24_nile)C++17
38 / 100
88 ms20424 KiB
#include "nile.h" #include <bits/stdc++.h> using namespace std; #define int i64 typedef long long i64; struct CC { static vector<int> A, B; static vector<i64> S; int par, size, l, r, best; void skip(int i) { best = min(best, A[i] - B[i]); } int get_best() const { return min({best, A[l] - B[l], A[r] - B[r]}); } i64 get_cost() const { return S[r + 1] - S[l] + (size & 1) * get_best(); } }; vector<int> CC::A = {}; vector<int> CC::B = {}; vector<i64> CC::S = {}; struct DSU { vector<CC> arr; i64 cost; int find(int u) { if (arr[u].par == u) return u; return arr[u].par = find(arr[u].par); } void join(int i) { int u = find(i); int v = find(i + 1); if (u == v) return; if (arr[u].size < arr[v].size) swap(u, v); cost -= arr[u].get_cost(); cost -= arr[v].get_cost(); arr[u].size += arr[v].size; arr[u].r = max(arr[u].r, arr[v].r); arr[u].l = min(arr[u].l, arr[v].l); arr[u].best = max(arr[u].best, arr[v].best); arr[v].par = u; cost += arr[u].get_cost(); } void skip(int i) { int u = find(i); cost -= arr[u].get_cost(); arr[u].skip(i); cost += arr[u].get_cost(); } DSU(int N) : arr(N), cost(0) { for (int i = 0; i < N; i++) { arr[i] = {i, 1, i, i, (int)2e9}; cost += arr[i].get_cost(); } } }; enum EventType { JOIN, SKIP, QUERY }; struct Event { EventType type; int time, position; }; bool operator<(const Event &a, const Event &b) { return tie(a.time, a.type) < tie(b.time, b.type); } vector<long long> calculate_costs(vector<signed> W, vector<signed> A, vector<signed> B, vector<signed> E) { vector<int> order(W.size()); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int u, int v) { return W[u] < W[v]; }); sort(W.begin(), W.end()); CC::A.resize(W.size()); CC::B.resize(W.size()); CC::S.resize(W.size() + 1); for (int i = 0; i < W.size(); i++) { CC::A[i] = A[order[i]]; CC::B[i] = B[order[i]]; CC::S[i + 1] = CC::S[i] + B[order[i]]; } vector<Event> events; for (int i = 0; i < E.size(); i++) events.push_back({QUERY, E[i], i}); for (int i = 0; i < W.size() - 1; i++) events.push_back({JOIN, W[i + 1] - W[i], i}); for (int i = 1; i < W.size() - 1; i++) events.push_back({SKIP, W[i + 1] - W[i - 1], i}); DSU dsu(W.size()); vector<i64> ans(E.size()); sort(events.begin(), events.end()); for (auto [type, _, idx]: events) { switch (type) { case JOIN: dsu.join(idx); break; case SKIP: dsu.skip(idx); break; case QUERY: ans[idx] = dsu.cost; break; } } return ans; }

Compilation message (stderr)

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:86:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~
nile.cpp:93:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < E.size(); i++)
      |                     ~~^~~~~~~~~~
nile.cpp:95:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < W.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
nile.cpp:97:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 1; i < W.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
#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...