Submission #590206

#TimeUsernameProblemLanguageResultExecution timeMemory
590206franfillWeirdtree (RMI21_weirdtree)C++17
13 / 100
2081 ms45932 KiB
#include "weirdtree.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; struct segtree { struct node { ll max1=-(1<<30), max2=-(1<<30); ll max1_cnt = 0; ll sum=0; ll tag = 1<<30; node(){}; node(ll v) { sum = v; max1_cnt = 1; max1 = v; max2 = -(1<<30); } void print() { //cout<<"max1: "<<max1<<" max2: "<<max2<<" sum: "<<sum<<" max1_cnt: "<<max1_cnt<<" tag:"<<tag<<endl; } }; vector < node > t; ll n; segtree(vector < ll > &v) { for (n = 1; n < v.size(); n *= 2); t.resize(2*n); for (ll i = 0; i < v.size(); i++) t[i+n] = node(v[i]); for (ll k = n-1; k; k--) { merge(t[k], t[k*2], t[k*2+1]); } } void merge(node &c, node a, node b) { if (a.max1 < b.max1) swap(a, b); c.sum = a.sum + b.sum; c.max1 = a.max1; c.max1_cnt = a.max1_cnt; if (b.max1 != a.max1) c.max2 = max(b.max1, a.max2); else c.max2 = max(a.max2, b.max2), c.max1_cnt += b.max1_cnt; } void propagate(ll k) { if (t[k].tag < t[k].max1) { t[k].sum -= (t[k].max1-t[k].tag)*t[k].max1_cnt; t[k].max1 = t[k].tag; if (k < n) { t[k*2].tag = min(t[k*2].tag, t[k].tag); t[k*2+1].tag = min(t[k*2+1].tag, t[k].tag); } } t[k].tag = 1<<30; } void set(ll i, ll val, ll k=1, ll x=0, ll y=-1) { if (y == -1) y = n; propagate(k); if (x == i && y == x + 1) { t[k] = node(val); return; } if (y <= i || x > i) return; ll m = (x+y)/2; set(i, val, k*2, x, m); set(i, val, k*2+1, m, y); merge(t[k], t[k*2], t[k*2+1]); } ll set_min(ll l, ll r, ll v, bool apply, ll count, ll k=1, ll x=0, ll y=-1) { if (y == -1) y = n; //cout << k << ": "; //t[k].print(); propagate(k); if (v >= t[k].max1) return 0; if (y <= l || r <= x) return 0; if (l <= x && y <= r && t[k].max2 < v) { ll red = (t[k].max1-v)*t[k].max1_cnt; if (red <= count || !apply) { if (apply) { t[k].tag = min(t[k].tag, v); propagate(k); } return min(red, count); } } if (k < n) { ll m = (x+y)/2; ll val1 = set_min(l, r, v, apply, count, k*2, x, m); count -= val1; ll val2 = set_min(l, r, v, apply, count, k*2+1, m, y); count -= val2; merge(t[k], t[k*2], t[k*2+1]); return val1 + val2; } return 0; } ll get(ll l, ll r, ll k=1, ll x=0, ll y=-1) { if (y == -1) y = n; propagate(k); if (l <= x && y <= r) return t[k].sum; if (r <= x || y <= l) return 0; ll m = (x+y)/2; return get(l, r, k*2, x, m) + get(l, r, k*2+1, m, y); } }; segtree *seg; void print() { for (ll i = 0; i < seg->n; i++) { //cout << seg->get(i, i+1) << ", "; } cout << "\n"; } void initialise(int N, int Q, int h_[]) { vector < ll > h(N); for (ll i = 0; i < N; i++) h[i] = h_[i+1]; seg = new segtree(h); } void cut(int l, int r, int k) { l--; ll x = 0, y = seg->t[1].max1+1; while(x < y-1) { ll m = (x+y)/2; if (seg->set_min(l, r, m, false, k) < k) { y = m; } else { x = m; } } //cout << "riduco fino a :" << y << "!\n"; //print(); k -= seg->set_min(l, r, y, true, k); //print(); //cout << "poto altri :" << k << "!\n"; seg->set_min(l, r, x, true, k); //print(); } void magic(int i, int x) { seg->set(i-1, x); } long long int inspect(int l, int r) { return seg->get(l-1, r); }

Compilation message (stderr)

weirdtree.cpp: In constructor 'segtree::segtree(std::vector<long long int>&)':
weirdtree.cpp:33:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for (n = 1; n < v.size(); n *= 2);
      |               ~~^~~~~~~~~~
weirdtree.cpp:35:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (ll i = 0; i < v.size(); i++) t[i+n] = node(v[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...