Submission #848371

---

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; }

struct Node {
	static vector<Node> buf;
	static size_t bufp;
	typedef const Node *Ref;
	Ref left, right;
	long long size;
	int val;
	mutable long long dp_cnt;
	mutable int mark;
	static int last_mark;
	static int marked_num;
	Node() : left(NULL), right(NULL), size(1), val(0), dp_cnt(0), mark(-1) {}
	static Ref newNode(Ref left, Ref right, int val) {
		Node *p;
		size_t initbufp = bufp;
		while(1) {
			p = &buf[bufp ++];
			if(bufp == buf.size())
				bufp = 0;
			if(p->mark != last_mark) break;
			if(bufp == initbufp) {
				cerr << "out of memory" << endl;
				abort();
			}
		}
		p->left = left, p->right = right, p->val = val;
		p->size = (!left ? 0 : left->size) + 1 + (!right ? 0 : right->size);
		p->mark = last_mark;
		++ marked_num;
		return p;
	}
	inline Ref propagated() const {
		return this;
	}
	inline Ref linkl(Ref c) const {
		return newNode(c, right, val);
	}
	inline Ref linkr(Ref c) const {
		return newNode(left, c, val);
	}
	inline Ref linklr(Ref l, Ref r) const {
		return newNode(l, r, val);
	}
};
vector<Node> Node::buf;
size_t Node::bufp = 0;
int Node::last_mark = 0;
int Node::marked_num = 0;

struct BoundedBalanceBinarySearchTree {
	typedef Node::Ref Ref;
	typedef pair<Ref, Ref> RefPair;
	static const int delta = 3, ratio = 2;

	static long long size(Ref t) { return !t ? 0 : t->size; }

	static Ref join(Ref l, Ref r) {
		if(!l) return r;
		if(!r) return l;
		long long sizeL = l->size, sizeR = r->size;
		if(delta * sizeL < sizeR) {
			r = r->propagated();
			return balance(r, join(l, r->left), r->right);
		}
		if(delta * sizeR < sizeL) {
			l = l->propagated();
			return balance(l, l->left, join(l->right, r));
		}
		return glue(l, r);
	}
	static RefPair split(Ref t, long long k) {
		if(!t) return RefPair(Ref(), Ref());
		t = t->propagated();
		long long s = size(t->left);
		if(k <= s) {
			RefPair p = split(t->left, k);
			return RefPair(p.first, link(t, p.second, t->right));
		} else {
			RefPair p = split(t->right, k - s - 1);
			return RefPair(link(t, t->left, p.first), p.second);
		}
	}
	static Ref insert(Ref t, long long k, Ref n) {
		if(!t) return n->linklr(NULL, NULL);
		t = t->propagated();
		long long s = size(t->left);
		if(k <= s)
			return balance(t, insert(t->left, k, n), t->right);
		else
			return balance(t, t->left, insert(t->right, k - s - 1, n));
	}
	static RefPair remove(Ref t, long long k) {
		if(!t) return RefPair(Ref(), Ref());
		t = t->propagated();
		long long s = size(t->left);
		if(k < s) {
			RefPair p = remove(t->left, k);
			return RefPair(balance(t, p.first, t->right), p.second);
		} else if(k > s) {
			RefPair p = remove(t->right, k - s - 1);
			return RefPair(balance(t, t->left, p.first), p.second);
		} else {
			Ref a = glue(t->left, t->right);
			return RefPair(a, t->linklr(NULL, NULL));
		}
	}
private:
	//t->linklr(l, r)した後にrotateしてバランスを取る感じ。ただしlとrがある程度バランスしている必要がある
	//tはpropagateした後の状態である必要がある
	static Ref balance(Ref t, Ref l, Ref r) {
		long long sizeL = size(l), sizeR = size(r);
		if(sizeL + sizeR > 1) {
			if(sizeR > delta * sizeL) return rotateL(t, l, r);
			if(sizeL > delta * sizeR) return rotateR(t, l, r);
		}
		return t->linklr(l, r);
	}
	//t->linklr(l, r)した後にどうにかバランスさせる
	//tはpropagateした後の状態である必要がある
	static Ref link(Ref t, Ref l, Ref r) {
		if(!l) return insert(r, 0, t);
		if(!r) return insert(l, l->size, t);
		long long sizeL = size(l), sizeR = size(r);
		if(delta * sizeL < sizeR) {
			r = r->propagated();
			return balance(r, link(t, l, r->left), r->right);
		}
		if(delta * sizeR < sizeL) {
			l = l->propagated();
			return balance(l, l->left, link(t, l->right, r));
		}
		return t->linklr(l, r);
	}
	static Ref rotateL(Ref t, Ref l, Ref r) {
		r = r->propagated();
		Ref rl = r->left, rr = r->right;
		if(size(rl) < ratio * size(rr)) {
			return r->linkl(t->linklr(l, rl));
		} else {	//((l,t,rll),rl,(rlr,r,rr))
			rl = rl->propagated();
			return rl->linklr(t->linklr(l, rl->left), r->linklr(rl->right, rr));
		}
	}
	static Ref rotateR(Ref t, Ref l, Ref r) {
		l = l->propagated();
		Ref ll = l->left, lr = l->right;
		if(size(lr) < ratio * size(ll)) {
			return l->linkr(t->linklr(lr, r));
		} else {	//((ll,l,lrl),lr,(lrr,t,r))
			lr = lr->propagated();
			return lr->linklr(l->linklr(ll, lr->left), t->linklr(lr->right, r));
		}
	}
	static Ref glue(Ref l, Ref r) {
		if(!l) return r;
		if(!r) return l;
		if(l->size > r->size) {
			RefPair p = remove(l, l->size - 1);
			return balance(p.second, p.first, r);
		} else {
			RefPair p = remove(r, 0);
			return balance(p.second, l, p.first);
		}
	}
};
typedef BoundedBalanceBinarySearchTree WBT;

Node::Ref build(int L, int R) {
	if(L > R) {
		return nullptr;
	} else {
		int mid = (L + R) / 2;
		auto l = build(L, mid - 1);
		auto r = build(mid + 1, R);
		return Node::newNode(l, r, mid);
	}
}

Node::Ref cycleTake(Node::Ref t, long long k) {
	if(t->size * 2 <= k)
		return cycleTake(WBT::join(t, t), k);
	else if(t->size <= k)
		return WBT::join(t, cycleTake(t, k - t->size));
	else
		return WBT::split(t, k).first;
}

vector<Node::Ref> ord;
void dfs(Node::Ref x) {
	if(x->dp_cnt == 0) {
		x->dp_cnt = -1;
		if(x->left)
			dfs(x->left);
		if(x->right)
			dfs(x->right);
		ord.push_back(x);
	}
}

void do_mark(Node::Ref x) {
	x->mark = Node::last_mark;
	++ Node::marked_num;
	if(x->left && x->left->mark != Node::last_mark)
		do_mark(x->left);
	if(x->right && x->right->mark != Node::last_mark)
		do_mark(x->right);
}

int main() {
	mt19937 re;
	uniform_int_distribution<ll> dist(1, (ll)1e18);
	int N; int Q;
	while(~scanf("%d%d", &N, &Q)) {
		Node::buf.assign(200 * 1024 * 1024 / sizeof(Node), Node());
		Node::bufp = 0;
		Node::last_mark = 0;
		Node::marked_num = 0;
		Node::Ref p = build(1, N);
		rep(i, Q) {
			if(Node::marked_num >= Node::buf.size() / 2) {
				++ Node::last_mark;
				int prev_num = Node::marked_num;
				Node::marked_num = 0;
				do_mark(p);
				//cerr << "gc: " << prev_num << " -> " << Node::marked_num << endl;
			}
			long long q;
			scanf("%lld", &q);
			p = cycleTake(p, q);
		}
		ord.clear();
		dfs(p);
		reverse(ord.begin(), ord.end());
		for(Node::Ref x : ord)
			x->dp_cnt = 0;
		p->dp_cnt = 1;
		vector<ll> ans(N);
		for(Node::Ref x : ord) {
			ans[x->val - 1] += x->dp_cnt;
			if(x->left)
				x->left->dp_cnt += x->dp_cnt;
			if(x->right)
				x->right->dp_cnt += x->dp_cnt;
		}
		for(int i = 0; i < N; ++ i)
			printf("%lld\n", ans[i]);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:238:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &q);
                     ^

Judge Result