oj.uz

Submission #852249

# Submission time Handle Problem Language Result Execution time Memory
852249 2023-09-21T13:38:20 Z sunwukong123 Sequence (APIO23_sequence) C++17
100 / 100
 1234 ms 91812 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;
int Q1[MAXN],Q2[MAXN],Q3[MAXN],Q4[MAXN];
bool check(int S){
    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=Q1[st];//seg->query_max(0,st-1);
            int Rval=Q2[en];//seg->query_min(en,n);

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

        // pretend every 0 is a +1

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

            if(Rval>=Lval){

                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);
    }

    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<(int)V[v].size();i++){
            int idx=V[v][i];
            Q1[idx]=seg->query_max(0,idx-1);
            Q2[idx]=seg->query_min(idx,n);
        }

        for(auto x:V[v]){
            seg->update(x,n,2);
        }

        // pretend every 0 is a +1

        for(int i=0;i<(int)V[v].size();i++){
            int idx=V[v][i];
            Q3[idx]=seg->query_min(0,idx-1);
            Q4[idx]=seg->query_max(idx,n);
        }
    }

    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 4 ms 20828 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 5 ms 21084 KB Output is correct
14 Correct 5 ms 21084 KB Output is correct
15 Correct 5 ms 21084 KB Output is correct
16 Correct 5 ms 21084 KB Output is correct
17 Correct 5 ms 21084 KB Output is correct
18 Correct 5 ms 21240 KB Output is correct
19 Correct 5 ms 21084 KB Output is correct
20 Correct 5 ms 21084 KB Output is correct
21 Correct 5 ms 21084 KB Output is correct
22 Correct 5 ms 21084 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 408 ms 82652 KB Output is correct
3 Correct 404 ms 86032 KB Output is correct
4 Correct 340 ms 76044 KB Output is correct
5 Correct 400 ms 84992 KB Output is correct
6 Correct 397 ms 85624 KB Output is correct
7 Correct 338 ms 76628 KB Output is correct
8 Correct 344 ms 76920 KB Output is correct
9 Correct 329 ms 76160 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 374 ms 74908 KB Output is correct
3 Correct 379 ms 76056 KB Output is correct
4 Correct 393 ms 76052 KB Output is correct
5 Correct 394 ms 75944 KB Output is correct
6 Correct 398 ms 76996 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 88736 KB Output is correct
2 Correct 749 ms 91732 KB Output is correct
3 Correct 833 ms 91108 KB Output is correct
4 Correct 797 ms 91128 KB Output is correct
5 Correct 652 ms 87784 KB Output is correct
6 Correct 640 ms 87788 KB Output is correct
7 Correct 424 ms 86620 KB Output is correct
8 Correct 425 ms 86308 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 5 ms 21084 KB Output is correct
14 Correct 5 ms 21084 KB Output is correct
15 Correct 5 ms 21084 KB Output is correct
16 Correct 5 ms 21084 KB Output is correct
17 Correct 5 ms 21084 KB Output is correct
18 Correct 5 ms 21240 KB Output is correct
19 Correct 5 ms 21084 KB Output is correct
20 Correct 5 ms 21084 KB Output is correct
21 Correct 5 ms 21084 KB Output is correct
22 Correct 5 ms 21084 KB Output is correct
23 Correct 120 ms 30852 KB Output is correct
24 Correct 108 ms 30812 KB Output is correct
25 Correct 118 ms 30852 KB Output is correct
26 Correct 93 ms 29840 KB Output is correct
27 Correct 105 ms 29844 KB Output is correct
28 Correct 98 ms 29840 KB Output is correct
29 Correct 71 ms 29520 KB Output is correct
30 Correct 73 ms 29592 KB Output is correct
31 Correct 56 ms 29932 KB Output is correct
32 Correct 63 ms 31576 KB Output is correct
33 Correct 114 ms 30556 KB Output is correct
34 Correct 108 ms 30940 KB Output is correct
35 Correct 134 ms 30576 KB Output is correct
36 Correct 113 ms 30620 KB Output is correct
37 Correct 121 ms 30640 KB Output is correct
38 Correct 140 ms 30680 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 5 ms 21084 KB Output is correct
14 Correct 5 ms 21084 KB Output is correct
15 Correct 5 ms 21084 KB Output is correct
16 Correct 5 ms 21084 KB Output is correct
17 Correct 5 ms 21084 KB Output is correct
18 Correct 5 ms 21240 KB Output is correct
19 Correct 5 ms 21084 KB Output is correct
20 Correct 5 ms 21084 KB Output is correct
21 Correct 5 ms 21084 KB Output is correct
22 Correct 5 ms 21084 KB Output is correct
23 Correct 408 ms 82652 KB Output is correct
24 Correct 404 ms 86032 KB Output is correct
25 Correct 340 ms 76044 KB Output is correct
26 Correct 400 ms 84992 KB Output is correct
27 Correct 397 ms 85624 KB Output is correct
28 Correct 338 ms 76628 KB Output is correct
29 Correct 344 ms 76920 KB Output is correct
30 Correct 329 ms 76160 KB Output is correct
31 Correct 374 ms 74908 KB Output is correct
32 Correct 379 ms 76056 KB Output is correct
33 Correct 393 ms 76052 KB Output is correct
34 Correct 394 ms 75944 KB Output is correct
35 Correct 398 ms 76996 KB Output is correct
36 Correct 807 ms 88736 KB Output is correct
37 Correct 749 ms 91732 KB Output is correct
38 Correct 833 ms 91108 KB Output is correct
39 Correct 797 ms 91128 KB Output is correct
40 Correct 652 ms 87784 KB Output is correct
41 Correct 640 ms 87788 KB Output is correct
42 Correct 424 ms 86620 KB Output is correct
43 Correct 425 ms 86308 KB Output is correct
44 Correct 120 ms 30852 KB Output is correct
45 Correct 108 ms 30812 KB Output is correct
46 Correct 118 ms 30852 KB Output is correct
47 Correct 93 ms 29840 KB Output is correct
48 Correct 105 ms 29844 KB Output is correct
49 Correct 98 ms 29840 KB Output is correct
50 Correct 71 ms 29520 KB Output is correct
51 Correct 73 ms 29592 KB Output is correct
52 Correct 56 ms 29932 KB Output is correct
53 Correct 63 ms 31576 KB Output is correct
54 Correct 114 ms 30556 KB Output is correct
55 Correct 108 ms 30940 KB Output is correct
56 Correct 134 ms 30576 KB Output is correct
57 Correct 113 ms 30620 KB Output is correct
58 Correct 121 ms 30640 KB Output is correct
59 Correct 140 ms 30680 KB Output is correct
60 Correct 1084 ms 86076 KB Output is correct
61 Correct 1234 ms 86100 KB Output is correct
62 Correct 1155 ms 86084 KB Output is correct
63 Correct 919 ms 77588 KB Output is correct
64 Correct 945 ms 77596 KB Output is correct
65 Correct 991 ms 77588 KB Output is correct
66 Correct 486 ms 76056 KB Output is correct
67 Correct 505 ms 76280 KB Output is correct
68 Correct 358 ms 80020 KB Output is correct
69 Correct 363 ms 91812 KB Output is correct
70 Correct 959 ms 85160 KB Output is correct
71 Correct 936 ms 84980 KB Output is correct
72 Correct 895 ms 84688 KB Output is correct
73 Correct 982 ms 85604 KB Output is correct
74 Correct 933 ms 85328 KB Output is correct
75 Correct 919 ms 84832 KB Output is correct