Submission #786765

#	Time	Username	Problem	Language	Result	Execution time	Memory
786765		qwerasdfzxcl	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	566 ms	29608 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;

int n;

struct Node{
	int mx, smx, cnt;
	Node(){}
	Node(int x):mx(x), smx(0), cnt(1) {}
	Node(int _mx, int _smx, int _cnt): mx(_mx), smx(_smx), cnt(_cnt){}

	Node operator + (const Node &N) const{
		Node ret;
		if (mx > N.mx) ret.mx = mx, ret.smx = max(N.mx, smx), ret.cnt = cnt;
		else if (mx < N.mx) ret.mx = N.mx, ret.smx = max(mx, N.smx), ret.cnt = N.cnt;
		else ret.mx = mx, ret.smx = max(smx, N.smx), ret.cnt = cnt + N.cnt;

		return ret;
	}
};

struct Seg{
	Node tree[1201200];
	ll tree2[1201200];

	int lazy[1201200];

	void init(int i, int l, int r, int a[]){
		lazy[i] = INF;
		if (l==r){
			tree[i] = Node(a[l]);
			tree2[i] = a[l];
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
		tree[i] = tree[i<<1] + tree[i<<1|1];
		tree2[i] = tree2[i<<1] + tree2[i<<1|1];
	}

	void propagate(int i, int l, int r){
		if (lazy[i]==INF) return;
		
		int d = tree[i].mx - min(tree[i].mx, lazy[i]);
		tree2[i] -= (ll)d * tree[i].cnt;
		tree[i].mx = min(tree[i].mx, lazy[i]);

		assert(tree[i].mx > tree[i].smx || tree[i].mx==0);

		if (l!=r){
			lazy[i<<1] = min(lazy[i<<1], lazy[i]);
			lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
		}

		lazy[i] = INF;
	}

	void updateM(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e && (x > tree[i].smx || (x==0 && tree[i].smx==0))){
			lazy[i] = x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		updateM(i<<1, l, m, s, e, x); updateM(i<<1|1, m+1, r, s, e, x);
		tree[i] = tree[i<<1] + tree[i<<1|1];
		tree2[i] = tree2[i<<1] + tree2[i<<1|1];
	}

	void updateV(int i, int l, int r, int p, int x){
		propagate(i, l, r);
		if (r<p || p<l) return;
		if (l==r){
			tree[i] = Node(x);
			tree2[i] = x;
			return;
		}

		int m = (l+r)>>1;
		updateV(i<<1, l, m, p, x); updateV(i<<1|1, m+1, r, p, x);
		tree[i] = tree[i<<1] + tree[i<<1|1];
		tree2[i] = tree2[i<<1] + tree2[i<<1|1];
	}

	int prefix(int i, int l, int r, int s, int val, int cnt){
		// printf(" call %d %d %d %d %d %d\n", i, l, r, s, val, cnt);
		propagate(i, l, r);
		if (r<s) return 0;
		if (s<=l){
			if (tree[i].mx < val) return 0;
			if (tree[i].mx==val && tree[i].cnt < cnt) return -tree[i].cnt;
			if (l==r){
				if (tree[i].mx == val) return l;
				else return 0;
			} 
		}
		
		int m = (l+r)>>1;
		int ret1 = prefix(i<<1, l, m, s, val, cnt);
		if (ret1 > 0) return ret1;

		cnt += ret1;
		int ret2 = prefix(i<<1|1, m+1, r, s, val, cnt);
		if (ret2 > 0) return ret2;
		return ret1 + ret2;
	}

	Node query(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return Node(0, 0, 0);
		if (s<=l && r<=e) return tree[i];

		int m = (l+r)>>1;
		return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
	}

	ll sum(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return 0;
		if (s<=l && r<=e) return tree2[i];

		int m = (l+r)>>1;
		return sum(i<<1, l, m, s, e) + sum(i<<1|1, m+1, r, s, e);
	}
}tree;

void initialise(int N, int Q, int h[]) {
	n = N;
	tree.init(1, 1, n, h);
}

void cut(int l, int r, int k) {
	while(k > 0){
		auto N = tree.query(1, 1, n, l, r);
		// printf("ok %d %d cnt = %d / k = %d\n", N.mx, N.smx, N.cnt, k);
		if (k >= (ll)N.cnt * (N.mx - N.smx)){
			k -= (ll)N.cnt * (N.mx - N.smx);
			tree.updateM(1, 1, n, l, r, N.smx);

			if (N.smx==0) return;
		}

		else{
			int quo = k / N.cnt, rem = k % N.cnt;
			int idx = l-1;
			if (rem > 0) idx = tree.prefix(1, 1, n, l, N.mx, rem);

			// printf(" okok idx = %d\n", idx);
			
			if (l<=idx) tree.updateM(1, 1, n, l, idx, N.mx-quo-1);
			if (idx+1<=r) tree.updateM(1, 1, n, idx+1, r, N.mx-quo);
			return;
		}
	}
}

void magic(int i, int x) {
	tree.updateV(1, 1, n, i, x);
}

long long int inspect(int l, int r) {
	return tree.sum(1, 1, n, l, r);
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29