oj.uz

답안 #760169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760169 2023-06-17T08:54:08 Z 8e7 서열 (APIO23_sequence) C++17
28 / 100
 2000 ms 45908 KB 
#include "sequence.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 500005
#define ff first
#define ss second
#define pii pair<int, int>
const int inf = 1<<30;
struct segtree{
	int ma[4*maxn], mi[4*maxn], tag[4*maxn];
	int type, N;
	void init(int cur, int l, int r) {
		if (r <= l) return;
		tag[cur] = 0;
		if (r - l == 1) {
			ma[cur] = mi[cur] = type ? N - l : l+1;
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
		ma[cur] = max(ma[cur*2], ma[cur*2+1]);
		mi[cur] = min(mi[cur*2], mi[cur*2+1]);
	}
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		ma[cur] += tag[cur];
		mi[cur] += tag[cur];
		if (r - l > 1) {
			tag[cur*2] += tag[cur];
			tag[cur*2+1] += tag[cur];
		}
		tag[cur] = 0;
	}
	void modify(int cur, int l, int r, int ql, int qr, int v) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += v;
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v);
		modify(cur*2+1, m, r, ql, qr, v);
		push(cur*2, l, m), push(cur*2+1, m, r);
		ma[cur] = max(ma[cur*2], ma[cur*2+1]);
		mi[cur] = min(mi[cur*2], mi[cur*2+1]);
	}
	pii query(int cur, int l, int r, int ql, int qr) { //(ma, mi)
		if (r <= l || ql >= r || qr <= l) return {-inf, inf};
		push(cur, l, r);
		if (ql <= l && qr >= r) return make_pair(ma[cur], mi[cur]);
		int m = (l + r) / 2;
		pii pl = query(cur*2, l, m, ql, qr), pr = query(cur*2+1, m, r, ql, qr);	
		pl.ff = max(pl.ff, pr.ff);
		pl.ss = min(pl.ss, pr.ss);
		return pl;
	}
	int get(int cur, int l, int r, int x) { 
		if (r <= l) return 0;
		push(cur, l, r);
		if (r - l == 1) return ma[cur];
		int m = (l + r) / 2;
		if (x < m) return get(cur*2, l, m, x);
		else return get(cur*2+1, m, r, x);
	}
} pref;
vector<int> pos[maxn];
int sequence(int N, std::vector<int> A) {
	pref.type = 0;
	pref.N = N;
	pref.init(1, 0, N);
	for (int i = 0;i < N;i++) {
		pos[A[i]].push_back(i);
	}

	//for (int j = 0;j < N;j++) cout << pref.get(1,0, N, j) << " ";
	//cout << endl;
	
	
	int ans = 1;
	vector<int> pv(N);
	
	for (int i = 1;i <= N;i++) {
		int siz = pos[i].size();
		if (siz == 0) continue;
		for (int j = 0;j < siz;j++) {
			pref.modify(1, 0, N, pos[i][j], N, -1);
		}
		for (int j = 0;j < siz;j++) {
			pv[pos[i][j]] = pref.get(1, 0, N, pos[i][j]);
		}
		//for (int j = 0;j < N;j++) cout << pref.get(1,0, N, j) << " ";
		//cout << endl;
		auto check = [&] (int ind, int j) {
			int l = pos[i][ind], r = pos[i][j], cnt = j - ind + 1; //[l, r]
			pii pl = pref.query(1, 0, N, 0, l+1), pr = pref.query(1, 0, N, r, N);
			pii p = {-pl.ss + pr.ff,  pr.ss - pl.ff};
			//debug(ind, j, p.ss, p.ff);
			if (max(p.ss, -cnt) <= min(p.ff, cnt)) {
				ans = max(ans, j - ind + 1);
				return true;
			} else {
				return false;
			}
		};
		for (int val = ans;val < siz;val++) {
			for (int x = 0;x + val < siz;x++) {
				if (check(x, x+val)) break;
			}
		}
		
		for (int j = 0;j < siz;j++) {
			pref.modify(1, 0, N, pos[i][j], N, -1);
		}

	}
 	return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 6 ms 12044 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 6 ms 12044 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 11 ms 12116 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 40 ms 12144 KB Output is correct
18 Correct 9 ms 12188 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 15 ms 12172 KB Output is correct
22 Correct 13 ms 12116 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 314 ms 40176 KB Output is correct
3 Correct 327 ms 40268 KB Output is correct
4 Execution timed out 2093 ms 32308 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 365 ms 32376 KB Output is correct
3 Execution timed out 2076 ms 32292 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 45908 KB Output is correct
2 Correct 469 ms 45888 KB Output is correct
3 Correct 451 ms 45320 KB Output is correct
4 Correct 457 ms 45332 KB Output is correct
5 Incorrect 417 ms 42060 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 6 ms 12044 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 11 ms 12116 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 40 ms 12144 KB Output is correct
18 Correct 9 ms 12188 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 15 ms 12172 KB Output is correct
22 Correct 13 ms 12116 KB Output is correct
23 Correct 70 ms 17620 KB Output is correct
24 Correct 72 ms 17656 KB Output is correct
25 Correct 70 ms 17668 KB Output is correct
26 Correct 1506 ms 16736 KB Output is correct
27 Correct 1506 ms 16752 KB Output is correct
28 Correct 1544 ms 16756 KB Output is correct
29 Execution timed out 2073 ms 16468 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 6 ms 12044 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 11 ms 12116 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 40 ms 12144 KB Output is correct
18 Correct 9 ms 12188 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 15 ms 12172 KB Output is correct
22 Correct 13 ms 12116 KB Output is correct
23 Correct 314 ms 40176 KB Output is correct
24 Correct 327 ms 40268 KB Output is correct
25 Execution timed out 2093 ms 32308 KB Time limit exceeded
26 Halted 0 ms 0 KB -