oj.uz

Submission #787865

# Submission time Handle Problem Language Result Execution time Memory
787865 2023-07-19T13:38:53 Z andrei_boaca Radio Towers (IOI22_towers) C++17
18 / 100
 935 ms 30068 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(abs(dp[tolft[R]]-ans)<=1);
    }
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 19276 KB Output is correct
2 Correct 665 ms 30064 KB Output is correct
3 Correct 716 ms 30024 KB Output is correct
4 Correct 663 ms 30036 KB Output is correct
5 Correct 694 ms 29968 KB Output is correct
6 Correct 604 ms 30060 KB Output is correct
7 Correct 555 ms 29980 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 2 ms 3024 KB Output is correct
2 Correct 3 ms 3536 KB Output is correct
3 Runtime error 6 ms 6968 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 2 ms 3024 KB Output is correct
2 Correct 3 ms 3536 KB Output is correct
3 Runtime error 6 ms 6968 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 703 ms 30052 KB Output is correct
2 Correct 868 ms 30032 KB Output is correct
3 Correct 912 ms 30024 KB Output is correct
4 Correct 830 ms 30036 KB Output is correct
5 Correct 733 ms 30020 KB Output is correct
6 Correct 935 ms 30024 KB Output is correct
7 Correct 899 ms 30024 KB Output is correct
8 Correct 681 ms 29944 KB Output is correct
9 Correct 703 ms 30040 KB Output is correct
10 Correct 620 ms 30056 KB Output is correct
11 Correct 756 ms 30024 KB Output is correct
12 Correct 608 ms 30032 KB Output is correct
13 Correct 583 ms 30012 KB Output is correct
14 Correct 2 ms 2896 KB Output is correct
15 Correct 2 ms 3408 KB Output is correct
16 Correct 2 ms 3408 KB Output is correct
17 Correct 52 ms 30044 KB Output is correct
18 Correct 50 ms 30024 KB Output is correct
19 Correct 48 ms 30068 KB Output is correct
20 Correct 45 ms 29996 KB Output is correct
21 Correct 39 ms 29992 KB Output is correct
22 Correct 36 ms 30044 KB Output is correct
23 Correct 35 ms 30052 KB Output is correct
24 Correct 47 ms 30060 KB Output is correct
25 Correct 53 ms 30064 KB Output is correct
26 Correct 39 ms 29960 KB Output is correct
27 Correct 2 ms 3408 KB Output is correct
28 Correct 2 ms 3408 KB Output is correct
29 Correct 3 ms 3456 KB Output is correct
30 Correct 3 ms 3408 KB Output is correct
31 Correct 2 ms 3408 KB Output is correct
32 Correct 2 ms 3408 KB Output is correct
33 Correct 2 ms 3408 KB Output is correct
34 Correct 2 ms 3456 KB Output is correct
35 Correct 2 ms 3408 KB Output is correct
36 Correct 2 ms 3408 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 20528 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 2 ms 3024 KB Output is correct
2 Correct 3 ms 3536 KB Output is correct
3 Runtime error 6 ms 6968 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 242 ms 19276 KB Output is correct
2 Correct 665 ms 30064 KB Output is correct
3 Correct 716 ms 30024 KB Output is correct
4 Correct 663 ms 30036 KB Output is correct
5 Correct 694 ms 29968 KB Output is correct
6 Correct 604 ms 30060 KB Output is correct
7 Correct 555 ms 29980 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 2 ms 3024 KB Output is correct
12 Correct 3 ms 3536 KB Output is correct
13 Runtime error 6 ms 6968 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -