Submission #390108

#TimeUsernameProblemLanguageResultExecution timeMemory
390108rk42745417Permutation Recovery (info1cup17_permutation)C++17
25 / 100
203 ms313428 KiB
/* -------------- | / | | / | | / | * |/ | | ------ * | | | | / \ | | |\ | | | |\ | \ | | | \ | | | | \ | \ | | | \ | | \ / \ | V | | \ \__/| ----- \ | */ #include <bits/stdc++.h> using namespace std; #define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL); using ll = int64_t; using ull = uint64_t; using ld = long double; using uint = uint32_t; const double EPS = 1e-8; const int INF = 0x3F3F3F3F; const ll LINF = 4611686018427387903; const int MOD = 1e9+7; /*--------------------------------------------------------------------------------------*/ const int N = 1e7; mt19937 rnd(time(0)); struct Treap { struct node { int l, r, sz, pri; ll val, sum; node(): l(0), r(0), sz(0), val(0), sum(0), pri(0) { } node(ll x): l(0), r(0), sz(1), val(x), sum(x), pri(rnd()) { } } arr[N]; int t; inline int new_node(ll v) { arr[++t] = node(v); return t; } inline void pull(int p) { arr[p].sz = sz(arr[p].l) + 1 + sz(arr[p].r); arr[p].sum = arr[arr[p].l].sum + arr[p].val + arr[arr[p].r].sum; } inline int sz(int p) { return arr[p].sz; } void split(int &a, int &b, int id, ll v) { if(!id) return a = b = 0, void(); if(arr[arr[id].l].sum + arr[id].val <= v) { a = id; split(arr[a].r, b, arr[id].r, v - (arr[arr[id].l].sum + arr[id].val)); pull(a); } else { b = id; split(a, arr[b].l, arr[id].l, v); pull(b); } } int merge(int a, int b) { if(!a || !b) return a ? a : b; if(arr[a].pri > arr[b].pri) { arr[a].r = merge(arr[a].r, b); pull(a); return a; } else { arr[b].l = merge(a, arr[b].l); pull(b); return b; } } void travesal(int id, vector<int> &ans, int g) { if(!id) return; travesal(arr[id].l, ans, g); g += sz(arr[id].l) + 1; //cout << "here " << ans[id] = g; travesal(arr[id].r, ans, g); } } treap; signed main() { EmiliaMyWife int n, rt = 0; cin >> n; vector<ll> arr(n); for(auto &a : arr) cin >> a; vector<int> ans(n + 1); for(int i = 0; i < n; i++) { int a, b; ll x = arr[i]; if(i) x -= arr[i - 1]; treap.split(a, b, rt, x - 1); rt = treap.merge(a, treap.new_node(x)); rt = treap.merge(rt, b); } treap.travesal(rt, ans, 0); for(int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n]; }

Compilation message (stderr)

permutation.cpp: In constructor 'Treap::node::node()':
permutation.cpp:31:11: warning: 'Treap::node::sum' will be initialized after [-Wreorder]
   31 |   ll val, sum;
      |           ^~~
permutation.cpp:30:17: warning:   'int Treap::node::pri' [-Wreorder]
   30 |   int l, r, sz, pri;
      |                 ^~~
permutation.cpp:32:3: warning:   when initialized here [-Wreorder]
   32 |   node(): l(0), r(0), sz(0), val(0), sum(0), pri(0) { }
      |   ^~~~
permutation.cpp: In constructor 'Treap::node::node(ll)':
permutation.cpp:31:11: warning: 'Treap::node::sum' will be initialized after [-Wreorder]
   31 |   ll val, sum;
      |           ^~~
permutation.cpp:30:17: warning:   'int Treap::node::pri' [-Wreorder]
   30 |   int l, r, sz, pri;
      |                 ^~~
permutation.cpp:33:3: warning:   when initialized here [-Wreorder]
   33 |   node(ll x): l(0), r(0), sz(1), val(x), sum(x), pri(rnd()) { }
      |   ^~~~
#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...