oj.uz

답안 #757804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757804 2023-06-13T18:40:01 Z Andrei 서열 (APIO23_sequence) C++17
24 / 100
 2000 ms 47872 KB 
#include <bits/stdc++.h>

using namespace std;

int fr[500005];

vector <int> pos[500005];

/**
1 <= l <= pos[i][j]
pos[i][j+x-1] + 1 <= r <= n

0000000****111

abs(cnt[-1]-cnt[1]) <= x
abs(cnt[1]-cnt[-1]) <= x
abs(pref[r] - pref[l]) <= x

-x <= pref[r] - pref[l] <= x
pref[l] - pref[r] <= x sau pref[r] - pref[l] <= x

[a,b]
[c,d]

[a-x,b+x] trebuie sa se intersecteze cu [c,d]
*/

struct LazySegmentTree
{
    int n;
    int aux[500005];
    int minim[2000005];
    int maxim[2000005];
    int lazy[2000005];

    void build(int i,int x,int y)
    {
        lazy[i]=0;
        if(x==y)
            minim[i]=maxim[i]=aux[x];
        else
        {
            int mid=(x+y)/2;
            build(2*i,x,mid);
            build(2*i+1,mid+1,y);
            minim[i]=min(minim[2*i],minim[2*i+1]);
            maxim[i]=max(maxim[2*i],maxim[2*i+1]);
        }
    }

    void init(int _n)
    {
        n=_n;
        for(int i=0; i<=n; i++)
            aux[i]=i;
        build(1,0,n);
    }

    void propag(int i,int x,int y)
    {
        if(x!=y)
        {
            lazy[2*i]+=lazy[i];
            lazy[2*i+1]+=lazy[i];
            minim[2*i]+=lazy[i];
            maxim[2*i]+=lazy[i];
            minim[2*i+1]+=lazy[i];
            maxim[2*i+1]+=lazy[i];
            lazy[i]=0;
        }
    }

    void update(int i,int x,int y,int l,int r,int v)
    {
        propag(i,x,y);
        if(l<=x && y<=r)
        {
            lazy[i]+=v;
            minim[i]+=v;
            maxim[i]+=v;
            propag(i,x,y);
        }
        else
        {
            int mid=(x+y)/2;
            if(l<=mid)
                update(2*i,x,mid,l,r,v);
            if(r>mid)
                update(2*i+1,mid+1,y,l,r,v);

            minim[i]=min(minim[2*i],minim[2*i+1]);
            maxim[i]=max(maxim[2*i],maxim[2*i+1]);
        }
    }

    pair <int,int> query(int i,int x,int y,int l,int r)
    {
        propag(i,x,y);
        if(l<=x && y<=r)
            return make_pair(minim[i],maxim[i]);

        int mid=(x+y)/2;
        pair <int,int> aux=make_pair(n,-n);
        if(l<=mid)
            aux=query(2*i,x,mid,l,r);
        if(r>mid)
        {
            pair <int,int> temp;
            temp=query(2*i+1,mid+1,y,l,r);

            aux.first=min(aux.first,temp.first);
            aux.second=max(aux.second,temp.second);
        }
        return aux;
    }
} sgt;

bool ok(int n,int x)
{
    sgt.init(n);
    for(int i=1; i<=n; i++)
    {
        for(auto it:pos[i])
            sgt.update(1,0,n,it+1,n,-1);

        if(fr[i]>=x)
        {
            for(int j=0; j+x-1<fr[i]; j++)
            {
                pair <int,int> aux=sgt.query(1,0,n,0,pos[i][j]);
                int a=aux.first;
                int b=aux.second;

                aux=sgt.query(1,0,n,pos[i][j+x-1]+1,n);
                int c=aux.first;
                int d=aux.second;

                if(max(a-x,c)<=min(b+x,d))
                    return 1;
            }
        }
        for(auto it:pos[i])
            sgt.update(1,0,n,it+1,n,-1);
    }
    return 0;
}

int sequence(int n,vector <int> a)
{
    int mxfr=0;
    for(int i=0; i<n; i++)
    {
        fr[a[i]]++;
        mxfr=max(mxfr,fr[a[i]]);
        pos[a[i]].push_back(i);
    }

    int st=1,dr=mxfr,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(ok(n,mij)==1)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st-1;
}

/*
int n;

vector <int> a;

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
    cout<<sequence(n,a)<<"\n";
    return 0;
}
*/

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12016 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 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
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12016 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 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 8 ms 12116 KB Output is correct
14 Correct 8 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct
16 Correct 9 ms 12072 KB Output is correct
17 Correct 12 ms 12160 KB Output is correct
18 Correct 6 ms 12164 KB Output is correct
19 Correct 12 ms 12116 KB Output is correct
20 Correct 12 ms 12188 KB Output is correct
21 Incorrect 11 ms 12068 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 119 ms 42160 KB Output is correct
3 Correct 509 ms 42116 KB Output is correct
4 Execution timed out 2076 ms 32340 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 1360 ms 32480 KB Output is correct
3 Execution timed out 2084 ms 32344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 456 ms 47804 KB Output is correct
2 Correct 489 ms 47872 KB Output is correct
3 Correct 145 ms 47208 KB Output is correct
4 Correct 152 ms 47180 KB Output is correct
5 Correct 253 ms 43340 KB Output is correct
6 Correct 415 ms 43452 KB Output is correct
7 Correct 420 ms 42100 KB Output is correct
8 Correct 292 ms 41648 KB Output is correct

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12016 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 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 8 ms 12116 KB Output is correct
14 Correct 8 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct
16 Correct 9 ms 12072 KB Output is correct
17 Correct 12 ms 12160 KB Output is correct
18 Correct 6 ms 12164 KB Output is correct
19 Correct 12 ms 12116 KB Output is correct
20 Correct 12 ms 12188 KB Output is correct
21 Incorrect 11 ms 12068 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12016 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 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 8 ms 12116 KB Output is correct
14 Correct 8 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct
16 Correct 9 ms 12072 KB Output is correct
17 Correct 12 ms 12160 KB Output is correct
18 Correct 6 ms 12164 KB Output is correct
19 Correct 12 ms 12116 KB Output is correct
20 Correct 12 ms 12188 KB Output is correct
21 Incorrect 11 ms 12068 KB Output isn't correct
22 Halted 0 ms 0 KB -