Submission #763853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
763853	2023-06-23T01:03:39 Z	gg123_pe	Sequence (APIO23_sequence)	C++17	28 / 100	2000 ms	8144 KB

sequence

#include "sequence.h"
#include <bits/stdc++.h> 
using namespace std;

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 5e5 + 5; 

int n; 
int bit[N], c[N]; 

void upd(int x, int val){
    for(; x < N; x = (x|(x+1))) bit[x] += val; 
}
int sum(int x){
    int res = 0;
    for(; x >= 0; x = (x&(x+1)) - 1) res += bit[x];  
    return res; 
}
int get(int x){
    int l = 1, r = n; 
    while(l < r){
        int m = (l+r)>>1; 
        if(sum(m) >= x) r = m; 
        else l = m+1; 
    }
    return c[l]; 
}
int sequence(int Ni, vector<int> A) {
    n = Ni; 
    int ans = 1; 
    f(i,0,n){
        c[A[i]]++; 
        upd(A[i], 1); 

        f(j,i,n){
            int l = j - i + 1; 
            if(l&1){
                ans = max(ans, get((l+1)/2)); 
            }
            else{
                ans = max(ans, get(l/2)); 
                ans = max(ans, get(l/2 + 1)); 
            }
            if(j+1 < n) {
                c[A[j+1]]++; 
                upd(A[j+1], 1); 
            }
        }
        f(j,i,n){
            c[A[j]]--; 
            upd(A[j], -1); 
        }
    }
    return ans;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	268 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	268 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	255 ms	356 KB	Output is correct
14	Correct	268 ms	356 KB	Output is correct
15	Correct	204 ms	344 KB	Output is correct
16	Correct	203 ms	348 KB	Output is correct
17	Correct	217 ms	356 KB	Output is correct
18	Correct	289 ms	340 KB	Output is correct
19	Correct	265 ms	356 KB	Output is correct
20	Correct	211 ms	352 KB	Output is correct
21	Correct	259 ms	340 KB	Output is correct
22	Correct	252 ms	352 KB	Output is correct

Subtask #3

0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Execution timed out	2082 ms	8144 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Execution timed out	2069 ms	4176 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2083 ms	8012 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	268 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	255 ms	356 KB	Output is correct
14	Correct	268 ms	356 KB	Output is correct
15	Correct	204 ms	344 KB	Output is correct
16	Correct	203 ms	348 KB	Output is correct
17	Correct	217 ms	356 KB	Output is correct
18	Correct	289 ms	340 KB	Output is correct
19	Correct	265 ms	356 KB	Output is correct
20	Correct	211 ms	352 KB	Output is correct
21	Correct	259 ms	340 KB	Output is correct
22	Correct	252 ms	352 KB	Output is correct
23	Execution timed out	2069 ms	1492 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	268 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	255 ms	356 KB	Output is correct
14	Correct	268 ms	356 KB	Output is correct
15	Correct	204 ms	344 KB	Output is correct
16	Correct	203 ms	348 KB	Output is correct
17	Correct	217 ms	356 KB	Output is correct
18	Correct	289 ms	340 KB	Output is correct
19	Correct	265 ms	356 KB	Output is correct
20	Correct	211 ms	352 KB	Output is correct
21	Correct	259 ms	340 KB	Output is correct
22	Correct	252 ms	352 KB	Output is correct
23	Execution timed out	2082 ms	8144 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-