oj.uz

Submission #852076

# Submission time Handle Problem Language Result Execution time Memory
852076 2023-09-21T08:01:31 Z mychecksedad Sequence (APIO23_sequence) C++17
7 / 100
 849 ms 48720 KB 
// #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,  -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;
			if(l > 1){
				array<int, 2> f = get(1, n, 1, l - 1, 1);
				a2 = calc(zero, f);
			}else
				a2 = zero;

			a1[0] -= k;
			// 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;
			}
		}
	}
	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

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:127:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |   int m = l+r>>1;
      |           ~^~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Incorrect 3 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Incorrect 3 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 143 ms 43088 KB Output is correct
3 Correct 286 ms 43080 KB Output is correct
4 Correct 468 ms 35252 KB Output is correct
5 Correct 141 ms 42068 KB Output is correct
6 Correct 162 ms 42064 KB Output is correct
7 Correct 200 ms 35636 KB Output is correct
8 Correct 849 ms 35780 KB Output is correct
9 Correct 133 ms 35176 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 48720 KB Output is correct
2 Correct 162 ms 48720 KB Output is correct
3 Correct 184 ms 48208 KB Output is correct
4 Correct 179 ms 48336 KB Output is correct
5 Incorrect 234 ms 45776 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Incorrect 3 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Incorrect 3 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -