oj.uz

Submission #749764

# Submission time Handle Problem Language Result Execution time Memory
749764 2023-05-28T12:55:41 Z penguin133 Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 129624 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 < 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 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 6 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 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 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 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 6 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 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 10 ms 12584 KB Output is correct
14 Correct 10 ms 12500 KB Output is correct
15 Correct 11 ms 12500 KB Output is correct
16 Correct 10 ms 12508 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 11 ms 12572 KB Output is correct
19 Correct 9 ms 12500 KB Output is correct
20 Correct 9 ms 12500 KB Output is correct
21 Correct 9 ms 12500 KB Output is correct
22 Correct 12 ms 12500 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 770 ms 123804 KB Output is correct
3 Correct 823 ms 123796 KB Output is correct
4 Correct 632 ms 119872 KB Output is correct
5 Correct 834 ms 122864 KB Output is correct
6 Correct 770 ms 122816 KB Output is correct
7 Correct 650 ms 116548 KB Output is correct
8 Correct 676 ms 116868 KB Output is correct
9 Correct 655 ms 122928 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 755 ms 126820 KB Output is correct
3 Correct 729 ms 122484 KB Output is correct
4 Correct 733 ms 122420 KB Output is correct
5 Correct 761 ms 126692 KB Output is correct
6 Correct 712 ms 125684 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 129532 KB Output is correct
2 Correct 1460 ms 129624 KB Output is correct
3 Correct 1446 ms 128960 KB Output is correct
4 Correct 1434 ms 129068 KB Output is correct
5 Correct 1154 ms 125612 KB Output is correct
6 Correct 1090 ms 125632 KB Output is correct
7 Correct 870 ms 124420 KB Output is correct
8 Correct 785 ms 124108 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 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 6 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 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 10 ms 12584 KB Output is correct
14 Correct 10 ms 12500 KB Output is correct
15 Correct 11 ms 12500 KB Output is correct
16 Correct 10 ms 12508 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 11 ms 12572 KB Output is correct
19 Correct 9 ms 12500 KB Output is correct
20 Correct 9 ms 12500 KB Output is correct
21 Correct 9 ms 12500 KB Output is correct
22 Correct 12 ms 12500 KB Output is correct
23 Correct 229 ms 30032 KB Output is correct
24 Correct 226 ms 29892 KB Output is correct
25 Correct 236 ms 30008 KB Output is correct
26 Correct 213 ms 29008 KB Output is correct
27 Correct 208 ms 29012 KB Output is correct
28 Correct 203 ms 29012 KB Output is correct
29 Correct 133 ms 29388 KB Output is correct
30 Correct 140 ms 29376 KB Output is correct
31 Correct 98 ms 31816 KB Output is correct
32 Correct 102 ms 30928 KB Output is correct
33 Correct 202 ms 30316 KB Output is correct
34 Correct 210 ms 30156 KB Output is correct
35 Correct 217 ms 30264 KB Output is correct
36 Correct 206 ms 30156 KB Output is correct
37 Correct 207 ms 30084 KB Output is correct
38 Correct 205 ms 30156 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 7 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 6 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 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 10 ms 12584 KB Output is correct
14 Correct 10 ms 12500 KB Output is correct
15 Correct 11 ms 12500 KB Output is correct
16 Correct 10 ms 12508 KB Output is correct
17 Correct 10 ms 12500 KB Output is correct
18 Correct 11 ms 12572 KB Output is correct
19 Correct 9 ms 12500 KB Output is correct
20 Correct 9 ms 12500 KB Output is correct
21 Correct 9 ms 12500 KB Output is correct
22 Correct 12 ms 12500 KB Output is correct
23 Correct 770 ms 123804 KB Output is correct
24 Correct 823 ms 123796 KB Output is correct
25 Correct 632 ms 119872 KB Output is correct
26 Correct 834 ms 122864 KB Output is correct
27 Correct 770 ms 122816 KB Output is correct
28 Correct 650 ms 116548 KB Output is correct
29 Correct 676 ms 116868 KB Output is correct
30 Correct 655 ms 122928 KB Output is correct
31 Correct 755 ms 126820 KB Output is correct
32 Correct 729 ms 122484 KB Output is correct
33 Correct 733 ms 122420 KB Output is correct
34 Correct 761 ms 126692 KB Output is correct
35 Correct 712 ms 125684 KB Output is correct
36 Correct 1450 ms 129532 KB Output is correct
37 Correct 1460 ms 129624 KB Output is correct
38 Correct 1446 ms 128960 KB Output is correct
39 Correct 1434 ms 129068 KB Output is correct
40 Correct 1154 ms 125612 KB Output is correct
41 Correct 1090 ms 125632 KB Output is correct
42 Correct 870 ms 124420 KB Output is correct
43 Correct 785 ms 124108 KB Output is correct
44 Correct 229 ms 30032 KB Output is correct
45 Correct 226 ms 29892 KB Output is correct
46 Correct 236 ms 30008 KB Output is correct
47 Correct 213 ms 29008 KB Output is correct
48 Correct 208 ms 29012 KB Output is correct
49 Correct 203 ms 29012 KB Output is correct
50 Correct 133 ms 29388 KB Output is correct
51 Correct 140 ms 29376 KB Output is correct
52 Correct 98 ms 31816 KB Output is correct
53 Correct 102 ms 30928 KB Output is correct
54 Correct 202 ms 30316 KB Output is correct
55 Correct 210 ms 30156 KB Output is correct
56 Correct 217 ms 30264 KB Output is correct
57 Correct 206 ms 30156 KB Output is correct
58 Correct 207 ms 30084 KB Output is correct
59 Correct 205 ms 30156 KB Output is correct
60 Execution timed out 2049 ms 123800 KB Time limit exceeded
61 Halted 0 ms 0 KB -