oj.uz

Submission #919820

# Submission time Handle Problem Language Result Execution time Memory
919820 2024-02-01T17:05:07 Z JakobZorz Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 35408 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -