Submission 837 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
837	15/05/2013 23:00:55	leandro	E - For Fun	Accepted	2933	30.5 KiB	GNU G++ 5.1.0

Code

/*
username: leandro
*/
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <set>
#include <map>
#include <sstream>
#include <queue>
#include <stack>
#include <ctime>

using namespace std;

//////////////////////////////////////
typedef long long i64;
typedef complex<double> pnt;
typedef pair<int, int> pii;
typedef vector<int> vi;
//////////////////////////////////////
const int oo = 1 << 30;
const double PI = M_PI;
const double EPS = 1e-15;
//////////////////////////////////////
#define F first
#define S second
#define foreach(i, u) \
		for (typeof(u.begin()) i = u.begin(); i != u.end(); i++)
#define REP(i, n) \
		for (int i = 0; i < (n); i++)
#define FOR(i, n) \
		for (int i = 1; i <= (n); i++)
//////////////////////////////////////
#define DEBUG(x) \
		cout << #x << " = " << x << endl

const int
	MaxA = 26,
	MaxN = 100005;

int N, Q;
char S[MaxN];
int total[MaxA];
int cumul[MaxA];

struct tree
{
	tree* L;
	tree* R;
	int lo, hi;
	int cnt[MaxA];
	bool lazy;
	tree(int __lo, int __hi)
	{
		L = NULL;
		R = NULL;
		lo = __lo;
		hi = __hi;
		lazy = false;
		for (int i = 0; i < MaxA; i++)
			cnt[i] = 0;
		if (lo != hi)
		{
			int mid = (lo + hi) >> 1;
			L = new tree(lo, mid);
			R = new tree(mid + 1, hi);
			sumUp();
		}
		else
		{
			cnt[ S[lo - 1] - 'a' ] = 1;
		}
	}

int length()
	{
		return hi - lo + 1;
	}

void sumUp()
	{
		for (int i = 0; i < MaxA; i++)
			cnt[i] = L->cnt[i] + R->cnt[i];
	}

void assignSegment(int start, int end, int* __cnt)
	{
		cumul[0] = __cnt[0];
		for (int i = 0; i < MaxA; i++)
		{
			cnt[ i ] = 0;
			cumul[i] = cumul[i - 1] + __cnt[i];
		}

int posS = -1;
		int posE = -1;
		for (int i = 0; i < MaxA; i++)
		{
			if (posS == -1 && cumul[i] >= start) posS = i;
			if (posE == -1 && cumul[i] >=   end) posE = i;
		}

if (cumul[posS] >= end)
		{
			cnt[posS] = end - start + 1;
			return;
		}

for (int i = posS; i <= posE; i++)
		{
			if (i == posS)
				cnt[i] = cumul[i] - start + 1;
			else
			if (i == posE)
				cnt[i] = end - cumul[i - 1];
			else
				cnt[i] = __cnt[i];
		}
	}

void propagate()
	{
		lazy = false;
		if (L != NULL)
		{
			L->assignSegment(1, L->length(), cnt);
			R->assignSegment(L->length() + 1, L->length() + R->length(), cnt);
			L->lazy = true;
			R->lazy = true;
		}
	}

void getCnt(int start, int end)
	{
		if (lazy)
			propagate();

if (start > hi || end < lo)
			return;

if (start <= lo && hi <= end)
		{
			for (int i = 0; i < MaxA; i++)
				total[i] += cnt[i];
			return;
		}

L->getCnt(start, end);
		R->getCnt(start, end);
		sumUp();
	}

void __update(int start, int end)
	{
		if (lazy)
			propagate();
		if (start > hi || end < lo)
			return;
		if (start <= lo && hi <= end)
		{
			lazy = true;
			assignSegment(lo - start + 1, hi - start + 1, total);
			propagate();
			return;
		}
		L->__update(start, end);
		R->__update(start, end);
		sumUp();
	}

void update(int start, int end)
	{
		for (int i = 0; i < MaxA; i++)
			total[i] = 0;
		getCnt(start, end);
		__update(start, end);
	}

void built()
	{
		if (lazy)
			propagate();

if (lo == hi)
		{
			for (int i = 0; i < MaxA; i++)
				if (cnt[i])
				{
					S[ lo-1 ] = 'a' + i;
					break;
				}
			return;
		}

L->built();
		R->built();

delete L;
		delete R;
	}
} *root;

int main()
{
	cin.sync_with_stdio( false );

cin >> S;
	N = strlen(S);

root = new tree(1, N);
	for (cin >> Q; Q; Q--)
	{
		int a, b;
		cin >> a >> b;
		root->update(a + 1, b);
	}

root->built();

cout << S << endl;

return 0;
}

Judgement Details

Test 01: 0.011 0.000 1416K ok
Test 02: 3.066 2.933 31264K ok
Test 03: 0.009 0.000 1424K ok
Test 04: 0.012 0.000 1464K ok
Test 05: 0.024 0.016 1564K ok
Test 06: 0.029 0.031 1652K ok
Test 07: 2.219 2.184 7380K ok
Test 08: 0.816 0.749 16340K ok
Test 09: 2.545 2.371 25084K ok
Test 10: 0.676 0.640 28840K ok
Accepted

Matcom Online Grader