Submission #251340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251340	2020-07-20T21:55:30 Z	luciocf	Lollipop (POI11_liz)	C++14	100 / 100	549 ms	37772 KB

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e6+10;

int a[maxn];
int pref[maxn];

int mx[2], l[2], r[2];

pii ans[maxn];

void get_0(int n)
{
	int mn[2], ind[2];

	mn[0] = 0, mn[1] = 1e9+10;
	ind[0] = 0, ind[1] = -1;

	for (int i = 1; i <= n; i++)
	{
		if (pref[i]%2 == 0)
		{
			if (pref[i]-mn[0] > mx[0])
			{
				mx[0] = pref[i]-mn[0];
				l[0] = ind[0]+1, r[0] = i;
			}

			if (pref[i] < mn[0])
			{
				mn[0] = pref[i];
				ind[0] = i;
			}
		}
		else
		{
			if (pref[i]-mn[1] > mx[0])
			{
				mx[0] = pref[i]-mn[1];
				l[0] = ind[1]+1, r[0] = i;
			}

			if (pref[i] < mn[1])
			{
				mn[1] = pref[i];
				ind[1] = i;
			}
		}
	}
}

void get_1(int n)
{
	int mn[2], ind[2];

	mn[0] = 0, mn[1] = 1e9+10;
	ind[0] = 0, ind[1] = -1;

	for (int i = 1; i <= n; i++)
	{
		if (pref[i]%2 == 0)
		{
			if (pref[i]-mn[1] > mx[1])
			{
				mx[1] = pref[i]-mn[1];
				l[1] = ind[1]+1, r[1] = i;
			}

			if (pref[i] < mn[0])
			{
				mn[0] = pref[i];
				ind[0] = i;
			}
		}
		else
		{
			if (pref[i]-mn[0] > mx[1])
			{
				mx[1] = pref[i]-mn[0];
				l[1] = ind[0]+1, r[1] = i;
			}

			if (pref[i] < mn[1])
			{
				mn[1] = pref[i];
				ind[1] = i;
			}
		}
	}
}

void gen_0(void)
{
	int L = l[0], R = r[0];
	int at = mx[0];

	while (at > 0)
	{
		ans[at] = {L, R};

		if (a[L] == 2)
			L++;
		else if (a[R] == 2)
			R--;
		else
			L++, R--;

		at -= 2;
	}
}

void gen_1(void)
{
	int L = l[1], R = r[1];
	int at = mx[1];

	while (at > 0)
	{
		ans[at] = {L, R};

		if (a[L] == 2)
			L++;
		else if (a[R] == 2)
			R--;
		else
			L++, R--;

		at -= 2;
	}
}


int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);


	for (int i = 1; i <= n; i++)
	{
		char c;
		scanf(" %c", &c);

		if (c == 'T') a[i] = 2, pref[i] = pref[i-1]+2;
		else a[i] = 1, pref[i] = pref[i-1]+1;
	}

	get_0(n); get_1(n);
	gen_0(); gen_1();

	while (m--)
	{
		int k;
		scanf("%d", &k);

		if (ans[k].first == 0) printf("NIE\n");
		else printf("%d %d\n", ans[k].first, ans[k].second);
	}
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
liz.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
liz.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	384 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	384 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	7 ms	640 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	640 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1152 KB	Output is correct
2	Correct	9 ms	1152 KB	Output is correct
3	Correct	35 ms	2424 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	2936 KB	Output is correct
2	Correct	147 ms	8440 KB	Output is correct
3	Correct	75 ms	5112 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	3200 KB	Output is correct
2	Correct	35 ms	2880 KB	Output is correct
3	Correct	81 ms	5620 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	6776 KB	Output is correct
2	Correct	112 ms	7032 KB	Output is correct
3	Correct	162 ms	10744 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	356 ms	15992 KB	Output is correct
2	Correct	297 ms	17144 KB	Output is correct
3	Correct	365 ms	21024 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	271 ms	19192 KB	Output is correct
2	Correct	349 ms	22188 KB	Output is correct
3	Correct	405 ms	25972 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	515 ms	36472 KB	Output is correct
2	Correct	454 ms	33016 KB	Output is correct
3	Correct	457 ms	32888 KB	Output is correct

Subtask #12
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	549 ms	37512 KB	Output is correct
2	Correct	535 ms	35320 KB	Output is correct
3	Correct	433 ms	37772 KB	Output is correct