oj.uz

Submission #749607

# Submission time Handle Problem Language Result Execution time Memory
749607 2023-05-28T09:55:05 Z penguin133 Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 156968 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());
struct node{
	int s, e, m;
	int mx, mn, lazy, val;
	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);
		mx = mn = lazy = val = 0;
	}
	
	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, *rgt, *lft2, *rgt2;
 
vector <int> occ[500005];
int B[10][500001];
int sequence(int N, vector <int> A){
	
	for(int i=0;i<N;i++)occ[A[i]].push_back(i);
	lft = new node(0, N - 1);
	rgt = new node(0, N - 1);
	int ans = 1;
	for(int i=0;i<N;i++){
		lft->upd(i, N - 1, 1);
		rgt->upd(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 = lft->qm(r, r), tmp = rgt->qm(0, r);
			int ref = rgt->qm(r, 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);
		}
		for(int j = 0; j < (int)occ[i].size(); j++){
			int r = occ[i][j];
			int tmp4 = lft->qmm(r, N - 1), ref4 = lft->qmm(r, r);
			tmp4 -= ref4;
			
			int tmp3 = rgt->qmm(0, r);
			int ref3 = rgt->qmm(r, 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 < 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 6 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12148 KB Output is correct
9 Correct 6 ms 12092 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 12152 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12148 KB Output is correct
9 Correct 6 ms 12092 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 12152 KB Output is correct
13 Correct 10 ms 12628 KB Output is correct
14 Correct 9 ms 12608 KB Output is correct
15 Correct 9 ms 12644 KB Output is correct
16 Correct 10 ms 12628 KB Output is correct
17 Correct 9 ms 12660 KB Output is correct
18 Correct 9 ms 12624 KB Output is correct
19 Correct 11 ms 12628 KB Output is correct
20 Correct 11 ms 12628 KB Output is correct
21 Correct 10 ms 12668 KB Output is correct
22 Correct 10 ms 12628 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 985 ms 151208 KB Output is correct
3 Correct 1022 ms 151212 KB Output is correct
4 Correct 895 ms 147264 KB Output is correct
5 Correct 1049 ms 150348 KB Output is correct
6 Correct 1006 ms 150348 KB Output is correct
7 Correct 894 ms 144184 KB Output is correct
8 Correct 883 ms 144312 KB Output is correct
9 Correct 884 ms 150316 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 1026 ms 154176 KB Output is correct
3 Correct 998 ms 149852 KB Output is correct
4 Correct 1029 ms 149748 KB Output is correct
5 Correct 1002 ms 154168 KB Output is correct
6 Correct 940 ms 153012 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1632 ms 156928 KB Output is correct
2 Correct 1621 ms 156968 KB Output is correct
3 Correct 1743 ms 156352 KB Output is correct
4 Correct 1771 ms 156396 KB Output is correct
5 Correct 1475 ms 153016 KB Output is correct
6 Correct 1510 ms 153016 KB Output is correct
7 Correct 1163 ms 151816 KB Output is correct
8 Correct 1147 ms 151504 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12148 KB Output is correct
9 Correct 6 ms 12092 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 12152 KB Output is correct
13 Correct 10 ms 12628 KB Output is correct
14 Correct 9 ms 12608 KB Output is correct
15 Correct 9 ms 12644 KB Output is correct
16 Correct 10 ms 12628 KB Output is correct
17 Correct 9 ms 12660 KB Output is correct
18 Correct 9 ms 12624 KB Output is correct
19 Correct 11 ms 12628 KB Output is correct
20 Correct 11 ms 12628 KB Output is correct
21 Correct 10 ms 12668 KB Output is correct
22 Correct 10 ms 12628 KB Output is correct
23 Correct 279 ms 34372 KB Output is correct
24 Correct 293 ms 34364 KB Output is correct
25 Correct 265 ms 34252 KB Output is correct
26 Correct 272 ms 33372 KB Output is correct
27 Correct 249 ms 33316 KB Output is correct
28 Correct 247 ms 33288 KB Output is correct
29 Correct 170 ms 33804 KB Output is correct
30 Correct 173 ms 33640 KB Output is correct
31 Correct 135 ms 36168 KB Output is correct
32 Correct 139 ms 35288 KB Output is correct
33 Correct 259 ms 34628 KB Output is correct
34 Correct 257 ms 34452 KB Output is correct
35 Correct 254 ms 34608 KB Output is correct
36 Correct 251 ms 34508 KB Output is correct
37 Correct 248 ms 34468 KB Output is correct
38 Correct 268 ms 34636 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12148 KB Output is correct
9 Correct 6 ms 12092 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 6 ms 12152 KB Output is correct
13 Correct 10 ms 12628 KB Output is correct
14 Correct 9 ms 12608 KB Output is correct
15 Correct 9 ms 12644 KB Output is correct
16 Correct 10 ms 12628 KB Output is correct
17 Correct 9 ms 12660 KB Output is correct
18 Correct 9 ms 12624 KB Output is correct
19 Correct 11 ms 12628 KB Output is correct
20 Correct 11 ms 12628 KB Output is correct
21 Correct 10 ms 12668 KB Output is correct
22 Correct 10 ms 12628 KB Output is correct
23 Correct 985 ms 151208 KB Output is correct
24 Correct 1022 ms 151212 KB Output is correct
25 Correct 895 ms 147264 KB Output is correct
26 Correct 1049 ms 150348 KB Output is correct
27 Correct 1006 ms 150348 KB Output is correct
28 Correct 894 ms 144184 KB Output is correct
29 Correct 883 ms 144312 KB Output is correct
30 Correct 884 ms 150316 KB Output is correct
31 Correct 1026 ms 154176 KB Output is correct
32 Correct 998 ms 149852 KB Output is correct
33 Correct 1029 ms 149748 KB Output is correct
34 Correct 1002 ms 154168 KB Output is correct
35 Correct 940 ms 153012 KB Output is correct
36 Correct 1632 ms 156928 KB Output is correct
37 Correct 1621 ms 156968 KB Output is correct
38 Correct 1743 ms 156352 KB Output is correct
39 Correct 1771 ms 156396 KB Output is correct
40 Correct 1475 ms 153016 KB Output is correct
41 Correct 1510 ms 153016 KB Output is correct
42 Correct 1163 ms 151816 KB Output is correct
43 Correct 1147 ms 151504 KB Output is correct
44 Correct 279 ms 34372 KB Output is correct
45 Correct 293 ms 34364 KB Output is correct
46 Correct 265 ms 34252 KB Output is correct
47 Correct 272 ms 33372 KB Output is correct
48 Correct 249 ms 33316 KB Output is correct
49 Correct 247 ms 33288 KB Output is correct
50 Correct 170 ms 33804 KB Output is correct
51 Correct 173 ms 33640 KB Output is correct
52 Correct 135 ms 36168 KB Output is correct
53 Correct 139 ms 35288 KB Output is correct
54 Correct 259 ms 34628 KB Output is correct
55 Correct 257 ms 34452 KB Output is correct
56 Correct 254 ms 34608 KB Output is correct
57 Correct 251 ms 34508 KB Output is correct
58 Correct 248 ms 34468 KB Output is correct
59 Correct 268 ms 34636 KB Output is correct
60 Execution timed out 2061 ms 151084 KB Time limit exceeded
61 Halted 0 ms 0 KB -