Submission #851938

#	Time	Username	Problem	Language	Result	Execution time	Memory
851938		mychecksedad	Sequence (APIO23_sequence)	C++17	0 / 100	1788 ms	48720 KiB

sequence

#include<sequence.h>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 5e5+10;
 
int n, lazy[4*N];
array<int, 2> T[4*N], zero = {0, 0}; // pos min, pos max, neg min, neg max
vector<int> c[N], arr;
 
array<int, 2> calc(array<int, 2> &a, array<int, 2> &b){
	array<int, 2> res;
	res[0] = min(a[0], b[0]);
	res[1] = max(a[1], b[1]);
	return res;
}
 
void build(int l, int r, int k){
	if(l == r){
		T[k][0] = l;
		T[k][1] = l;
		lazy[k] = 0;
		return;
	}
	int m = l+r>>1;
	build(l, m, k<<1);
	build(m+1, r, k<<1|1);
	lazy[k] = 0;
	T[k] = calc(T[k<<1], T[k<<1|1]);
}
 
void push(int k){
	if(lazy[k] != 0){
		for(int i = 0; i < 2; ++i) T[k<<1][i] += lazy[k];
		for(int i = 0; i < 2; ++i) T[k<<1|1][i] += lazy[k];
		lazy[k<<1] += lazy[k];
		lazy[k<<1|1] += lazy[k];
		lazy[k] = 0;
	}
}
 
 
void update(int l, int r, int ql, int qr, int k, int delta){
	if(ql > r || l > qr) return;
	if(ql <= l && r <= qr){
		for(int i = 0; i < 2; ++i) T[k][i] += delta;
		lazy[k] += delta;
		return;
	}
	push(k);
	int m = l+r>>1;
	update(l, m, ql, qr, k<<1, delta);
	update(m+1, r, ql, qr, k<<1|1, delta);
	T[k] = calc(T[k<<1], T[k<<1|1]);
}
 
array<int, 2> get(int l, int r, int ql, int qr, int k){
	if(ql > r || l > qr) return {0, -1};
	if(ql <= l && r <= qr){
		return T[k];
	}
	push(k);
 
	int m = l+r>>1;
 
	array<int, 2> a1 = get(l, m, ql, qr, k<<1);
	array<int, 2> a2 = get(m+1, r, ql, qr, k<<1|1);
	
	if(a1[0] > a1[1])
		return a2;
	if(a2[0] > a2[1])
		return a1;
	return calc(a1, a2);
}
 
 
bool check(int k){
	vector<int> v;
	for(int i = 1; i <= n; ++i) if(c[i].size() >= k) v.pb(i);
	sort(all(v));
 
	int last = 1; // last non applied
	build(1, n, 1);
	for(int x: v){
		// cout << k << ' ' << x << '\n';
		while(last <= x){
			for(auto pos: c[last]){
				update(1, n, pos, n, 1, last == x ? -1 : -2);
			}
			++last;
		}
 
		int l, r;
		for(int i = 0; i < c[x].size() - k + 1; ++i){
			l = c[x][i], r = c[x][i + k - 1];
			// cout << k << ' ' << x << ' ' << l << ' ' << r << '\n';
			array<int, 2> a1 = get(1, n, r, n, 1);
			array<int, 2> a2;
			a1[0] -= 2 * k;
			if(l > 1){
				array<int, 2> f = get(1, n, 1, l - 1, 1);
				a2 = calc(zero, f);
			}else
				a2 = zero;
 
			// cout << a1[0] << ' ' << a1[1] << ' ' << a2[0] << ' ' << a2[1] << "f\n";
 
			if((a1[0] >= a2[0] && a1[0] <= a2[1]) || (a2[0] >= a1[0] && a2[0] <= a1[1])){
				return 1;
			}
		}
		for(auto pos: c[x]){
			update(1, n, pos, n, 1, -1);
		}
	}
	return 0;
}
 
int sequence(int _n, vector<int> A){
	n = _n;
	int ans = 1, l = 2, r = n;
	arr = A;
	for(int i = 0; i < n; ++i){
		c[A[i]].pb(i + 1);
	}
 
	while(l <= r){
		int m = l+r>>1;
		if(check(m)){
			ans = m;
			l = m + 1;
		}else{
			r = m - 1;
		}
	}
 
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'void build(int, int, int)':
sequence.cpp:27:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int m = l+r>>1;
      |          ~^~
sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int m = l+r>>1;
      |          ~^~
sequence.cpp: In function 'std::array<int, 2> get(int, int, int, int, int)':
sequence.cpp:66:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m = l+r>>1;
      |          ~^~
sequence.cpp: In function 'bool check(int)':
sequence.cpp:81:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |  for(int i = 1; i <= n; ++i) if(c[i].size() >= k) v.pb(i);
      |                                 ~~~~~~~~~~~~^~~~
sequence.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int i = 0; i < c[x].size() - k + 1; ++i){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:130:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |   int m = l+r>>1;
      |           ~^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18