oj.uz

Submission #1068295

# Submission time Handle Problem Language Result Execution time Memory
1068295 2024-08-21T09:08:46 Z 정민찬(#11128) Weirdtree (RMI21_weirdtree) C++17
42 / 100
 2000 ms 417176 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

struct SegmentTree{
	vector<map<ll,ll>> tree;
	vector<ll> sum;
	vector<ll> lazy;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.resize(sz);
		lazy.assign(sz, inf);
		sum.assign(sz, 0);
	}
	vector<pll> propagate(ll node, ll s, ll e) {
		vector<pll> ret;
		while (!tree[node].empty()) {
			auto it = prev(tree[node].end());
			if (it->first <= lazy[node]) break;
			ret.push_back(*it);
			sum[node] -= (it->first - lazy[node]) * it->second;
			tree[node][lazy[node]] += it->second;
			tree[node].erase(it);
		}
		if (s != e) {
			lazy[node*2] = min(lazy[node], lazy[node*2]);
			lazy[node*2+1] = min(lazy[node], lazy[node*2+1]);
		}
		lazy[node] = inf;
		return ret;
	}
	void Push(ll node, ll s, ll e, ll tar, ll val) {
		propagate(node, s, e);
		if (s > tar || tar > e) return;
		tree[node][val] ++;
		sum[node] += val;
		if (s == e) return;
		ll mid = s + e >> 1;
		Push(node*2, s, mid, tar, val);
		Push(node*2+1, mid+1, e, tar, val);
	}
	void Ers(ll node, ll s, ll e, ll tar, ll val) {
		propagate(node, s, e);
		if (s > tar || tar > e) return;
		tree[node][val] --;
		if (tree[node][val] == 0) tree[node].erase(val);
		sum[node] -= val;
		if (s == e) return;
		ll mid = s + e >> 1;
		Ers(node*2, s, mid, tar, val);
		Ers(node*2+1, mid+1, e, tar, val);
	}
	vector<pll> update(ll node, ll s, ll e, ll l, ll r, ll v) {
		propagate(node, s, e);
		if (l > e || s > r) return {};
		if (l <= s && e <= r) {
			lazy[node] = v;
			return propagate(node, s, e);
		}
		ll mid = s + e >> 1;
		vector<pll> t1 = update(node*2, s, mid, l, r, v);
		vector<pll> t2 = update(node*2+1, mid+1, e, l, r, v);
		vector<pll> ret;
		ret.reserve(t1.size() + t2.size());
		for (auto &x : t1) ret.push_back(x);
		for (auto &x : t2) ret.push_back(x);
		for (auto &[h, cnt] : ret) {
			sum[node] -= (h - v) * cnt;
			tree[node][v] += cnt;
			tree[node][h] -= cnt;
			if (tree[node][h] == 0) tree[node].erase(h);
		}
		return ret;
	}
	pll getMax(ll node, ll s, ll e, ll l, ll r) {
		propagate(node, s, e);
		if (l > e || s > r) return {0, 0};
		if (l <= s && e <= r) {
			return {prev(tree[node].end())->first, prev(tree[node].end())->second};
		}
		ll mid = s + e >> 1;
		pll t1 = getMax(node*2, s, mid, l, r);
		pll t2 = getMax(node*2+1, mid+1, e, l, r);
		if (t1.first > t2.first) return t1;
		if (t1.first < t2.first) return t2;
		return {t1.first, t1.second + t2.second};
	}
	ll getSecond(ll node, ll s, ll e, ll l, ll r, ll k) {
		propagate(node, s, e);
		if (l > e || s > r) return 0;
		if (l <= s && e <= r) {
			if (prev(tree[node].end())->first != k) return prev(tree[node].end())->first;
			if (tree[node].size() == 1) return 0;
			return prev(prev(tree[node].end()))->first;
		}
		ll mid = s + e >> 1;
		return max(getSecond(node*2, s, mid, l, r, k), getSecond(node*2+1, mid+1, e, l, r, k));
	}
	ll getSum(ll node, ll s, ll e, ll l, ll r) {
		propagate(node, s, e);
		if (l > e || s > r) return 0;
		if (l <= s && e <= r) return sum[node];
		ll mid = s + e >> 1;
		return getSum(node*2, s, mid, l, r) + getSum(node*2+1, mid+1, e, l, r);
	}
	pll findLeft(ll node, ll s, ll e, ll l, ll r, ll mx, ll k) {
		propagate(node, s, e);
		if (l > e || s > r) return {-1, 0};
		if (tree[node].empty() || prev(tree[node].end())->first < mx) return {-1, 0};
		if (prev(tree[node].end())->first == mx && prev(tree[node].end())->second < k) return {-1, prev(tree[node].end())->second};
		if (s == e) return {s, 0};
		ll mid = s + e >> 1;
		pll t1 = findLeft(node*2, s, mid, l, r, mx, k);
		if (t1.first == -1) {
			pll t2 = findLeft(node*2+1, mid+1, e, l, r, mx, k - t1.second);
			return {t2.first, t1.second + t2.second};
		}
		return t1;
	}
};

SegmentTree seg;

ll n;

void initialise(int N, int Q, int h[]) {
	n = N;
	seg.init(N);
	for (ll i=1; i<=N; i++) {
		seg.Push(1, 1, N, i, h[i]);
	}
}

void cut(int l, int r, int _k) {
	ll k = _k;
	while (true) {
		pll ret = seg.getMax(1, 1, n, l, r);
		ll mx = ret.first, cnt = ret.second;
		ll sec = seg.getSecond(1, 1, n, l, r, mx);
		if (mx == 0) break;
		if ((mx - sec) * cnt <= k) {
			seg.update(1, 1, n, l, r, sec);
			k -= (mx - sec) * cnt;
			continue;
		}
		ll diff = k / cnt;
		seg.update(1, 1, n, l, r, mx - diff);
		k %= cnt;
		if (k == 0) break;
		ll idx = seg.findLeft(1, 1, n, l, r, mx - diff, k).first;
		//if (idx == -1) break;
		assert(idx != -1);
		seg.update(1, 1, n, l, idx, mx - diff - 1);
		break;
	}
}

void magic(int i, int x) {
	ll cur = seg.getSum(1, 1, n, i, i);
	seg.Ers(1, 1, n, i, cur);
	seg.Push(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
	return seg.getSum(1, 1, n, l, r);
}
/*
int main() {
    int N, Q;
    cin >> N >> Q;

    int h[N + 1];

    for (int i = 1; i <= N; ++i) cin >> h[i];

    initialise(N, Q, h);

    for (int i = 1; i <= Q; ++i) {
        int t;
        cin >> t;

        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            cut(l, r, k);
        } else if (t == 2) {
            int i, x;
            cin >> i >> x;
            magic(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }
    return 0;
}
*/

Compilation message

weirdtree.cpp: In member function 'void SegmentTree::init(ll)':
weirdtree.cpp:15:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   15 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
weirdtree.cpp: In member function 'void SegmentTree::Push(ll, ll, ll, ll, ll)':
weirdtree.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'void SegmentTree::Ers(ll, ll, ll, ll, ll)':
weirdtree.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'std::vector<std::pair<long long int, long long int> > SegmentTree::update(ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'pll SegmentTree::getMax(ll, ll, ll, ll, ll)':
weirdtree.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'll SegmentTree::getSecond(ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:101:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'll SegmentTree::getSum(ll, ll, ll, ll, ll)':
weirdtree.cpp:108:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |   ll mid = s + e >> 1;
      |            ~~^~~
weirdtree.cpp: In member function 'pll SegmentTree::findLeft(ll, ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:117:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |   ll mid = s + e >> 1;
      |            ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 995 ms 101204 KB Output is correct
4 Correct 1138 ms 99568 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1256 KB Output is correct
2 Correct 15 ms 1116 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1256 KB Output is correct
2 Correct 15 ms 1116 KB Output is correct
3 Execution timed out 2076 ms 417176 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 404828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 995 ms 101204 KB Output is correct
4 Correct 1138 ms 99568 KB Output is correct
5 Correct 12 ms 1256 KB Output is correct
6 Correct 15 ms 1116 KB Output is correct
7 Correct 1052 ms 101456 KB Output is correct
8 Correct 1230 ms 99032 KB Output is correct
9 Correct 1084 ms 98384 KB Output is correct
10 Correct 1275 ms 104488 KB Output is correct
11 Correct 1321 ms 106288 KB Output is correct
12 Correct 67 ms 29292 KB Output is correct
13 Correct 199 ms 30956 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 995 ms 101204 KB Output is correct
4 Correct 1138 ms 99568 KB Output is correct
5 Correct 12 ms 1256 KB Output is correct
6 Correct 15 ms 1116 KB Output is correct
7 Execution timed out 2076 ms 417176 KB Time limit exceeded
8 Halted 0 ms 0 KB -