Submission #848371


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

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

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

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 20
TLE × 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 936 ms 207988 KB
02.txt AC 938 ms 208116 KB
03.txt AC 935 ms 208116 KB
04.txt AC 938 ms 208116 KB
05.txt AC 938 ms 208116 KB
06.txt TLE 2120 ms 205056 KB
07.txt TLE 2120 ms 205056 KB
08.txt TLE 2120 ms 205056 KB
09.txt TLE 2120 ms 205056 KB
10.txt TLE 2120 ms 205056 KB
11.txt TLE 2120 ms 205056 KB
12.txt TLE 2120 ms 205056 KB
13.txt TLE 2120 ms 205056 KB
14.txt TLE 2120 ms 205056 KB
15.txt TLE 2123 ms 205056 KB
16.txt TLE 2120 ms 205056 KB
17.txt TLE 2120 ms 205056 KB
18.txt TLE 2120 ms 205056 KB
19.txt TLE 2120 ms 205056 KB
20.txt TLE 2120 ms 205056 KB
21.txt TLE 2120 ms 205056 KB
22.txt TLE 2120 ms 205056 KB
23.txt TLE 2120 ms 205056 KB
24.txt AC 604 ms 208624 KB
25.txt AC 643 ms 209388 KB
26.txt AC 533 ms 206964 KB
27.txt AC 398 ms 205952 KB
28.txt AC 426 ms 206964 KB
29.txt AC 444 ms 206964 KB
30.txt AC 449 ms 206964 KB
31.txt AC 331 ms 205056 KB
32.txt AC 354 ms 206964 KB
33.txt AC 331 ms 205056 KB
34.txt AC 363 ms 208244 KB
35.txt AC 332 ms 205056 KB
36.txt AC 335 ms 205056 KB
s1.txt AC 334 ms 205056 KB
s2.txt AC 369 ms 205056 KB