Submission #1145861

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

unsigned xor128() {
	static unsigned x = 123456789, y = 362436069, z = random_device{}(), w = random_device{}();
	unsigned t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

struct Node {
	static Node nullNode;
	static int K;

	unsigned priority;
	Node *left, *right;
	int size;
	int pos;
	int consume;
	long long produce;
	long long sumBase;
	long long sumMaxAdd;

	bool isNull() const { return priority == 0; }

	Node *set(int D, int A) {
		*this = nullNode;
		do priority = xor128(); while (priority == 0);
		pos = D;
		consume = A;
		return update();
	}

	inline Node *update() {
		assert(!isNull());
		size = left->size + 1 + right->size;
		produce = left->produce;
		sumBase = left->sumBase;
		sumMaxAdd = left->sumMaxAdd;
		if (!left->isNull()) {
			produce += (ll)(pos - left->pos) * K;
		}
		{
			ll t = min((ll)consume, produce);
			produce -= t;
			sumBase += t;
			sumMaxAdd += consume - t;
		}
		if (!right->isNull()) {
			produce += (ll)(right->pos - pos) * K;
		}
		{
			ll t = min((ll)right->sumMaxAdd, produce);
			produce -= t;
			sumBase += t;
			sumMaxAdd += right->sumMaxAdd - t;
		}
		sumBase += right->sumBase;
		produce += right->produce;
		return this;
	}
	inline void propagate() {
	}
	inline Node *linkl(Node *c) {
		left = c;
		return update();
	}
	inline Node *linkr(Node *c) {
		right = c;
		return update();
	}
	inline Node *linklr(Node *l, Node *r) {
		left = l, right = r;
		return update();
	}
	inline Node *linkl2(Node *c) {
		if (priority >= c->priority)
			return linkl(c);
		else
			return c->linkr(linkl(c->right));
	}
	inline Node *linkr2(Node *c) {
		if (priority >= c->priority)
			return linkr(c);
		else
			return c->linkl(linkr(c->left));
	}
};
int Node::K;
Node Node::nullNode = {
	0,
	&nullNode, &nullNode,
	0, -1, 0,
	0, 0, 0
};

struct RBST {
	typedef Node *Ref;
	static Ref join(Ref l, Ref r) {
		if (l->isNull()) return r;
		if (r->isNull()) return l;
		if (l->priority >= r->priority) {
			l->propagate();
			return l->linkr(join(l->right, r));
		}
		else {
			r->propagate();
			return r->linkl(join(l, r->left));
		}
	}
	typedef pair<Ref, Ref> RefPair;
	static RefPair splitPos(Ref t, int pos) {
		if (t->isNull()) return RefPair(&Node::nullNode, &Node::nullNode);
		t->propagate();
		if (pos <= t->pos) {
			RefPair p = splitPos(t->left, pos);
			return RefPair(p.first, t->linkl(p.second));
		}
		else {
			RefPair p = splitPos(t->right, pos);
			return RefPair(t->linkr(p.first), p.second);
		}
	}
	static Ref insertPos(Ref t, Ref n) {
		if (t->isNull()) return n;
		t->propagate();
		if (n->pos <= t->pos)
			return t->linkl2(insertPos(t->left, n));
		else
			return t->linkr2(insertPos(t->right, n));
	}
	static void decompose(Ref t, vector<Ref> &res) {
		if (t->isNull()) return;
		t->propagate();
		Ref l = t->left, r = t->right;
		t->left = t->right = &Node::nullNode;
		decompose(l, res);
		res.push_back(t);
		decompose(r, res);
	}
};


int main() {
	int Q; int K;
	while (~scanf("%d%d", &Q, &K)) {
		Node::K = K;
		vector<Node> nodes(Q + 1);
		Node *t = &nodes[Q];
		t->set(0, 0);
		for (int qi = 0; qi < Q; ++qi) {
			int ty;
			scanf("%d", &ty);
			if (ty == 1) {
				int D; int A;
				scanf("%d%d", &D, &A);
				Node *node = &nodes[qi];
				node->set(D, A);
				t = RBST::insertPos(t, node);
			}
			else if (ty == 2) {
				int D;
				scanf("%d", &D);
				auto p = RBST::splitPos(t, D + 1);
				ll ans = p.first->sumBase;
				t = RBST::join(p.first, p.second);
				printf("%lld\n", ans);
			}
			else abort();
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:160:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ty);
                    ^
./Main.cpp:163:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &D, &A);
                          ^
./Main.cpp:170:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &D);
                    ^

Judge Result