Submission #360676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
360676	2021-01-28T05:45:38 Z	arnold518	Non-boring sequences (CERC12_D)	C++14	1 / 1	2093 ms	21228 KB

D

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int TC, N;
int A[MAXN+10];

int tree[MAXN*4+10], lazy[MAXN*4+10];

void busy(int node, int tl, int tr)
{
	if(lazy[node]==0) return;
	tree[node]+=lazy[node];
	if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
	lazy[node]=0;
}

void init(int node, int tl, int tr)
{
	tree[node]=lazy[node]=0;
	if(tl==tr) return;
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
}

void update(int node, int tl, int tr, int l, int r, int v)
{
	busy(node, tl, tr);
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		lazy[node]+=v;
		busy(node, tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, v);
	update(node*2+1, mid+1, tr, l, r, v);
	tree[node]=min(tree[node*2], tree[node*2+1]);
}

int query(int node, int tl, int tr, int l, int r)
{
	busy(node, tl, tr);
	if(l<=tl && tr<=r) return tree[node];
	if(r<tl || tr<l) return 987654321;
	int mid=tl+tr>>1;
	return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}

int main()
{
	int i, j;

	scanf("%d", &TC);
	while(TC--)
	{
		scanf("%d", &N);
		for(i=1; i<=N; i++) scanf("%d", &A[i]);
		init(1, 1, N);

		map<int, pii> M;
		bool ans=true;
		for(i=1; i<=N; i++)
		{
			update(1, 1, N, M[A[i]].first, M[A[i]].second, -1);
			M[A[i]]=pii(M[A[i]].second+1, i);
			update(1, 1, N, M[A[i]].first, M[A[i]].second, 1);

			if(query(1, 1, N, 1, i)==0) ans=false;
		}
		if(ans) printf("non-boring\n");
		else printf("boring\n");
	}
}

Compilation message

D.cpp: In function 'void init(int, int, int)':
D.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid=tl+tr>>1;
      |          ~~^~~
D.cpp: In function 'void update(int, int, int, int, int, int)':
D.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int mid=tl+tr>>1;
      |          ~~^~~
D.cpp: In function 'int query(int, int, int, int, int)':
D.cpp:53:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid=tl+tr>>1;
      |          ~~^~~
D.cpp: In function 'int main()':
D.cpp:59:9: warning: unused variable 'j' [-Wunused-variable]
   59 |  int i, j;
      |         ^
D.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d", &TC);
      |  ~~~~~^~~~~~~~~~~
D.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
D.cpp:65:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   for(i=1; i<=N; i++) scanf("%d", &A[i]);
      |                       ~~~~~^~~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	2540 KB	Output is correct
2	Correct	667 ms	9088 KB	Output is correct
3	Correct	961 ms	21228 KB	Output is correct
4	Correct	619 ms	13804 KB	Output is correct
5	Correct	2093 ms	20668 KB	Output is correct
6	Correct	1437 ms	16872 KB	Output is correct
7	Correct	1187 ms	15212 KB	Output is correct