답안 #919820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919820	2024-02-01T17:05:07 Z	JakobZorz	서열 (APIO23_sequence)	C++17	28 / 100	2000 ms	35408 KB

sequence

#include"sequence.h"
#include<vector>
#include<iostream>
using namespace std;

int n;
int arr2[500000];
int tree[500001];
vector<int>arr[500000];

int get_min(int l,int r){
    int res=1e9;
    for(int i=l;i<r;i++)
        res=min(res,tree[i]);
    return res;
}

int get_max(int l,int r){
    int res=-1e9;
    for(int i=l;i<r;i++)
        res=max(res,tree[i]);
    return res;
}

int sequence(int N,vector<int>A){
    n=N;
    for(int i=0;i<n;i++){
        arr[A[i]-1].push_back(i);
        arr2[i]=A[i]-1;
    }
    for(int i=0;i<=n;i++)
        tree[i]=-i;
    
    int res=1;
    for(int v=0;v<n;v++){
        for(int idx:arr[v])
            for(int i=idx+1;i<=n;i++)
                tree[i]++;
        
        int l=0;
        for(int r=0;r<(int)arr[v].size();r++){
            l=0;
            int min2=get_min(arr[v][r],n+1);
            int max2=get_max(arr[v][r],n+1);
            int min1=get_min(0,arr[v][l]+1);
            int max1=get_max(0,arr[v][l]+1);
            while(l<r&&(max1+r-l+1<min2||max2+r-l+1<min1)){
                l++;
                min1=get_min(0,arr[v][l]+1);
                max1=get_max(0,arr[v][l]+1);
            }
            res=max(res,r-l+1);
        }
        
        for(int idx:arr[v])
            for(int i=idx+1;i<=n;i++)
                tree[i]++;
    }
    
    return res;
}

Subtask #1

11.0 / 11.0

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

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	4 ms	14940 KB	Output is correct
4	Correct	4 ms	14936 KB	Output is correct
5	Correct	4 ms	14936 KB	Output is correct
6	Correct	4 ms	14936 KB	Output is correct
7	Correct	3 ms	14936 KB	Output is correct
8	Correct	4 ms	14940 KB	Output is correct
9	Correct	3 ms	14936 KB	Output is correct
10	Correct	4 ms	14936 KB	Output is correct
11	Correct	4 ms	14936 KB	Output is correct
12	Correct	3 ms	14936 KB	Output is correct
13	Correct	14 ms	14936 KB	Output is correct
14	Correct	15 ms	14936 KB	Output is correct
15	Correct	62 ms	14988 KB	Output is correct
16	Correct	63 ms	14936 KB	Output is correct
17	Correct	405 ms	15184 KB	Output is correct
18	Correct	14 ms	14936 KB	Output is correct
19	Correct	14 ms	14936 KB	Output is correct
20	Correct	14 ms	14936 KB	Output is correct
21	Correct	79 ms	14936 KB	Output is correct
22	Correct	67 ms	14940 KB	Output is correct

Subtask #3

0.0 / 7.0

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

Subtask #4

0.0 / 12.0

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

Subtask #5

0.0 / 13.0

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

Subtask #6

0.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	4 ms	14940 KB	Output is correct
4	Correct	4 ms	14936 KB	Output is correct
5	Correct	4 ms	14936 KB	Output is correct
6	Correct	4 ms	14936 KB	Output is correct
7	Correct	3 ms	14936 KB	Output is correct
8	Correct	4 ms	14940 KB	Output is correct
9	Correct	3 ms	14936 KB	Output is correct
10	Correct	4 ms	14936 KB	Output is correct
11	Correct	4 ms	14936 KB	Output is correct
12	Correct	3 ms	14936 KB	Output is correct
13	Correct	14 ms	14936 KB	Output is correct
14	Correct	15 ms	14936 KB	Output is correct
15	Correct	62 ms	14988 KB	Output is correct
16	Correct	63 ms	14936 KB	Output is correct
17	Correct	405 ms	15184 KB	Output is correct
18	Correct	14 ms	14936 KB	Output is correct
19	Correct	14 ms	14936 KB	Output is correct
20	Correct	14 ms	14936 KB	Output is correct
21	Correct	79 ms	14936 KB	Output is correct
22	Correct	67 ms	14940 KB	Output is correct
23	Execution timed out	2041 ms	17496 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	4 ms	14940 KB	Output is correct
4	Correct	4 ms	14936 KB	Output is correct
5	Correct	4 ms	14936 KB	Output is correct
6	Correct	4 ms	14936 KB	Output is correct
7	Correct	3 ms	14936 KB	Output is correct
8	Correct	4 ms	14940 KB	Output is correct
9	Correct	3 ms	14936 KB	Output is correct
10	Correct	4 ms	14936 KB	Output is correct
11	Correct	4 ms	14936 KB	Output is correct
12	Correct	3 ms	14936 KB	Output is correct
13	Correct	14 ms	14936 KB	Output is correct
14	Correct	15 ms	14936 KB	Output is correct
15	Correct	62 ms	14988 KB	Output is correct
16	Correct	63 ms	14936 KB	Output is correct
17	Correct	405 ms	15184 KB	Output is correct
18	Correct	14 ms	14936 KB	Output is correct
19	Correct	14 ms	14936 KB	Output is correct
20	Correct	14 ms	14936 KB	Output is correct
21	Correct	79 ms	14936 KB	Output is correct
22	Correct	67 ms	14940 KB	Output is correct
23	Execution timed out	2040 ms	29776 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-