oj.uz

Submission #760112

# Submission time Handle Problem Language Result Execution time Memory
760112 2023-06-17T07:59:30 Z 8e7 Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 56284 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, suf;
vector<int> pos[maxn];
int sequence(int N, std::vector<int> A) {
	pref.type = 0, suf.type = 1;
	pref.N = suf.N = N;
	pref.init(1, 0, N), suf.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;

	
	for (int i = 1;i <= N;i++) {
		int siz = pos[i].size();
		for (int j = 0;j < siz;j++) {
			pref.modify(1, 0, N, pos[i][j], N, -1);
			suf.modify(1, 0, N, 0, pos[i][j]+1, -1);
		}

		//for (int j = 0;j < N;j++) cout << pref.get(1,0, N, j) << " ";
		//cout << endl;

		for (int j = 0;j < siz;j++) {
			int r = pos[i][j];
			int vj = pref.get(1, 0, N, r);

			auto check = [&] (int ind) {
				int l = pos[i][ind], cnt = j - ind + 1; //[l, r]
				int sum = vj - pref.get(1, 0, N, l), vind = suf.get(1, 0, N, l);
				pii pl = suf.query(1, 0, N, 0, l), pr = pref.query(1, 0, N, r+1, N);
				pii p = {sum + max(0, pl.ff-vind) + max(0, pr.ff-vj), sum + min(0, pl.ss-vind) + min(0, pr.ss-vj)};
				//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 ind = 0;ind < j;ind++) check(ind);	
		}
		for (int j = 0;j < siz;j++) {
			pref.modify(1, 0, N, pos[i][j], N, -1);
			suf.modify(1, 0, N, 0, pos[i][j]+1, -1);
		}

	}
 	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 12040 KB Output is correct
3 Correct 5 ms 12092 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12036 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12104 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12100 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 12040 KB Output is correct
3 Correct 5 ms 12092 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12036 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12104 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12100 KB Output is correct
13 Correct 8 ms 12244 KB Output is correct
14 Correct 9 ms 12116 KB Output is correct
15 Correct 19 ms 12116 KB Output is correct
16 Correct 18 ms 12220 KB Output is correct
17 Correct 100 ms 12204 KB Output is correct
18 Correct 7 ms 12244 KB Output is correct
19 Correct 19 ms 12116 KB Output is correct
20 Correct 27 ms 12116 KB Output is correct
21 Correct 23 ms 12116 KB Output is correct
22 Correct 20 ms 12116 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 680 ms 50624 KB Output is correct
3 Correct 708 ms 50560 KB Output is correct
4 Execution timed out 2069 ms 42692 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12040 KB Output is correct
2 Execution timed out 2059 ms 43760 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 56284 KB Output is correct
2 Correct 796 ms 56268 KB Output is correct
3 Correct 812 ms 55712 KB Output is correct
4 Correct 816 ms 55704 KB Output is correct
5 Correct 824 ms 52372 KB Output is correct
6 Correct 816 ms 52368 KB Output is correct
7 Correct 669 ms 51172 KB Output is correct
8 Correct 655 ms 50856 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 12040 KB Output is correct
3 Correct 5 ms 12092 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12036 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12104 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12100 KB Output is correct
13 Correct 8 ms 12244 KB Output is correct
14 Correct 9 ms 12116 KB Output is correct
15 Correct 19 ms 12116 KB Output is correct
16 Correct 18 ms 12220 KB Output is correct
17 Correct 100 ms 12204 KB Output is correct
18 Correct 7 ms 12244 KB Output is correct
19 Correct 19 ms 12116 KB Output is correct
20 Correct 27 ms 12116 KB Output is correct
21 Correct 23 ms 12116 KB Output is correct
22 Correct 20 ms 12116 KB Output is correct
23 Correct 159 ms 20464 KB Output is correct
24 Correct 162 ms 20464 KB Output is correct
25 Correct 170 ms 20472 KB Output is correct
26 Execution timed out 2086 ms 19444 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 5 ms 12040 KB Output is correct
3 Correct 5 ms 12092 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12036 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 12104 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12100 KB Output is correct
13 Correct 8 ms 12244 KB Output is correct
14 Correct 9 ms 12116 KB Output is correct
15 Correct 19 ms 12116 KB Output is correct
16 Correct 18 ms 12220 KB Output is correct
17 Correct 100 ms 12204 KB Output is correct
18 Correct 7 ms 12244 KB Output is correct
19 Correct 19 ms 12116 KB Output is correct
20 Correct 27 ms 12116 KB Output is correct
21 Correct 23 ms 12116 KB Output is correct
22 Correct 20 ms 12116 KB Output is correct
23 Correct 680 ms 50624 KB Output is correct
24 Correct 708 ms 50560 KB Output is correct
25 Execution timed out 2069 ms 42692 KB Time limit exceeded
26 Halted 0 ms 0 KB -