oj.uz

Submission #749332

# Submission time Handle Problem Language Result Execution time Memory
749332 2023-05-27T19:02:05 Z amunduzbaev Sequence (APIO23_sequence) C++17
50 / 100
 2000 ms 56296 KB 
#include "sequence.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ar array
typedef long long ll;
//~ #define int ll
 
const int INF = 1e9;
 
struct ST{
	vector<int> min, max, p;
	int N;
	
	ST(){
		N = 5e5 + 5;
		min.resize(N << 2);
		max.resize(N << 2);
		p.resize(N << 2);
	}
	
	ST(int N): N(N) {
		min.resize(N << 2);
		max.resize(N << 2);
		p.resize(N << 2);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		min[x << 1] += p[x], max[x << 1] += p[x], p[x << 1] += p[x];
		min[x << 1 | 1] += p[x], max[x << 1 | 1] += p[x], p[x << 1 | 1] += p[x];
		p[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			min[x] += v, max[x] += v, p[x] += v;
			return;
		}
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
		min[x] = ::min(min[x << 1], min[x << 1 | 1]);
		max[x] = ::max(max[x << 1], max[x << 1 | 1]);
	}
	
	void add(int l, int r, int v){
		assert(r < N);
		add(l, r, v, 0, N, 1);
	}
	
	int Max(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return -INF;
		if(lx >= l && rx <= r) return max[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return ::max(Max(l, r, lx, m, x << 1), Max(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int Max(int l, int r){
		assert(r < N);
		return Max(l, r, 0, N, 1);
	}
	
	int first_less(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(min[x] > v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			push(x, lx, rx);
			if(min[x << 1] <= v) return first_less(l, r, v, lx, m, x << 1);
			else {
				assert(min[x << 1 | 1] <= v); 
				return first_less(l, r, v, m + 1, rx, x << 1 | 1);
			}
		}
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		int res = first_less(l, r, v, lx, m, x << 1);
		if(res == -1) res = first_less(l, r, v, m + 1, rx, x << 1 | 1);
		return res;
	}
	
	int first_less(int l, int r, int v){
		assert(r < N);
		return first_less(l, r, v, 0, N, 1);
	}
	
	int Min(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return INF;
		if(lx >= l && rx <= r) return min[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return ::min(Min(l, r, lx, m, x << 1), Min(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int Min(int l, int r){
		assert(r < N);
		return Min(l, r, 0, N, 1);
	}
	
};
 
int sequence(int n, vector<int> a){ 
	a.insert(a.begin(), 0);
 
	ST A, B;
	
	vector<int> p(n);
	iota(p.begin(), p.end(), 1);
	sort(p.begin(), p.end(), [&](int i, int j){
		if(a[i] != a[j]) return a[i] < a[j];
		return i < j;
	});
	
	for(int i=1;i<=n;i++){
		B.add(i, i, i);
		A.add(i, i, -i);
	}
	
	int res = 0;
	for(int i=0,j=0;i<n;){
		vector<int> pos;
		while(j < n && a[p[i]] == a[p[j]]){
			pos.push_back(p[j]);
			A.add(p[j], n, 2);
			j++;
		}
		
		for(int k=0;k<(int)pos.size();k++){
			int L1 = B.first_less(0, pos[k] - 1, B.Max(pos[k], n));
			int L2 = A.first_less(0, pos[k] - 1, A.Max(pos[k], n));
			
			int L = max(L1, L2);
			
			assert(A.Min(0, L) <= A.Max(pos[k], n));
			assert(B.Min(0, L) <= B.Max(pos[k], n));
			assert(!L || (A.Min(0, L - 1) > A.Max(pos[k], n) || B.Min(0, L - 1) > B.Max(pos[k], n)));
			
			int l = upper_bound(pos.begin(), pos.end(), L) - pos.begin();
			res = max(res, k - l + 1);
		}
		
		while(i < j){
			B.add(p[i], n, -2);
			i++;
		}
	}
	
	return res;
}

/*
 
7
1 2 3 1 2 1 3
 
9
1 1 2 3 4 3 2 1 1
 
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
 
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47260 KB Output is correct
2 Correct 21 ms 47188 KB Output is correct
3 Correct 19 ms 47188 KB Output is correct
4 Correct 19 ms 47188 KB Output is correct
5 Correct 20 ms 47156 KB Output is correct
6 Correct 20 ms 47192 KB Output is correct
7 Correct 20 ms 47188 KB Output is correct
8 Correct 20 ms 47280 KB Output is correct
9 Correct 20 ms 47188 KB Output is correct
10 Correct 20 ms 47188 KB Output is correct
11 Correct 19 ms 47188 KB Output is correct
12 Correct 20 ms 47288 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47260 KB Output is correct
2 Correct 21 ms 47188 KB Output is correct
3 Correct 19 ms 47188 KB Output is correct
4 Correct 19 ms 47188 KB Output is correct
5 Correct 20 ms 47156 KB Output is correct
6 Correct 20 ms 47192 KB Output is correct
7 Correct 20 ms 47188 KB Output is correct
8 Correct 20 ms 47280 KB Output is correct
9 Correct 20 ms 47188 KB Output is correct
10 Correct 20 ms 47188 KB Output is correct
11 Correct 19 ms 47188 KB Output is correct
12 Correct 20 ms 47288 KB Output is correct
13 Correct 30 ms 47220 KB Output is correct
14 Correct 29 ms 47320 KB Output is correct
15 Correct 33 ms 47424 KB Output is correct
16 Correct 30 ms 47316 KB Output is correct
17 Correct 30 ms 47308 KB Output is correct
18 Correct 30 ms 47204 KB Output is correct
19 Correct 34 ms 47316 KB Output is correct
20 Correct 30 ms 47248 KB Output is correct
21 Correct 30 ms 47240 KB Output is correct
22 Correct 30 ms 47308 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47260 KB Output is correct
2 Execution timed out 2070 ms 53040 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Execution timed out 2029 ms 56296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 53028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47260 KB Output is correct
2 Correct 21 ms 47188 KB Output is correct
3 Correct 19 ms 47188 KB Output is correct
4 Correct 19 ms 47188 KB Output is correct
5 Correct 20 ms 47156 KB Output is correct
6 Correct 20 ms 47192 KB Output is correct
7 Correct 20 ms 47188 KB Output is correct
8 Correct 20 ms 47280 KB Output is correct
9 Correct 20 ms 47188 KB Output is correct
10 Correct 20 ms 47188 KB Output is correct
11 Correct 19 ms 47188 KB Output is correct
12 Correct 20 ms 47288 KB Output is correct
13 Correct 30 ms 47220 KB Output is correct
14 Correct 29 ms 47320 KB Output is correct
15 Correct 33 ms 47424 KB Output is correct
16 Correct 30 ms 47316 KB Output is correct
17 Correct 30 ms 47308 KB Output is correct
18 Correct 30 ms 47204 KB Output is correct
19 Correct 34 ms 47316 KB Output is correct
20 Correct 30 ms 47248 KB Output is correct
21 Correct 30 ms 47240 KB Output is correct
22 Correct 30 ms 47308 KB Output is correct
23 Correct 504 ms 48228 KB Output is correct
24 Correct 500 ms 48224 KB Output is correct
25 Correct 489 ms 48228 KB Output is correct
26 Correct 475 ms 48348 KB Output is correct
27 Correct 495 ms 48176 KB Output is correct
28 Correct 511 ms 48280 KB Output is correct
29 Correct 470 ms 48352 KB Output is correct
30 Correct 490 ms 48472 KB Output is correct
31 Correct 457 ms 48968 KB Output is correct
32 Correct 484 ms 48216 KB Output is correct
33 Correct 516 ms 48440 KB Output is correct
34 Correct 496 ms 48324 KB Output is correct
35 Correct 470 ms 48228 KB Output is correct
36 Correct 511 ms 48344 KB Output is correct
37 Correct 562 ms 48324 KB Output is correct
38 Correct 536 ms 48328 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47260 KB Output is correct
2 Correct 21 ms 47188 KB Output is correct
3 Correct 19 ms 47188 KB Output is correct
4 Correct 19 ms 47188 KB Output is correct
5 Correct 20 ms 47156 KB Output is correct
6 Correct 20 ms 47192 KB Output is correct
7 Correct 20 ms 47188 KB Output is correct
8 Correct 20 ms 47280 KB Output is correct
9 Correct 20 ms 47188 KB Output is correct
10 Correct 20 ms 47188 KB Output is correct
11 Correct 19 ms 47188 KB Output is correct
12 Correct 20 ms 47288 KB Output is correct
13 Correct 30 ms 47220 KB Output is correct
14 Correct 29 ms 47320 KB Output is correct
15 Correct 33 ms 47424 KB Output is correct
16 Correct 30 ms 47316 KB Output is correct
17 Correct 30 ms 47308 KB Output is correct
18 Correct 30 ms 47204 KB Output is correct
19 Correct 34 ms 47316 KB Output is correct
20 Correct 30 ms 47248 KB Output is correct
21 Correct 30 ms 47240 KB Output is correct
22 Correct 30 ms 47308 KB Output is correct
23 Execution timed out 2070 ms 53040 KB Time limit exceeded
24 Halted 0 ms 0 KB -