oj.uz

Submission #769606

# Submission time Handle Problem Language Result Execution time Memory
769606 2023-06-29T20:39:13 Z gg123_pe Sequence (APIO23_sequence) C++17
40 / 100
 302 ms 33512 KB 
#include "sequence.h"
#include <bits/stdc++.h> 
using namespace std;

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 5e5 + 5; 

int n; 
int bit[N], c[N];
vector <pair<int,int>> pos[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 subtask_2(vector <int> A){
    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;
}
int id(int pos){
    if(pos == 0) return 0; 
    if(c[1] >= pos) return 1; 
    if(c[1] + c[2] >= pos) return 2; 
    return 3; 
}
int res(vector <int> v){
    vector <int> aux, mini; 
    int len = v.size(), ans = 1; 
    f(i,0,len) {
        aux.push_back(v[i] - 2*i); 
        mini.push_back(v[i] - 2*i); 
    }
    fa(i,len-2,0) mini[i] = min(mini[i+1], mini[i]); 

    f(i,0,len-1){
        int ult = aux[i] + 1; // <= ult
        if(mini[i+1] > ult) continue; 
        int l = i+1, r = len-1; 
        while(l < r){
            int m = (l+r+1)>>1; 
            if(mini[m] > ult) r = m-1;  
            else l = m; 
        }
        ans = max(ans, l-i+1); 
    }
    return ans;     
}
int subtask_4(vector <int> A){
    for(int x: A) c[x]++; 
    int p1 = 0, p2 = 0; 
    if(n&1) p1 = (n+1)/2; 
    else p1 = n/2, p2 = p1 + 1; 

    if(id(p1) == 1 or id(p1) == 3) return c[id(p1)]; 
    if(id(p2) == 1 or id(p2) == 3) return c[id(p2)]; 
    if(c[2] > c[1] and c[2] > c[3]) return c[2]; 

    int ans = c[2];
    vector <int> P1, P3; 
    f(i,0,n){
        if(A[i] == 1) P1.push_back(i); 
        if(A[i] == 3) P3.push_back(i); 
    }
    ans = max(ans, res(P1)); 
    ans = max(ans, res(P3)); 
    return ans; 
}
bool is(int l, int r, int ty){
    if(l > r) return 0; 
    if(l != r) return 1; 
    return l%2 == ty; 
}
int subtask_3(vector <int> A){
    int ans = 0, id = 0; 
    while(id < n){
        int c = 0, ini = id+1, comp = A[id]; 
        while(A[id] == comp and id < n) c++, id++; 
        ans = max(ans, c);  
        pos[comp].push_back({ini, ini + c - 1}); 
    } 
    f(i,1,n+1){
        if(pos[i].size() != 2) continue; 
        int l1 = pos[i][0].first, r1 = pos[i][1].second; 
        int l2 = pos[i][1].first, r2 = pos[i][1].second; 
        int C = r1 - l1 + r2 - l2 + 2;
        int B = -(r1 + 1) + (l2 - 1) + 1;
        int A = n - C - B, ty = (B+C)%2; 

        bool fe = 0; 
        if(is(max(0, B-C), min(A, B+C), ty)) fe = 1; 
        if(is(max(0, B-C-1), min(A, B+C-1), 1-ty)) fe = 1; 
        if(fe) ans = max(ans, C);    
    }
    return ans; 
}
int sequence(int Ni, vector<int> A) {
    n = Ni; 

    if(n <= 2000) return subtask_2(A); 
    
    int maxi = 0; 
    for(int x: A) maxi = max(maxi, x); 

    if(maxi <= 3) return subtask_4(A); 
    return subtask_3(A); 
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 9 ms 12036 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12092 KB Output is correct
6 Correct 6 ms 12072 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12088 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 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 9 ms 12036 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12092 KB Output is correct
6 Correct 6 ms 12072 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12088 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 258 ms 12116 KB Output is correct
14 Correct 262 ms 12116 KB Output is correct
15 Correct 202 ms 12092 KB Output is correct
16 Correct 207 ms 12092 KB Output is correct
17 Correct 218 ms 12116 KB Output is correct
18 Correct 302 ms 12116 KB Output is correct
19 Correct 266 ms 12116 KB Output is correct
20 Correct 210 ms 12096 KB Output is correct
21 Correct 265 ms 12116 KB Output is correct
22 Correct 255 ms 12116 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Incorrect 62 ms 27704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 39 ms 17856 KB Output is correct
3 Correct 56 ms 22576 KB Output is correct
4 Correct 38 ms 17840 KB Output is correct
5 Correct 38 ms 17840 KB Output is correct
6 Correct 64 ms 24176 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 33512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 9 ms 12036 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12092 KB Output is correct
6 Correct 6 ms 12072 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12088 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 258 ms 12116 KB Output is correct
14 Correct 262 ms 12116 KB Output is correct
15 Correct 202 ms 12092 KB Output is correct
16 Correct 207 ms 12092 KB Output is correct
17 Correct 218 ms 12116 KB Output is correct
18 Correct 302 ms 12116 KB Output is correct
19 Correct 266 ms 12116 KB Output is correct
20 Correct 210 ms 12096 KB Output is correct
21 Correct 265 ms 12116 KB Output is correct
22 Correct 255 ms 12116 KB Output is correct
23 Incorrect 17 ms 14676 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 9 ms 12036 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12092 KB Output is correct
6 Correct 6 ms 12072 KB Output is correct
7 Correct 5 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 6 ms 12088 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 258 ms 12116 KB Output is correct
14 Correct 262 ms 12116 KB Output is correct
15 Correct 202 ms 12092 KB Output is correct
16 Correct 207 ms 12092 KB Output is correct
17 Correct 218 ms 12116 KB Output is correct
18 Correct 302 ms 12116 KB Output is correct
19 Correct 266 ms 12116 KB Output is correct
20 Correct 210 ms 12096 KB Output is correct
21 Correct 265 ms 12116 KB Output is correct
22 Correct 255 ms 12116 KB Output is correct
23 Incorrect 62 ms 27704 KB Output isn't correct
24 Halted 0 ms 0 KB -