oj.uz

Submission #749766

# Submission time Handle Problem Language Result Execution time Memory
749766 2023-05-28T12:59:21 Z penguin133 Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 129592 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
struct node{
	int s, e, m;
	int mx, mn, lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		lazy = 0;
		mn = s + 1, mx = e + 1;
	}
	
	void prop(){
		if(!lazy)return;
		mx += lazy, mn += lazy;
		if(s != e)l->lazy += lazy, r->lazy += lazy;
		lazy = 0;
	}
	
	void upd(int a, int b, int c){
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			mn= min(l->mn, r->mn);
			mx=  max(l->mx, r->mx);
		}
	}
	
	pi qry(int a, int b){
		prop();
		if(a == s && b == e)return {mn, mx};
		if(b <= m)return l->qry(a, b);
		else if(a > m)return r->qry(a, b);
		else{
			pi lft = l->qry(a, m), rgt = r->qry(m+1 ,b);
			return {min(lft.fi, rgt.fi), max(lft.se, rgt.se)};
		}
	}
	
	int qm(int a, int b){
		prop();
		if(a == s && b == e)return mx;
		if(b <= m)return l->qm(a, b);
		if(a > m)return r->qm(a, b);
		return max(l->qm(a, m), r->qm(m+1, b));
	}
	
	int qmm(int a, int b){
		prop();
		if(a == s && b == e)return mn;
		if(b <= m)return l->qmm(a, b);
		if(a > m)return r->qmm(a, b);
		return min(l->qmm(a, m), r->qmm(m+1, b));
	}
	
}*lft;
 
struct node2{
	int s, e, m;
	int mx, mn, lazy;
	node2 *l, *r;
	node2(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node2(s, m), r = new node2(m+1, e);
		lazy = 0, mx = (n - s), mn = (n - e);
	}
	
	void prop(){
		if(!lazy)return;
		mx += lazy, mn += lazy;
		if(s != e)l->lazy += lazy, r->lazy += lazy;
		lazy = 0;
	}
	
	void upd(int a, int b, int c){
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			mn= min(l->mn, r->mn);
			mx=  max(l->mx, r->mx);
		}
	}
	int qm(int a, int b){
		prop();
		if(a == s && b == e)return mx;
		if(b <= m)return l->qm(a, b);
		if(a > m)return r->qm(a, b);
		return max(l->qm(a, m), r->qm(m+1, b));
	}
	
	int qmm(int a, int b){
		prop();
		if(a == s && b == e)return mn;
		if(b <= m)return l->qmm(a, b);
		if(a > m)return r->qmm(a, b);
		return min(l->qmm(a, m), r->qmm(m+1, b));
	}
	
}*rgt;
 
vector <int> occ[500005];
int B[10][500001], lf[500005], rg[500005];
 
void upd(int f[], int l, int r, int v){
	l++;
	r += 2;
	for(;l<=n;l+=(l & -l))f[l] += v;
	for(;r<=n;r+=(r & -r))f[r] -= v;
}
 
int qr(int f[], int p){
	p++;
	int res = 0;
	for(;p;p-=(p & -p))res += f[p];
	return res;
}
 
int sequence(int N, vector <int> A){
	n = N;
	for(int i=0;i<N;i++)occ[A[i]].push_back(i);
	lft = new node(0, N - 1);
	rgt = new node2(0, N - 1);
	int ans = 1;
	for(int i=0;i<N;i++){
		upd(lf, i, N, 1);
		upd(rg, 0, i, 1);
	}
	for(int i=1;i<=N;i++){
		
		int in = 0;
		for(int j = 0; j < (int)occ[i].size(); j++){
			int r = occ[i][j];
			int tmp2 = lft->qm(r, N - 1), ref2 = qr(lf, r), tmp = rgt->qm(0, r);
			int ref = qr(rg, r);
			tmp -= ref;
			int tmp5 = (r == 0 ? 0 : ref2 - 1);
          
			tmp2 -= ref2; 
			B[0][j] = tmp, B[1][j] = ref, B[2][j] = tmp2, B[3][j] = ref2, B[8][j] = tmp5;
		}
		
		for(auto j : occ[i]){
			lft->upd(j, N - 1, -2);
			rgt->upd(0, j, -2);
			upd(lf, j, N - 1, -2);
			upd(rg, 0, j, -2);
		}
		for(int j = 0; j < (int)occ[i].size(); j++){
			int r = occ[i][j];
			int tmp4 = lft->qmm(r, N - 1), ref4 = qr(lf, r);
			tmp4 -= ref4;
			
			int tmp3 = rgt->qmm(0, r);
			int ref3 = qr(rg, r);
			
			tmp3 -= ref3;
			int tmp6 = (r == 0 ? 0 : ref4 + 1);
			B[4][j] = tmp3, B[5][j] = ref3, B[6][j] = tmp4, B[7][j] = ref4, B[9][j] = tmp6;
			int tmp2 = B[2][j], ref2 = B[3][j];
			while(in + ans <= j){
				int tmp = B[0][in];
				tmp3 = B[4][in], ref3 = B[5][in];
				tmp += tmp2;
				tmp3 += tmp4;
				int val = ref2 - B[8][in];
				int val2 = ref4 - B[9][in];
				long long mn = val + tmp, mx = val2 + tmp3;
				if(mn * mx > 0)in++;
				else break;
			}
			//cout << i << ' ' << j << ' ' << in << '\n';
			ans = max(ans, j - in + 1);
        }
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12028 KB Output is correct
3 Correct 8 ms 12128 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12160 KB Output is correct
9 Correct 8 ms 12160 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12096 KB Output is correct
12 Correct 8 ms 12116 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12028 KB Output is correct
3 Correct 8 ms 12128 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12160 KB Output is correct
9 Correct 8 ms 12160 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12096 KB Output is correct
12 Correct 8 ms 12116 KB Output is correct
13 Correct 10 ms 12548 KB Output is correct
14 Correct 9 ms 12500 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 10 ms 12492 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 9 ms 12604 KB Output is correct
19 Correct 10 ms 12500 KB Output is correct
20 Correct 9 ms 12500 KB Output is correct
21 Correct 9 ms 12596 KB Output is correct
22 Correct 10 ms 12592 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 773 ms 123812 KB Output is correct
3 Correct 855 ms 123804 KB Output is correct
4 Correct 651 ms 119856 KB Output is correct
5 Correct 818 ms 122800 KB Output is correct
6 Correct 790 ms 122864 KB Output is correct
7 Correct 693 ms 116640 KB Output is correct
8 Correct 686 ms 116764 KB Output is correct
9 Correct 715 ms 122912 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12028 KB Output is correct
2 Correct 836 ms 126700 KB Output is correct
3 Correct 786 ms 122372 KB Output is correct
4 Correct 737 ms 122352 KB Output is correct
5 Correct 740 ms 126708 KB Output is correct
6 Correct 668 ms 125728 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1413 ms 129576 KB Output is correct
2 Correct 1388 ms 129592 KB Output is correct
3 Correct 1412 ms 128960 KB Output is correct
4 Correct 1412 ms 128960 KB Output is correct
5 Correct 1071 ms 125644 KB Output is correct
6 Correct 1103 ms 125652 KB Output is correct
7 Correct 782 ms 124472 KB Output is correct
8 Correct 787 ms 124236 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12028 KB Output is correct
3 Correct 8 ms 12128 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12160 KB Output is correct
9 Correct 8 ms 12160 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12096 KB Output is correct
12 Correct 8 ms 12116 KB Output is correct
13 Correct 10 ms 12548 KB Output is correct
14 Correct 9 ms 12500 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 10 ms 12492 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 9 ms 12604 KB Output is correct
19 Correct 10 ms 12500 KB Output is correct
20 Correct 9 ms 12500 KB Output is correct
21 Correct 9 ms 12596 KB Output is correct
22 Correct 10 ms 12592 KB Output is correct
23 Correct 220 ms 30028 KB Output is correct
24 Correct 212 ms 30020 KB Output is correct
25 Correct 218 ms 30008 KB Output is correct
26 Correct 201 ms 28984 KB Output is correct
27 Correct 200 ms 29012 KB Output is correct
28 Correct 213 ms 28896 KB Output is correct
29 Correct 127 ms 29376 KB Output is correct
30 Correct 131 ms 29384 KB Output is correct
31 Correct 102 ms 31796 KB Output is correct
32 Correct 103 ms 30916 KB Output is correct
33 Correct 220 ms 30204 KB Output is correct
34 Correct 220 ms 30180 KB Output is correct
35 Correct 204 ms 30228 KB Output is correct
36 Correct 210 ms 30152 KB Output is correct
37 Correct 210 ms 30180 KB Output is correct
38 Correct 225 ms 30252 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 8 ms 12028 KB Output is correct
3 Correct 8 ms 12128 KB Output is correct
4 Correct 8 ms 12160 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 7 ms 12124 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12160 KB Output is correct
9 Correct 8 ms 12160 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12096 KB Output is correct
12 Correct 8 ms 12116 KB Output is correct
13 Correct 10 ms 12548 KB Output is correct
14 Correct 9 ms 12500 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 10 ms 12492 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 9 ms 12604 KB Output is correct
19 Correct 10 ms 12500 KB Output is correct
20 Correct 9 ms 12500 KB Output is correct
21 Correct 9 ms 12596 KB Output is correct
22 Correct 10 ms 12592 KB Output is correct
23 Correct 773 ms 123812 KB Output is correct
24 Correct 855 ms 123804 KB Output is correct
25 Correct 651 ms 119856 KB Output is correct
26 Correct 818 ms 122800 KB Output is correct
27 Correct 790 ms 122864 KB Output is correct
28 Correct 693 ms 116640 KB Output is correct
29 Correct 686 ms 116764 KB Output is correct
30 Correct 715 ms 122912 KB Output is correct
31 Correct 836 ms 126700 KB Output is correct
32 Correct 786 ms 122372 KB Output is correct
33 Correct 737 ms 122352 KB Output is correct
34 Correct 740 ms 126708 KB Output is correct
35 Correct 668 ms 125728 KB Output is correct
36 Correct 1413 ms 129576 KB Output is correct
37 Correct 1388 ms 129592 KB Output is correct
38 Correct 1412 ms 128960 KB Output is correct
39 Correct 1412 ms 128960 KB Output is correct
40 Correct 1071 ms 125644 KB Output is correct
41 Correct 1103 ms 125652 KB Output is correct
42 Correct 782 ms 124472 KB Output is correct
43 Correct 787 ms 124236 KB Output is correct
44 Correct 220 ms 30028 KB Output is correct
45 Correct 212 ms 30020 KB Output is correct
46 Correct 218 ms 30008 KB Output is correct
47 Correct 201 ms 28984 KB Output is correct
48 Correct 200 ms 29012 KB Output is correct
49 Correct 213 ms 28896 KB Output is correct
50 Correct 127 ms 29376 KB Output is correct
51 Correct 131 ms 29384 KB Output is correct
52 Correct 102 ms 31796 KB Output is correct
53 Correct 103 ms 30916 KB Output is correct
54 Correct 220 ms 30204 KB Output is correct
55 Correct 220 ms 30180 KB Output is correct
56 Correct 204 ms 30228 KB Output is correct
57 Correct 210 ms 30152 KB Output is correct
58 Correct 210 ms 30180 KB Output is correct
59 Correct 225 ms 30252 KB Output is correct
60 Execution timed out 2053 ms 123808 KB Time limit exceeded
61 Halted 0 ms 0 KB -