Submission 1707 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1707	12/06/2013 20:27:27	rlac	C - Mánager de memoria	Accepted	4368	308.9 KiB	GNU G++ 5.1.0

Code

#include <algorithm>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#ifdef RLAC
	#define DEB(a)			clog << __LINE__ << ": " << #a << " = " << (a) << endl
	#define DEB2(a, b)		DEB(a); DEB(b)
	#define OUT(a, n)		for (int J = 0; J < (n); ++J)	clog << (a)[J] << " \n"[J == (n) - 1];
	#define OUT2(a, n, m)	{	DEB(a);	for (int I = 0; I < (n); ++I)	OUT(a[I], m);	}
	#define NAME			"default"
#else
	#define DEB(a)
	#define DEB2(a, b)
	#define OUT(a, n)
	#define OUT2(a, n, m)
#endif

using namespace std;

typedef complex<double> point;
typedef long long ll;
typedef pair<int, int> ii;

const int MAXN = 1e6 + 5;

//Begin persistent treap

int random ()	{	return (rand() << 15) + rand();	}

struct _node;
typedef _node* node;

struct _node 
{
	int v, cnt, id;
	ll sum;
	node lch, rch;
} *root;

int size (node t) 	{	return t != NULL ? t->cnt : 0;	}

ll sum (node t)		{	return t != NULL ? t->sum : 0;	}

void update (node t)
{
	if (t != NULL)
	{
		t->sum = sum(t->lch) + sum(t->rch) + t->v;
		t->cnt = size(t->lch) + size(t->rch) + 1;
	}
}

const int MAXS = 8e6;
int num, cnt, fr[MAXS], in[MAXN];
_node buf[MAXS];

int used[MAXS];

node new_node (int v, node l, node r, int num)
{		
	assert(num < MAXS);
	buf[num].v = v;
	buf[num].lch = l;
	buf[num].rch = r;
	buf[num].id = num;
	used[num] = -1;
	update(buf + num);
	return buf + num;
}

void dfs (node t, int cv)
{
	if (t != NULL)
	{
		used[t->id] = cv;
		dfs(t->lch, cv);
		dfs(t->rch, cv);
	}	
}

void collect (int cv)
{
	dfs(root, cv);
	
	for (int i = 0; i < num; ++i)
	{
		if (used[i] && used[i] != cv)
		{
			used[i] = 0;
			fr[cnt++] = i;
		}
	}
}

node new_node (int v, node l, node r)
{
	if (cnt > 0)
		return new_node(v, l, r, fr[--cnt]);
		
	return new_node(v, l, r, num++);
}

node build (int b, int e)
{
	if (b > e)
		return NULL;
		
	int m = (b + e) / 2;
	return new_node(in[m], build(b, m - 1), build(m + 1, e));
}

void split (node t, int cnt, node &l, node &r)
{
	if (t == NULL)
		l = r = NULL;
	else
	{
		int aux = size(t->lch);
		
		if (aux >= cnt)
		{
			split(t->lch, cnt, l, r);
			r = new_node(t->v, r, t->rch);
		}
		else
		{
			split(t->rch, cnt - aux - 1, l, r);
			l = new_node(t->v, t->lch, l);
		}
	}
}

node merge (node l, node r)
{
	if (l == NULL || r == NULL)
		return l != NULL ? l : r;
		
	if (random() % (l->cnt + r->cnt) < l->cnt)
	{
		return new_node(l->v, l->lch, merge(l->rch, r));
	}
	
	return new_node(r->v, merge(l, r->lch), r->rch);
}

//End persistent treap

int n, x, a, b, m, k, l;
char q[5];

void copy (int a, int b, int l)
{
	node n1, n2, n3, n4, n5;
	split(root, a, n1, n3);
	split(n3, l, n2, n1);
	split(root, b, n1, n4);
	split(n4, l, n5, n3);
	root = merge(n1, n2);
	root = merge(root, n3);
}

ll sum (node t, int cnt)
{
	if (t == NULL || cnt == 0)
		return 0;
		
	int aux = size(t->lch);
	
	if (aux >= cnt)
		return sum(t->lch, cnt);
		
	return sum(t->lch) + t->v + sum(t->rch, cnt - aux - 1);
}

ll sum (int a, int b)
{
	return sum(root, b + 1) - sum(root, a);
}

void print (node t, int a, int b)
{
	if (t == NULL)
		return;
		
	int cnt = size(t->lch);
	
	if (a < cnt)
		print(t->lch, a, b);
		
	if (a <= cnt && cnt <= b)
		cout << t->v << " ";
		
	if (cnt < b)
		print(t->rch, a - cnt - 1, b - cnt - 1);
}

void print (int a, int b)
{
	print(root, a, b);
	cout << '\n';
}

int main ()
{
	//Improvement region
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << setprecision(6) << fixed;
	clog.copyfmt(cout);

//Input region
	#ifdef RLAC
		system("notepad "NAME".in");
		freopen(NAME".in", "r", stdin);
		FILE * FILE_NAME = freopen(NAME".out", "w", stdout);
		int TIME = clock();
	#endif
	//Add your code here...
	cin >> n >> x >> a >> b >> m;
	
	for (int i = 0; i < n; ++i)
	{		
		in[i] = x;
		x = (x * 1ll * a + b) % m;
	}

root = build(0, n - 1);
	cin >> k;
	
	for (int i = 0, it = 0; i < k; ++i, ++it)
	{
		cin >> q >> a >> b;
		
		if (q[0] == 'c')
		{
			cin >> l;
			copy(a - 1, b - 1, l);
		}
		else if (q[0] == 's')
			cout << sum(a - 1, b - 1) << '\n';
		else
			print(a - 1, b - 1);
		
		if (it == 50000)
		{
			collect(i);
			it = 0;
		}
	}
	
	//Output region
	#ifdef RLAC
		cout << flush;
		clog << clock() - TIME << endl;
		fclose(FILE_NAME);
		system("notepad "NAME".out");
	#endif
	return 0;
}

Judgement Details

Test 01: 0.009 0.000 1432K ok
Test 02: 0.008 0.000 1432K ok
Test 03: 0.009 0.000 1436K ok
Test 04: 0.024 0.016 1616K ok
Test 05: 0.021 0.031 1472K ok
Test 06: 0.021 0.016 2700K ok
Test 07: 29.255 0.998 39808K ok
Test 08: 13.465 0.390 51632K ok
Test 09: 9.722 0.281 61176K ok
Test 10: 5.877 0.328 65396K ok
Test 11: 14.139 0.499 75440K ok
Test 12: 0.403 0.218 70804K ok
Test 13: 100.946 4.368 154860K ok
Test 14: 0.951 0.499 5756K ok
Test 15: 48.730 3.962 271824K ok
Test 16: 8.131 3.089 276404K ok
Test 17: 0.456 0.156 80932K ok
Test 18: 0.286 0.125 64276K ok
Test 19: 0.394 0.187 74860K ok
Test 20: 0.352 0.125 87960K ok
Test 21: 2.520 1.622 186020K ok
Test 22: 1.998 1.513 231140K ok
Test 23: 11.970 3.058 316344K ok
Accepted

Matcom Online Grader