Submission #138469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138469	2019-07-30T05:01:17 Z	김세빈(#3318)	Non-boring sequences (CERC12_D)	C++14	1 / 1	1414 ms	41236 KB

D

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct query{
	ll l, r, v;
	query() {}
	query(ll l, ll r, ll v) : l(l), r(r), v(v) {}
};

struct segtree{
	ll T[606060], S[606060], V[606060];
	
	void addval(ll p, ll s, ll e, ll l, ll r, ll v)
	{
		if(e < l || r < s) return;
		if(l <= s && e <= r){
			S[p] += v;
			if(S[p] == 0) V[p] = T[p];
			else V[p] = e - s + 1;
			return;
		}
		
		addval(p << 1, s, s + e >> 1, l, r, v);
		addval(p << 1 | 1, (s + e >> 1) + 1, e, l, r, v);
		
		T[p] = V[p << 1] + V[p << 1 | 1];
		if(S[p] == 0) V[p] = T[p];
		else V[p] = e - s + 1;
	}
	
	ll getval() { return V[1]; }
};

segtree T;
vector <query> Q[202020];
vector <ll> X;
ll A[202020], C[202020], L[202020], R[202020];
ll n;

bool tc()
{
	ll i, s;
	
	scanf("%lld", &n);
	
	X.clear();
	
	for(i=1; i<=n; i++){
		scanf("%lld", A + i);
		X.push_back(A[i]);
	}
	
	sort(X.begin(), X.end());
	
	for(i=0; i<=n+1; i++){
		Q[i].clear();
		C[i] = 0;
	}
	
	for(i=1; i<=n; i++){
		A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
		L[i] = C[A[i]] + 1; C[A[i]] = i;
	}
	
	for(i=0; i<n; i++){
		C[i] = n + 1;
	}
	
	for(i=n; i>=1; i--){
		R[i] = C[A[i]] - 1; C[A[i]] = i;
		Q[L[i]].emplace_back(i, R[i], 1);
		Q[i + 1].emplace_back(i, R[i], -1);
	}
	
	s = 0;
	
	for(i=1; i<=n+1; i++){
		for(query &q: Q[i]){
			T.addval(1, 1, n, q.l, q.r, q.v);
		}
		
		s += T.getval();
	}
	
	return s != n * (n + 1) / 2;
}

int main()
{
	int t;
	
	scanf("%d", &t);
	
	for(; t--; ){
		printf("%s\n", tc()? "boring" : "non-boring");
	}
	
	return 0;
}

Compilation message

D.cpp: In member function 'void segtree::addval(ll, ll, ll, ll, ll, ll)':
D.cpp:26:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   addval(p << 1, s, s + e >> 1, l, r, v);
                     ~~^~~
D.cpp:27:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   addval(p << 1 | 1, (s + e >> 1) + 1, e, l, r, v);
                       ~~^~~
D.cpp: In function 'bool tc()':
D.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
D.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", A + i);
   ~~~~~^~~~~~~~~~~~~~~
D.cpp: In function 'int main()':
D.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	5880 KB	Output is correct
2	Correct	396 ms	21812 KB	Output is correct
3	Correct	583 ms	38204 KB	Output is correct
4	Correct	312 ms	41236 KB	Output is correct
5	Correct	1414 ms	37604 KB	Output is correct
6	Correct	1137 ms	35812 KB	Output is correct
7	Correct	946 ms	35684 KB	Output is correct