Submission #1112768

#TimeUsernameProblemLanguageResultExecution timeMemory
1112768FIFI_cppNile (IOI24_nile)C++17
23 / 100
114 ms35608 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <cstdlib> #include <cmath> #include <queue> #include <stack> #include <deque> #include <fstream> #include <iterator> #include <set> #include <map> #include <unordered_map> #include <iomanip> #include <cctype> #include <string> #include <cassert> #include <set> #include <bitset> #include <unordered_set> #include <numeric> #define all(a) a.begin(), a.end() #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define pb push_back #define ppi pair<int,pair<int,int>> //#define int long long #define ll long long using namespace std; // /\_/\ // (= ._.) // / > \> // encouraging cat const int INF = 10000000000000000; const int mod = 1000000007; //const int mod = 998244353; const int MAXN = 200005; //ifstream fin('xor.in'); //ofstream fout('xor.out'); ll curr_res = 0; struct Index { ll a,b,w; }; struct Node { ll parent, min_value, min_index, size, sb, l, r; }; vector<Index> vals; vector<Node> info; vector<pair<ll,ll>> e; bool cmp(const Index &x, const Index &y) { return x.w < y.w; } ll find_parent(ll x) { if (x == info[x].parent) { return x; } return info[x].parent = find_parent(info[x].parent); } void remove(Node x, int ix) { if (x.size == 1) { curr_res -= vals[ix].a; } else if (x.size % 2 == 0) { curr_res -= x.sb; } else { curr_res -= x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b)); } } void add(Node x) { if (x.size % 2 == 0) { curr_res += x.sb; } else { curr_res += x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b)); } } pair<Node, Node> merge(Node x,Node y, ll ix, ll iy) { y.parent = ix; x.size += y.size; if (y.min_value < x.min_value) { x.min_value = y.min_value; x.min_index = y.min_index; } x.sb += y.sb; x.l = min(x.l, y.l); x.r = max(x.r,y.r); return {x,y}; } void onion (ll x, ll y) { x = find_parent(x); y = find_parent(y); if (x == y) return; remove(info[x], x); remove(info[y], y); if (info[y].size > info[x].size) { swap(x,y); } pair<Node, Node> m = merge(info[x], info[y], x, y); info[x] = m.first; info[y] = m.second; add(info[x]); } Node set_best(Node x, int index) { if (x.size % 2) curr_res -= x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b)); if (vals[index].a - vals[index].b < x.min_value) { x.min_value = vals[index].a - vals[index].b; x.min_index = index; } if (x.size % 2) curr_res += x.sb + min(x.min_value, min(vals[x.l].a - vals[x.l].b, vals[x.r].a - vals[x.r].b)); return x; } std::vector<ll> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { ll n = A.size(); info.resize(n); vals.resize(n); for (ll i = 0;i < n;i++) { vals[i].a = A[i]; vals[i].b = B[i]; vals[i].w = W[i]; } sort(all(vals), cmp); for (ll i = 0;i < n;i++) { info[i].l = i; info[i].r = i; info[i].parent = i; info[i].min_index = i; info[i].min_value = INF; info[i].sb = vals[i].b; info[i].size = 1; curr_res += vals[i].a; } ll q = E.size(); e.resize(q); for (ll i = 0;i < q;i++) { e[i].first = E[i]; e[i].second = i; } sort(all(e)); vector<pair<ll,ll>> diff; for (ll i = 0;i < n - 1;i++) { diff.push_back({vals[i + 1].w - (ll)vals[i].w, -i - 1}); if (i < n - 2) { diff.pb({vals[i + 2].w - (ll)vals[i].w, i + 1}); } } sort(all(diff)); vector<ll> res(q); ll e_index = 0; info[0].min_value = vals[0].a - vals[0].b; info[n - 1].min_value = vals[n - 1].a - vals[n - 1].b; for (ll i = 0;i < diff.size();i++) { if (diff[i].first <= e[e_index].first) { if (diff[i].second < 0) { int mergei = diff[i].second * -1 - 1; ll a = mergei; ll b = mergei + 1; onion(a,b); } else { diff[i].second--; int nd = find_parent(diff[i].second + 1); info[nd] = set_best(info[nd], diff[i].second + 1); } } else { res[e[e_index].second] = curr_res; e_index++; i--; } } for (; e_index < q;e_index++) { res[e[e_index].second] = curr_res; } return res; }

Compilation message (stderr)

nile.cpp:33:1: warning: multi-line comment [-Wcomment]
   33 | //    /\_/\
      | ^
nile.cpp:37:17: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   37 | const int INF = 10000000000000000;
      |                 ^~~~~~~~~~~~~~~~~
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:178:21: 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]
  178 |     for (ll i = 0;i < diff.size();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...