oj.uz

Submission #787862

# Submission time Handle Problem Language Result Execution time Memory
787862 2023-07-19T13:37:53 Z andrei_boaca Radio Towers (IOI22_towers) C++17
18 / 100
 962 ms 30060 KB 
#include "towers.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
typedef pair<int,int> pii;
int n;
int v[100005];
int rmq[22][100005];
int loga[100005];
int lft[100005],rgt[100005];
int tolft[100005];
int getmax(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
int getR(int poz,int delta)
{
    int st=poz+2;
    int dr=n;
    int ans=1e9;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(getmax(poz+1,mij-1)-delta>=v[poz])
        {
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return ans;
}
int getL(int poz,int delta)
{
    int st=1;
    int dr=poz-2;
    int ans=0;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(getmax(mij+1,poz-1)-delta>=v[poz])
        {
            ans=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return ans;
}
int bin[22][100005];
int rmin[22][100005];
int uplft[100005];
int getmin(int l,int r)
{
    int lg=loga[r-l+1];
    return min(rmin[lg][l],rmin[lg][r-(1<<lg)+1]);
}
bool subtask1=1;
int magic;
void init(int N, std::vector<int> H) {
    n=N;
    for(int i=1;i<=n;i++)
    {
        v[i]=H[i-1];
        for(int j=0;j<=20;j++)
            if((1<<j)<=i)
                loga[i]=j;
    }
    bool cresc=1;
    subtask1=1;
    magic=0;
    for(int i=1;i<=n;i++)
    {
        if(v[i]==v[i-1])
        {
            subtask1=0;
            break;
        }
        if(cresc==1)
        {
            if(v[i]<v[i-1])
            {
                cresc=0;
                continue;
            }
        }
        else
        {
            if(v[i]>v[i-1])
            {
                subtask1=0;
                break;
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        rmq[0][i]=v[i];
        rmin[0][i]=v[i];
        for(int j=1;j<=20;j++)
        {
            rmq[j][i]=rmq[j-1][i];
            rmin[j][i]=rmin[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=n)
            {
                rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
                rmin[j][i]=min(rmin[j][i],rmin[j-1][poz]);
            }
        }
    }
    if(subtask1==1)
    {
        int maxim=getmax(1,n);
        for(int i=1;i<=n;i++)
            if(v[i]==maxim)
            {
                magic=i;
                break;
            }
    }
    for(int i=1;i<=n;i++)
    {
        if(v[i]<=v[i-1])
            tolft[i]=i;
        else
            tolft[i]=tolft[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        uplft[i]=i;
        if(v[i-1]>=v[i])
            uplft[i]=uplft[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        lft[i]=getL(i,1)+1;
        lft[i]=uplft[lft[i]]-1;
        lft[i]=tolft[lft[i]];
        bin[0][i]=lft[i];
        for(int j=1;j<=20;j++)
            bin[j][i]=bin[j-1][bin[j-1][i]];
    }
}
int dp[100005];
int arb[4*100005];
vector<int> add[100005];
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(nod*2,st,mij,poz,val);
    else
        update(nod*2+1,mij+1,dr,poz,val);
    arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a,int b)
{
    if(st>=a&&dr<=b)
        return arb[nod];
    int mij=(st+dr)/2;
    int rez=0;
    if(a<=mij)
        rez=max(rez,query(nod*2,st,mij,a,b));
    if(b>mij)
        rez=max(rez,query(nod*2+1,mij+1,dr,a,b));
    return rez;
}
int max_towers(int L, int R, int D)
{
    L++;
    R++;
    if(subtask1==1)
    {
        if(L<magic&&R>magic)
        {
            if(v[magic]-D>=max(v[L],v[R]))
                return 2;
            return 1;
        }
        return 1;
    }
    if(D==1)
    {
        int rez=1;
        int nod=tolft[R];
        for(int j=20;j>=0;j--)
            if(bin[j][nod]>=L)
            {
                rez+=(1<<j);
                nod=bin[j][nod];
            }
        int l=getL(nod,D)+1;
        l=uplft[l];
        int st=L;
        int dr=l-1;
        if(st<=dr)
        {
            if(getmin(st,dr)<v[l])
                rez++;
        }
        return rez;
    }
    for(int i=1;i<=4*n;i++)
        arb[i]=0;
    for(int i=1;i<=n;i++)
        add[i].clear();
    int ans=1;
    for(int i=L;i<=R;i++)
    {
        for(int j:add[i])
            update(1,1,n,j,dp[j]);
        dp[i]=1;
        int r=getR(i,D);
        int l=getL(i,D);
        if(l>=L)
            dp[i]=1+query(1,1,n,L,l);
        ans=max(ans,dp[i]);
        if(r<=R)
            add[r].push_back(i);
    }
    if(ans>1)
    {
        assert(dp[tolft[R]]==ans);
    }
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 19272 KB Output is correct
2 Correct 769 ms 30024 KB Output is correct
3 Correct 791 ms 30056 KB Output is correct
4 Correct 709 ms 30060 KB Output is correct
5 Correct 811 ms 30036 KB Output is correct
6 Correct 764 ms 30048 KB Output is correct
7 Correct 715 ms 29976 KB Output is correct
8 Correct 1 ms 2896 KB Output is correct
9 Correct 2 ms 3408 KB Output is correct
10 Correct 2 ms 3408 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3024 KB Output is correct
2 Correct 2 ms 3536 KB Output is correct
3 Runtime error 7 ms 6992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3024 KB Output is correct
2 Correct 2 ms 3536 KB Output is correct
3 Runtime error 7 ms 6992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 30040 KB Output is correct
2 Correct 956 ms 30060 KB Output is correct
3 Correct 727 ms 30036 KB Output is correct
4 Correct 962 ms 30024 KB Output is correct
5 Correct 910 ms 30036 KB Output is correct
6 Correct 650 ms 30028 KB Output is correct
7 Correct 861 ms 30024 KB Output is correct
8 Correct 580 ms 30056 KB Output is correct
9 Correct 680 ms 30036 KB Output is correct
10 Correct 864 ms 29968 KB Output is correct
11 Correct 684 ms 30000 KB Output is correct
12 Correct 831 ms 30024 KB Output is correct
13 Correct 677 ms 29952 KB Output is correct
14 Correct 1 ms 2896 KB Output is correct
15 Correct 3 ms 3408 KB Output is correct
16 Correct 2 ms 3500 KB Output is correct
17 Correct 39 ms 29948 KB Output is correct
18 Correct 36 ms 30032 KB Output is correct
19 Correct 43 ms 30056 KB Output is correct
20 Correct 44 ms 29996 KB Output is correct
21 Correct 40 ms 29964 KB Output is correct
22 Correct 45 ms 29980 KB Output is correct
23 Correct 44 ms 30052 KB Output is correct
24 Correct 41 ms 29960 KB Output is correct
25 Correct 46 ms 29956 KB Output is correct
26 Correct 36 ms 30056 KB Output is correct
27 Correct 2 ms 3408 KB Output is correct
28 Correct 2 ms 3408 KB Output is correct
29 Correct 2 ms 3408 KB Output is correct
30 Correct 3 ms 3408 KB Output is correct
31 Correct 3 ms 3408 KB Output is correct
32 Correct 2 ms 3408 KB Output is correct
33 Correct 2 ms 3536 KB Output is correct
34 Correct 2 ms 3408 KB Output is correct
35 Correct 3 ms 3408 KB Output is correct
36 Correct 3 ms 3428 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 20448 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3024 KB Output is correct
2 Correct 2 ms 3536 KB Output is correct
3 Runtime error 7 ms 6992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 19272 KB Output is correct
2 Correct 769 ms 30024 KB Output is correct
3 Correct 791 ms 30056 KB Output is correct
4 Correct 709 ms 30060 KB Output is correct
5 Correct 811 ms 30036 KB Output is correct
6 Correct 764 ms 30048 KB Output is correct
7 Correct 715 ms 29976 KB Output is correct
8 Correct 1 ms 2896 KB Output is correct
9 Correct 2 ms 3408 KB Output is correct
10 Correct 2 ms 3408 KB Output is correct
11 Correct 1 ms 3024 KB Output is correct
12 Correct 2 ms 3536 KB Output is correct
13 Runtime error 7 ms 6992 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -