oj.uz

Submission #851934

# Submission time Handle Problem Language Result Execution time Memory
851934 2023-09-20T20:38:17 Z mychecksedad Sequence (APIO23_sequence) C++17
13 / 100
 386 ms 51652 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+100;

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];

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 < int(c[x].size()) + 1 - k; ++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;

			// 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;
			}
			if(a1[0] < a2[0]){
				if(a2[0] - a1[1] <= k) return 1;
			}else{
				if(a1[0] - a2[1] <= k) 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;
	for(int i = 0; i < n; ++i){
		c[A[i]].pb(i + 1);
	}

	vector<int> sz;
	for(int i = 1; i <= n; ++i) if(c[i].size() > 0) sz.pb(c[i].size());
	sort(all(sz));
	for(int i = sz.size() - 1; i >= 0; --i){
		if(i == sz.size() - 1 || sz[i] != sz[i + 1]){
			if(check(sz[i])) return sz[i];
		}
	}

	return 1;
}

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: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:135:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   if(i == sz.size() - 1 || sz[i] != sz[i + 1]){
      |      ~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 17.0

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

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15192 KB Output is correct
2 Correct 79 ms 42376 KB Output is correct
3 Correct 161 ms 42432 KB Output is correct
4 Correct 130 ms 33540 KB Output is correct
5 Correct 80 ms 41412 KB Output is correct
6 Correct 82 ms 41416 KB Output is correct
7 Incorrect 364 ms 33668 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 86 ms 33276 KB Output is correct
3 Correct 386 ms 33208 KB Output is correct
4 Correct 96 ms 33208 KB Output is correct
5 Correct 122 ms 33276 KB Output is correct
6 Incorrect 253 ms 33212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 51652 KB Output is correct
2 Correct 107 ms 51652 KB Output is correct
3 Correct 121 ms 48320 KB Output is correct
4 Correct 125 ms 48320 KB Output is correct
5 Correct 216 ms 45252 KB Output is correct
6 Correct 220 ms 47304 KB Output is correct
7 Correct 292 ms 46020 KB Output is correct
8 Correct 179 ms 44420 KB Output is correct

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 18.0

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