oj.uz

답안 #1068315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068315 2024-08-21T09:14:07 Z 정민찬(#11128) Weirdtree (RMI21_weirdtree) C++17
42 / 100
 2000 ms 416896 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,greater<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) {
		if (lazy[node] == inf) return {};
		vector<pll> ret;
		while (!tree[node].empty()) {
			if (tree[node].begin()->first <= lazy[node]) break;
			ret.push_back(*tree[node].begin());
			sum[node] -= (tree[node].begin()->first - lazy[node]) * tree[node].begin()->second;
			tree[node][lazy[node]] += tree[node].begin()->second;
			tree[node].erase(tree[node].begin());
		}
		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 {tree[node].begin()->first, tree[node].begin()->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 (tree[node].begin()->first != k) return tree[node].begin()->first;
			if (tree[node].size() == 1) return 0;
			return next(tree[node].begin())->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() || tree[node].begin()->first < mx) return {-1, 0};
		if (tree[node].begin()->first == mx && tree[node].begin()->second < k) return {-1, tree[node].begin()->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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1112 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1112 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 1039 ms 100268 KB Output is correct
4 Correct 1068 ms 98388 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1112 KB Output is correct
2 Correct 14 ms 1116 KB Output is correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1112 KB Output is correct
2 Correct 14 ms 1116 KB Output is correct
3 Execution timed out 2036 ms 416896 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2067 ms 402516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1112 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 1039 ms 100268 KB Output is correct
4 Correct 1068 ms 98388 KB Output is correct
5 Correct 12 ms 1112 KB Output is correct
6 Correct 14 ms 1116 KB Output is correct
7 Correct 1048 ms 100904 KB Output is correct
8 Correct 1018 ms 98388 KB Output is correct
9 Correct 1028 ms 97964 KB Output is correct
10 Correct 1183 ms 103636 KB Output is correct
11 Correct 1071 ms 105560 KB Output is correct
12 Correct 53 ms 28432 KB Output is correct
13 Correct 148 ms 30556 KB Output is correct

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1112 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 1039 ms 100268 KB Output is correct
4 Correct 1068 ms 98388 KB Output is correct
5 Correct 12 ms 1112 KB Output is correct
6 Correct 14 ms 1116 KB Output is correct
7 Execution timed out 2036 ms 416896 KB Time limit exceeded
8 Halted 0 ms 0 KB -