답안 #759662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759662	2023-06-16T14:17:25 Z	IvanJ	서열 (APIO23_sequence)	C++17	28 / 100	2000 ms	18648 KB

sequence

#include "sequence.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

struct tree {
	int pot;
	vector<int> T;
	void init(int N) {
		pot = 1;
		while(pot < N) pot <<= 1;
		for(int i = 0;i < pot * 2;i++) T.pb(0);
	}
	
	void add(int x) {
		x += pot;
		T[x]++;
		x >>= 1;
		while(x > 0) T[x] = T[x * 2] + T[x * 2 + 1], x >>= 1;
	}
	
	int find(int x, int lo, int hi, int target) {
		if(lo == hi) return lo;
		int mid = (lo + hi) / 2;
		if(T[x * 2] >= target) 
			return find(x * 2, lo, mid, target);
		else 
			return find(x * 2 + 1, mid + 1, hi, target - T[x * 2]);
	}
	
	ii medians() {
		int K = T[1];
		int p1 = (K - 1) / 2 + 1;
		int p2 = K / 2 + 1;
		return {find(1, 0, pot - 1, p1), find(1, 0, pot - 1, p2)};
	}
};

int sequence(int N, vector<int> A) {
	tree T;
	T.init(N);
	for(int i = 0;i < N;i++) A[i]--;
	int ans = 0;
	for(int i = 0;i < N;i++) {
		vector<int> cnt(N, 0);
		tree T;
		T.init(N);
		for(int j = i;j < N;j++) {
			cnt[A[j]]++;
			T.add(A[j]);
			ii p = T.medians();
			ans = max(ans, max(cnt[p.x], cnt[p.y]));
		}
	}
	return ans;
}

Subtask #1

11.0 / 11.0

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

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	136 ms	344 KB	Output is correct
14	Correct	129 ms	340 KB	Output is correct
15	Correct	127 ms	340 KB	Output is correct
16	Correct	109 ms	344 KB	Output is correct
17	Correct	105 ms	344 KB	Output is correct
18	Correct	191 ms	348 KB	Output is correct
19	Correct	133 ms	352 KB	Output is correct
20	Correct	115 ms	340 KB	Output is correct
21	Correct	131 ms	344 KB	Output is correct
22	Correct	132 ms	352 KB	Output is correct

Subtask #3

0.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Execution timed out	2068 ms	18500 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Execution timed out	2060 ms	18648 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2050 ms	18640 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	136 ms	344 KB	Output is correct
14	Correct	129 ms	340 KB	Output is correct
15	Correct	127 ms	340 KB	Output is correct
16	Correct	109 ms	344 KB	Output is correct
17	Correct	105 ms	344 KB	Output is correct
18	Correct	191 ms	348 KB	Output is correct
19	Correct	133 ms	352 KB	Output is correct
20	Correct	115 ms	340 KB	Output is correct
21	Correct	131 ms	344 KB	Output is correct
22	Correct	132 ms	352 KB	Output is correct
23	Execution timed out	2062 ms	4500 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	136 ms	344 KB	Output is correct
14	Correct	129 ms	340 KB	Output is correct
15	Correct	127 ms	340 KB	Output is correct
16	Correct	109 ms	344 KB	Output is correct
17	Correct	105 ms	344 KB	Output is correct
18	Correct	191 ms	348 KB	Output is correct
19	Correct	133 ms	352 KB	Output is correct
20	Correct	115 ms	340 KB	Output is correct
21	Correct	131 ms	344 KB	Output is correct
22	Correct	132 ms	352 KB	Output is correct
23	Execution timed out	2068 ms	18500 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-