oj.uz

답안 #750423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750423 2023-05-29T13:43:16 Z penguin133 서열 (APIO23_sequence) C++17
82 / 100
 2000 ms 129468 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;
	}
	
	inline void prop(){
		if(!lazy)return;
		mx += lazy, mn += lazy;
		if(s != e)l->lazy += lazy, r->lazy += lazy;
		lazy = 0;
	}
	
	inline 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)};
		}
	}
	
	inline 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));
	}
	
	inline 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);
	}
	
	inline void prop(){
		if(!lazy)return;
		mx += lazy, mn += lazy;
		if(s != e)l->lazy += lazy, r->lazy += lazy;
		lazy = 0;
	}
	
	inline 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);
		}
	}
	inline 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));
	}
	
	inline 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];
 
inline 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;
}
 
inline 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

# 결과 실행 시간 메모리 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 6 ms 12168 KB Output is correct
5 Correct 7 ms 12164 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 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 6 ms 12168 KB Output is correct
5 Correct 7 ms 12164 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct
13 Correct 10 ms 12516 KB Output is correct
14 Correct 13 ms 12464 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 9 ms 12500 KB Output is correct
17 Correct 9 ms 12500 KB Output is correct
18 Correct 9 ms 12500 KB Output is correct
19 Correct 9 ms 12584 KB Output is correct
20 Correct 10 ms 12500 KB Output is correct
21 Correct 9 ms 12516 KB Output is correct
22 Correct 9 ms 12516 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 817 ms 123816 KB Output is correct
3 Correct 921 ms 123804 KB Output is correct
4 Correct 693 ms 119764 KB Output is correct
5 Correct 846 ms 122800 KB Output is correct
6 Correct 833 ms 122764 KB Output is correct
7 Correct 712 ms 116544 KB Output is correct
8 Correct 673 ms 116668 KB Output is correct
9 Correct 688 ms 122912 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 750 ms 126744 KB Output is correct
3 Correct 715 ms 122532 KB Output is correct
4 Correct 714 ms 122276 KB Output is correct
5 Correct 717 ms 126660 KB Output is correct
6 Correct 665 ms 125608 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1350 ms 129460 KB Output is correct
2 Correct 1340 ms 129468 KB Output is correct
3 Correct 1375 ms 129072 KB Output is correct
4 Correct 1377 ms 128960 KB Output is correct
5 Correct 1071 ms 125632 KB Output is correct
6 Correct 1088 ms 125624 KB Output is correct
7 Correct 778 ms 124468 KB Output is correct
8 Correct 796 ms 124112 KB Output is correct

Subtask #6
22.0 / 22.0

# 결과 실행 시간 메모리 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 6 ms 12168 KB Output is correct
5 Correct 7 ms 12164 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct
13 Correct 10 ms 12516 KB Output is correct
14 Correct 13 ms 12464 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 9 ms 12500 KB Output is correct
17 Correct 9 ms 12500 KB Output is correct
18 Correct 9 ms 12500 KB Output is correct
19 Correct 9 ms 12584 KB Output is correct
20 Correct 10 ms 12500 KB Output is correct
21 Correct 9 ms 12516 KB Output is correct
22 Correct 9 ms 12516 KB Output is correct
23 Correct 220 ms 30000 KB Output is correct
24 Correct 219 ms 30076 KB Output is correct
25 Correct 220 ms 30008 KB Output is correct
26 Correct 218 ms 29000 KB Output is correct
27 Correct 206 ms 29104 KB Output is correct
28 Correct 203 ms 29004 KB Output is correct
29 Correct 130 ms 29276 KB Output is correct
30 Correct 128 ms 29416 KB Output is correct
31 Correct 100 ms 31796 KB Output is correct
32 Correct 105 ms 30924 KB Output is correct
33 Correct 204 ms 30088 KB Output is correct
34 Correct 204 ms 30104 KB Output is correct
35 Correct 201 ms 30144 KB Output is correct
36 Correct 204 ms 30156 KB Output is correct
37 Correct 200 ms 30144 KB Output is correct
38 Correct 207 ms 30172 KB Output is correct

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 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 6 ms 12168 KB Output is correct
5 Correct 7 ms 12164 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct
13 Correct 10 ms 12516 KB Output is correct
14 Correct 13 ms 12464 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 9 ms 12500 KB Output is correct
17 Correct 9 ms 12500 KB Output is correct
18 Correct 9 ms 12500 KB Output is correct
19 Correct 9 ms 12584 KB Output is correct
20 Correct 10 ms 12500 KB Output is correct
21 Correct 9 ms 12516 KB Output is correct
22 Correct 9 ms 12516 KB Output is correct
23 Correct 817 ms 123816 KB Output is correct
24 Correct 921 ms 123804 KB Output is correct
25 Correct 693 ms 119764 KB Output is correct
26 Correct 846 ms 122800 KB Output is correct
27 Correct 833 ms 122764 KB Output is correct
28 Correct 712 ms 116544 KB Output is correct
29 Correct 673 ms 116668 KB Output is correct
30 Correct 688 ms 122912 KB Output is correct
31 Correct 750 ms 126744 KB Output is correct
32 Correct 715 ms 122532 KB Output is correct
33 Correct 714 ms 122276 KB Output is correct
34 Correct 717 ms 126660 KB Output is correct
35 Correct 665 ms 125608 KB Output is correct
36 Correct 1350 ms 129460 KB Output is correct
37 Correct 1340 ms 129468 KB Output is correct
38 Correct 1375 ms 129072 KB Output is correct
39 Correct 1377 ms 128960 KB Output is correct
40 Correct 1071 ms 125632 KB Output is correct
41 Correct 1088 ms 125624 KB Output is correct
42 Correct 778 ms 124468 KB Output is correct
43 Correct 796 ms 124112 KB Output is correct
44 Correct 220 ms 30000 KB Output is correct
45 Correct 219 ms 30076 KB Output is correct
46 Correct 220 ms 30008 KB Output is correct
47 Correct 218 ms 29000 KB Output is correct
48 Correct 206 ms 29104 KB Output is correct
49 Correct 203 ms 29004 KB Output is correct
50 Correct 130 ms 29276 KB Output is correct
51 Correct 128 ms 29416 KB Output is correct
52 Correct 100 ms 31796 KB Output is correct
53 Correct 105 ms 30924 KB Output is correct
54 Correct 204 ms 30088 KB Output is correct
55 Correct 204 ms 30104 KB Output is correct
56 Correct 201 ms 30144 KB Output is correct
57 Correct 204 ms 30156 KB Output is correct
58 Correct 200 ms 30144 KB Output is correct
59 Correct 207 ms 30172 KB Output is correct
60 Execution timed out 2004 ms 123800 KB Time limit exceeded
61 Halted 0 ms 0 KB -