oj.uz

Submission #852242

# Submission time Handle Problem Language Result Execution time Memory
852242 2023-09-21T13:28:17 Z sunwukong123 Sequence (APIO23_sequence) C++17
50 / 100
 2000 ms 83792 KB 
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 500005;

const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
int A[MAXN];
vector<int> V[MAXN];
struct node {
    int s,e,m,lazy,mn,mx;
    node *l, *r;
    node (int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        lazy=0;
        
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
            mn=min(l->mn,r->mn);
            mx=max(l->mx,r->mx);
        } else{
            mn=-_s;mx=-_s;
        }
    }

    void value(){
        if(lazy==0)return;
        if(s==e){
            mn+=lazy;
            mx+=lazy;
            lazy=0;
            return;
        }
        l->lazy+=lazy;
        r->lazy+=lazy;
        mn+=lazy;
        mx+=lazy;
        lazy=0;
        return;
    }
    void update(int x, int y, int nval){
        value();
        if(s==x&&e==y){
            lazy+=nval;
            return;
        }
        if(x>m)r->update(x,y,nval);
        else if(y<=m)l->update(x,y,nval);
        else l->update(x,m,nval),r->update(m+1,y,nval);
        l->value();r->value();
        mn=min(l->mn,r->mn);
        mx=max(l->mx,r->mx);
    }
    int query_min(int x, int y){
        value();
        if(s==x&&e==y)return mn;
        if(x>m)return r->query_min(x,y);
        else if(y<=m)return l->query_min(x,y);
        else return min(l->query_min(x,m),r->query_min(m+1,y));
    }
    int query_max(int x, int y){
        value();
        if(s==x&&e==y)return mx;
        if(x>m)return r->query_max(x,y);
        else if(y<=m)return l->query_max(x,y);
        else return max(l->query_max(x,m),r->query_max(m+1,y));
    }
    ~node(){
        if(s!=e){
            delete l;
            delete r;
        }
        
    }
}*seg;
bool check(int S){
    seg=new node(0,n);
    for(int v=1;v<=n;v++){

        //pretend everything 0 is a -1
        vector<int> idxes;
        for(int i=0;i+S-1<(int)V[v].size();i++){
            int st=V[v][i];
            int en=V[v][i+S-1];

            int Lval=seg->query_max(0,st-1);
            int Rval=seg->query_min(en,n);

            if(Rval<=Lval){
                idxes.push_back(i);
            }
        }

        for(auto x:V[v]){

            seg->update(x,n,2);
        }

        // pretend every 0 is a +1

        for(auto i:idxes){
            int st=V[v][i];
            int en=V[v][i+S-1];
            int Lval=seg->query_min(0,st-1);
            int Rval=seg->query_max(en,n);

            if(Rval>=Lval){
                delete seg;
                return 1;
            }
        }

    }
    delete seg;
    return 0;
}

int sequence(int N, std::vector<int> vec) {
    n=N;
    for(int i=1;i<=n;i++){
        A[i]=vec[i-1];
    }
    for(int i=1;i<=n;i++){
        V[A[i]].push_back(i);
    }

    int lo=0,hi=n+1;
    while(lo<hi-1){
        int mid=(lo+hi)/2;
        if(check(mid))lo=mid;
        else hi=mid;
    }
    return lo;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12916 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 3 ms 12888 KB Output is correct
13 Correct 7 ms 13144 KB Output is correct
14 Correct 9 ms 13168 KB Output is correct
15 Correct 7 ms 12888 KB Output is correct
16 Correct 7 ms 12888 KB Output is correct
17 Correct 6 ms 12888 KB Output is correct
18 Correct 6 ms 13144 KB Output is correct
19 Correct 7 ms 13152 KB Output is correct
20 Correct 7 ms 13144 KB Output is correct
21 Correct 7 ms 13144 KB Output is correct
22 Correct 7 ms 13152 KB Output is correct

Subtask #3
0.0 / 7.0

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

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12916 KB Output is correct
2 Execution timed out 2023 ms 68092 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 2027 ms 83792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12916 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 3 ms 12888 KB Output is correct
13 Correct 7 ms 13144 KB Output is correct
14 Correct 9 ms 13168 KB Output is correct
15 Correct 7 ms 12888 KB Output is correct
16 Correct 7 ms 12888 KB Output is correct
17 Correct 6 ms 12888 KB Output is correct
18 Correct 6 ms 13144 KB Output is correct
19 Correct 7 ms 13152 KB Output is correct
20 Correct 7 ms 13144 KB Output is correct
21 Correct 7 ms 13144 KB Output is correct
22 Correct 7 ms 13152 KB Output is correct
23 Correct 628 ms 22864 KB Output is correct
24 Correct 648 ms 23100 KB Output is correct
25 Correct 566 ms 22872 KB Output is correct
26 Correct 376 ms 21920 KB Output is correct
27 Correct 400 ms 21848 KB Output is correct
28 Correct 464 ms 21968 KB Output is correct
29 Correct 265 ms 21600 KB Output is correct
30 Correct 283 ms 21640 KB Output is correct
31 Correct 295 ms 22516 KB Output is correct
32 Correct 289 ms 23888 KB Output is correct
33 Correct 448 ms 22976 KB Output is correct
34 Correct 509 ms 22948 KB Output is correct
35 Correct 487 ms 22892 KB Output is correct
36 Correct 510 ms 22988 KB Output is correct
37 Correct 475 ms 22872 KB Output is correct
38 Correct 558 ms 22932 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12916 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 3 ms 12888 KB Output is correct
13 Correct 7 ms 13144 KB Output is correct
14 Correct 9 ms 13168 KB Output is correct
15 Correct 7 ms 12888 KB Output is correct
16 Correct 7 ms 12888 KB Output is correct
17 Correct 6 ms 12888 KB Output is correct
18 Correct 6 ms 13144 KB Output is correct
19 Correct 7 ms 13152 KB Output is correct
20 Correct 7 ms 13144 KB Output is correct
21 Correct 7 ms 13144 KB Output is correct
22 Correct 7 ms 13152 KB Output is correct
23 Execution timed out 2049 ms 78160 KB Time limit exceeded
24 Halted 0 ms 0 KB -