Submission #1198162

#TimeUsernameProblemLanguageResultExecution timeMemory
1198162TymondWeirdtree (RMI21_weirdtree)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "weirdtree.h" using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; struct pair_hash{ size_t operator()(const pair<int,int>&x)const{ return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32)); } }; struct Node{ ll mx1, mx2, f1, sum; Node(){ mx1 = mx2 = f1 = sum = 0LL; } Node(ll a){ mx1 = sum = a; f1 = 1LL; mx2 = 0LL; } Node(ll a, ll b, ll c, ll d){ mx1 = a; mx2 = b; f1 = c; sum = d; } Node operator+(const Node& other) const{ if(mx1 == other.mx1){ return Node(mx1, max(mx2, other.mx2), f1 + other.f1, sum + other.sum); }else if(mx1 > other.mx1){ return Node(mx1, max(mx2, other.mx1), f1, sum + other.sum); }else{ return Node(other.mx1, max(mx1, other.mx2), other.f1, sum + other.sum); } } }; const int BASE = (1 << 19); Node tree[2 * BASE + 7]; ll H[BASE]; int n, q; void upd(int i, ll x){ i += BASE; tree[i] = Node(x); i /= 2; while(i > 0){ tree[i] = tree[2 * i] + tree[2 * i + 1]; i /= 2; } } ll query(int v, int l, int p, int a, int b){ if(p < a || b < l){ return 0LL; } if(a <= l && p <= b){ return tree[v].sum; } int mid = (l + p) / 2; ll ret = (ll)query(2 * v, l, mid, a, b) + query(2 * v + 1, mid + 1, p, a, b); tree[v] = tree[2 * v] + tree[2 * v + 1]; return ret; } void initialise(int N, int Q, int h[]) { n = N; q = Q; for(int i = 1; i <= n; i++){ H[i] = h[i]; tree[i + BASE] = Node(H[i]); } for(int i = BASE; i >= 1; i--){ tree[i] = tree[2 * i] + tree[2 * i + 1]; } } Node join(int v, int l, int p, int a, int b){ if(p < a || b < l){ return Node(); } if(a <= l && p <= b){ return tree[v]; } int mid = (l + p) / 2; return join(2 * v, l, mid, a, b) + join(2 * v + 1, mid + 1, p, a, b); } ll v1,c1, v2, c2,mx1,mx2; void changeAll(int v, int l, int p, int a, int b){ if(p < a || b < l){ return; } if(a <= l && p <= b){ if(tree[v].mx1 < mx1){ return; } if(l == p){ tree[v].mx1 = mx2; tree[v].sum -= (tree[v].f1 * (mx1 - mx2)); return; } } int mid = (l + p) / 2; changeAll(2 * v, l, mid ,a, b, mx1, mx2); changeAll(2 * v + 1, mid + 1, p, a, b, mx1, mx2); tree[v] = tree[2 * v] + tree[2 * v + 1]; } pii used = mp(0, 0); void change(int v, int l, int p, int a, int b){ if(p < a || b < l){ return; } if(a <= l && p <= b){ if(tree[v].mx1 < mx1){ return; } if(l == p){ if(used.fi < c1){ tree[v].mx1 = v1; used.fi++; tree[v].sum -= (tree[v].f1 * (mx1 - v1)); return; }else{ tree[v].mx1 = v2; used.se++; tree[v].sum -= (tree[v].f1 * (mx1 - v2)); return; } } } int mid = (l + p) / 2; change(2 * v, l, mid, a, b, v1, c1, v2,c2, mx1); change(2 * v + 1, mid + 1, p, a, b, v1, c1, v2,c2, mx1); tree[v] = tree[2 * v] + tree[2 * v + 1]; } void cut(int l, int r, int k) { //cout << "-----\n"; Node curr; while(k){ curr = join(1, 0, BASE - 1, l, r); /*for(int i = 1; i <= 6; i++){ cout << tree[i + BASE].mx1 << ' '; } cout << '\n'; cout << curr.mx1 << ' ' << curr.mx2 << ' ' << curr.f1 << '\n'; cout << (ll)(curr.mx1 - curr.mx2) * curr.f1 << ' ' << k << '\n';*/ mx1 = curr.mx1; mx2 = curr.mx2; if((ll)(curr.mx1 - curr.mx2) * curr.f1 > k){ v1 = mx1 - (k + curr.f1 - 1) / curr.f1; v2 = mx1 - k / curr.f1; c1 = k - curr.f1 * v2; c2 = curr.f1 - c1; used = mp(0, 0); change(1, 0, BASE - 1, l, r); k = 0; }else{ k = (ll)k - (ll)(curr.mx1 - curr.mx2) * curr.f1; changeAll(1, 0, BASE - 1, l, r); if(curr.mx2 == 0){ k = 0; } } } } void magic(int i, int x){ H[i] = x; upd(i, x); } ll inspect(int l, int r) { return query(1, 0, BASE - 1, l, r); } /*int main(){ int h[7] = {0, 1, 2, 3, 1, 2, 3}; initialise(6, 10, h); cut(1, 6, 3); //for(int i = 1; i <= 6; i++){ // cout << tree[i + BASE].mx1 << ' '; //} //cout << '\n'; cout << inspect(1, 6) << '\n'; cut(1, 3, 3); cout << inspect(1, 6) << '\n'; cut(1, 3, 1000); cout << inspect(1, 6) << '\n'; magic(1, 1000); cout << inspect(1, 6) << '\n'; cut(1, 3, 999); cout << inspect(1, 5) << '\n'; return 0; } */

Compilation message (stderr)

weirdtree.cpp: In function 'void changeAll(int, int, int, int, int)':
weirdtree.cpp:150:14: error: too many arguments to function 'void changeAll(int, int, int, int, int)'
  150 |     changeAll(2 * v, l, mid ,a, b, mx1, mx2);
      |     ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
weirdtree.cpp:133:6: note: declared here
  133 | void changeAll(int v, int l, int p, int a, int b){
      |      ^~~~~~~~~
weirdtree.cpp:151:14: error: too many arguments to function 'void changeAll(int, int, int, int, int)'
  151 |     changeAll(2 * v + 1, mid + 1, p, a, b, mx1, mx2);
      |     ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
weirdtree.cpp:133:6: note: declared here
  133 | void changeAll(int v, int l, int p, int a, int b){
      |      ^~~~~~~~~
weirdtree.cpp: In function 'void change(int, int, int, int, int)':
weirdtree.cpp:182:11: error: too many arguments to function 'void change(int, int, int, int, int)'
  182 |     change(2 * v, l, mid, a, b, v1, c1, v2,c2, mx1);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
weirdtree.cpp:156:6: note: declared here
  156 | void change(int v, int l, int p, int a, int b){
      |      ^~~~~~
weirdtree.cpp:183:11: error: too many arguments to function 'void change(int, int, int, int, int)'
  183 |     change(2 * v + 1, mid + 1, p, a, b, v1, c1, v2,c2, mx1);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
weirdtree.cpp:156:6: note: declared here
  156 | void change(int v, int l, int p, int a, int b){
      |      ^~~~~~