oj.uz

Submission #760174

# Submission time Handle Problem Language Result Execution time Memory
760174 2023-06-17T09:00:40 Z 8e7 Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 43940 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;
	
	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 < 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), pr = pref.query(1, 0, N, r, N);
			pl.ff = max(pl.ff, 0), pl.ss = min(pl.ss, 0);
			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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11944 KB Output is correct
3 Correct 6 ms 11988 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 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12064 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11944 KB Output is correct
3 Correct 6 ms 11988 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 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12064 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 7 ms 12060 KB Output is correct
15 Correct 11 ms 12148 KB Output is correct
16 Correct 10 ms 12056 KB Output is correct
17 Correct 33 ms 12116 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 14 ms 12148 KB Output is correct
22 Correct 13 ms 12116 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 290 ms 38192 KB Output is correct
3 Correct 297 ms 38212 KB Output is correct
4 Execution timed out 2089 ms 30268 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11944 KB Output is correct
2 Correct 332 ms 31344 KB Output is correct
3 Execution timed out 2076 ms 30492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 43940 KB Output is correct
2 Correct 408 ms 43820 KB Output is correct
3 Correct 428 ms 43452 KB Output is correct
4 Correct 433 ms 43340 KB Output is correct
5 Correct 400 ms 40076 KB Output is correct
6 Correct 451 ms 40024 KB Output is correct
7 Correct 346 ms 38948 KB Output is correct
8 Correct 369 ms 38512 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11944 KB Output is correct
3 Correct 6 ms 11988 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 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12064 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 7 ms 12060 KB Output is correct
15 Correct 11 ms 12148 KB Output is correct
16 Correct 10 ms 12056 KB Output is correct
17 Correct 33 ms 12116 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 14 ms 12148 KB Output is correct
22 Correct 13 ms 12116 KB Output is correct
23 Correct 67 ms 17352 KB Output is correct
24 Correct 67 ms 17368 KB Output is correct
25 Correct 73 ms 17348 KB Output is correct
26 Correct 1517 ms 16436 KB Output is correct
27 Correct 1522 ms 16432 KB Output is correct
28 Correct 1547 ms 16424 KB Output is correct
29 Execution timed out 2067 ms 16084 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11944 KB Output is correct
3 Correct 6 ms 11988 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 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12064 KB Output is correct
11 Correct 5 ms 11988 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 7 ms 12060 KB Output is correct
15 Correct 11 ms 12148 KB Output is correct
16 Correct 10 ms 12056 KB Output is correct
17 Correct 33 ms 12116 KB Output is correct
18 Correct 7 ms 12116 KB Output is correct
19 Correct 7 ms 12116 KB Output is correct
20 Correct 7 ms 12116 KB Output is correct
21 Correct 14 ms 12148 KB Output is correct
22 Correct 13 ms 12116 KB Output is correct
23 Correct 290 ms 38192 KB Output is correct
24 Correct 297 ms 38212 KB Output is correct
25 Execution timed out 2089 ms 30268 KB Time limit exceeded
26 Halted 0 ms 0 KB -