oj.uz

Submission #760166

# Submission time Handle Problem Language Result Execution time Memory
760166 2023-06-17T08:50:03 Z 8e7 Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 60200 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;
	vector<int> pv(N), sv(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);
			suf.modify(1, 0, N, 0, pos[i][j]+1, -1);
		}
		for (int j = 0;j < siz;j++) {
			pv[pos[i][j]] = pref.get(1, 0, N, pos[i][j]);
			sv[pos[i][j]] = suf.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]
			int sum = pv[r] - pref.get(1, 0, N, l);
			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 x = 0;x < siz;x++) {
			for (int y = x+ans;y < siz;y++) check(x, y);
		}
		
		/*
		int low = 1, up = siz+1;
		while (low < up - 1) {
			//int mid = (low + up) / 2;
			int mid = low+1;
			bool poss = 0;
			for (int x = 0;x <= siz - mid;x++) {
				if (check(x, x+mid-1)) {
					poss = 1;
					break;
				}
			}
			if (poss) low = mid;
			else up = mid;
		}
		*/
		
		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;
}

Compilation message

sequence.cpp: In lambda function:
sequence.cpp:111:8: warning: unused variable 'sum' [-Wunused-variable]
  111 |    int sum = pv[r] - pref.get(1, 0, N, l);
      |        ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 12096 KB Output is correct
3 Correct 6 ms 12044 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 12040 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12100 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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 12096 KB Output is correct
3 Correct 6 ms 12044 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 12040 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12100 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 8 ms 12244 KB Output is correct
14 Correct 8 ms 12260 KB Output is correct
15 Correct 11 ms 12244 KB Output is correct
16 Correct 11 ms 12240 KB Output is correct
17 Correct 33 ms 12216 KB Output is correct
18 Correct 8 ms 12244 KB Output is correct
19 Correct 8 ms 12248 KB Output is correct
20 Correct 8 ms 12252 KB Output is correct
21 Correct 15 ms 12244 KB Output is correct
22 Correct 14 ms 12256 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 631 ms 54476 KB Output is correct
3 Correct 682 ms 54468 KB Output is correct
4 Execution timed out 2071 ms 46532 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 12096 KB Output is correct
2 Correct 724 ms 46688 KB Output is correct
3 Execution timed out 2089 ms 46636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 60200 KB Output is correct
2 Correct 879 ms 60188 KB Output is correct
3 Correct 886 ms 59624 KB Output is correct
4 Correct 944 ms 59624 KB Output is correct
5 Incorrect 812 ms 56384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 12096 KB Output is correct
3 Correct 6 ms 12044 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 12040 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12100 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 8 ms 12244 KB Output is correct
14 Correct 8 ms 12260 KB Output is correct
15 Correct 11 ms 12244 KB Output is correct
16 Correct 11 ms 12240 KB Output is correct
17 Correct 33 ms 12216 KB Output is correct
18 Correct 8 ms 12244 KB Output is correct
19 Correct 8 ms 12248 KB Output is correct
20 Correct 8 ms 12252 KB Output is correct
21 Correct 15 ms 12244 KB Output is correct
22 Correct 14 ms 12256 KB Output is correct
23 Correct 168 ms 21092 KB Output is correct
24 Correct 137 ms 21088 KB Output is correct
25 Correct 134 ms 21100 KB Output is correct
26 Correct 1586 ms 20176 KB Output is correct
27 Correct 1478 ms 20184 KB Output is correct
28 Correct 1584 ms 20168 KB Output is correct
29 Execution timed out 2077 ms 19796 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 12096 KB Output is correct
3 Correct 6 ms 12044 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 12040 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12100 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 8 ms 12244 KB Output is correct
14 Correct 8 ms 12260 KB Output is correct
15 Correct 11 ms 12244 KB Output is correct
16 Correct 11 ms 12240 KB Output is correct
17 Correct 33 ms 12216 KB Output is correct
18 Correct 8 ms 12244 KB Output is correct
19 Correct 8 ms 12248 KB Output is correct
20 Correct 8 ms 12252 KB Output is correct
21 Correct 15 ms 12244 KB Output is correct
22 Correct 14 ms 12256 KB Output is correct
23 Correct 631 ms 54476 KB Output is correct
24 Correct 682 ms 54468 KB Output is correct
25 Execution timed out 2071 ms 46532 KB Time limit exceeded
26 Halted 0 ms 0 KB -