Submission #848177


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 + 10000U >= Node::buf.size()) {
				++ 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 7375 Byte
Status TLE
Exec Time 2161 ms
Memory 238052 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 × 21
TLE × 17
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 967 ms 207988 KB
02.txt AC 933 ms 208116 KB
03.txt AC 931 ms 208116 KB
04.txt AC 933 ms 208116 KB
05.txt AC 939 ms 208116 KB
06.txt TLE 2126 ms 237924 KB
07.txt TLE 2126 ms 238052 KB
08.txt TLE 2126 ms 238052 KB
09.txt TLE 2126 ms 237924 KB
10.txt TLE 2126 ms 237924 KB
11.txt TLE 2122 ms 237924 KB
12.txt TLE 2126 ms 237924 KB
13.txt TLE 2122 ms 237924 KB
14.txt TLE 2126 ms 237924 KB
15.txt TLE 2126 ms 238052 KB
16.txt TLE 2126 ms 238052 KB
17.txt TLE 2122 ms 237924 KB
18.txt TLE 2122 ms 237924 KB
19.txt TLE 2130 ms 237924 KB
20.txt TLE 2126 ms 237924 KB
21.txt AC 1940 ms 237924 KB
22.txt TLE 2161 ms 237924 KB
23.txt TLE 2120 ms 205056 KB
24.txt AC 586 ms 208624 KB
25.txt AC 618 ms 209388 KB
26.txt AC 555 ms 206964 KB
27.txt AC 442 ms 205952 KB
28.txt AC 458 ms 206964 KB
29.txt AC 449 ms 206964 KB
30.txt AC 452 ms 206964 KB
31.txt AC 374 ms 205056 KB
32.txt AC 360 ms 206964 KB
33.txt AC 336 ms 205056 KB
34.txt AC 365 ms 208244 KB
35.txt AC 334 ms 205056 KB
36.txt AC 333 ms 205056 KB
s1.txt AC 333 ms 205056 KB
s2.txt AC 332 ms 205056 KB