Submission #848075


Source Code Expand

Copy
#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;
	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;
		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;

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;
	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::Ref p = build(1, N);
		rep(i, Q) {
			if(i % 10000 == 9999) {
				++ Node::last_mark;
				do_mark(p);
			}
			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

Submission Time
Task E - Sequential operations on Sequence
User anta
Language C++14 (GCC 5.4.1)
Score 0
Code Size 7091 Byte
Status RE
Exec Time 1753 ms
Memory 209388 KB

Compile Error

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 20
RE × 18
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 956 ms 207988 KB
02.txt AC 967 ms 208116 KB
03.txt AC 980 ms 208116 KB
04.txt AC 969 ms 208116 KB
05.txt AC 951 ms 208116 KB
06.txt RE 1573 ms 205056 KB
07.txt RE 1562 ms 205056 KB
08.txt RE 1558 ms 205056 KB
09.txt RE 1587 ms 205056 KB
10.txt RE 1589 ms 205056 KB
11.txt RE 1557 ms 205056 KB
12.txt RE 1553 ms 205056 KB
13.txt RE 1615 ms 205056 KB
14.txt RE 1566 ms 205056 KB
15.txt RE 1557 ms 205056 KB
16.txt RE 1558 ms 205056 KB
17.txt RE 1575 ms 205056 KB
18.txt RE 1607 ms 205056 KB
19.txt RE 1601 ms 205056 KB
20.txt RE 1555 ms 205056 KB
21.txt RE 1607 ms 205056 KB
22.txt RE 1753 ms 205056 KB
23.txt RE 1166 ms 205056 KB
24.txt AC 661 ms 208624 KB
25.txt AC 714 ms 209388 KB
26.txt AC 594 ms 206964 KB
27.txt AC 404 ms 205952 KB
28.txt AC 440 ms 206964 KB
29.txt AC 415 ms 206964 KB
30.txt AC 446 ms 206964 KB
31.txt AC 332 ms 205056 KB
32.txt AC 398 ms 206964 KB
33.txt AC 346 ms 205056 KB
34.txt AC 366 ms 208244 KB
35.txt AC 332 ms 205056 KB
36.txt AC 334 ms 205056 KB
s1.txt AC 366 ms 205056 KB
s2.txt AC 334 ms 205056 KB