Submission #1170129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170129		mkolko21	Two Antennas (JOI19_antennas)	C++20	22 / 100	234 ms	50580 KiB

antennas

#include <iostream>
#include <vector>
#define int long long
using namespace std;

const int roz=(1<<20);

int tab[200'007][3];
int tree[(roz*2)+3][2];
vector<pair<int,int> > zmiany[200'007];

void dod(int v, int h)
{
    v=v+roz;
    tree[v][0]=h;
    tree[v][1]=h;
    v=v/2;
    while(v>0){
        if(tree[v*2][0]!=0 && tree[v*2+1][0]!=0)
            tree[v][0]=min(tree[v*2][0],tree[v*2+1][0]);
        else
            tree[v][0]=max(tree[v*2][0],tree[v*2+1][0]);
        tree[v][1]=max(tree[v*2][1],tree[v*2+1][1]);
        v=v/2;
    }
}

pair<int,int> szuk(int pocz, int kon)
{
    pair<int,int> odp={0,0};
    pocz=pocz+roz-1;
    kon=kon+roz+1;

    while(pocz/2!=kon/2){
        if(pocz%2==0){
            if(odp.first==0)
                odp.first=tree[pocz+1][0];
            if(tree[pocz+1][0]!=0)
                odp.first=min(odp.first,tree[pocz+1][0]);
            odp.second=max(odp.second,tree[pocz+1][1]);
        }
        if(kon%2==1){
            if(odp.first==0)
                odp.first=tree[kon-1][0];
            if(tree[pocz+1][0]!=0)
                odp.first=min(odp.first,tree[kon-1][0]);
            odp.second=max(odp.second,tree[kon-1][1]);
        }
        pocz=pocz/2;kon=kon/2;
    }
    return odp;
}

int fun(int pocz, int kon)
{
    int odp=-1, p;
    for(int a=pocz; a<=kon; a++)
    {
        for(int i=0; i<zmiany[a].size(); i++)
            dod(zmiany[a][i].first,zmiany[a][i].second);
        zmiany[a].clear();

        zmiany[min(kon+1,a+tab[a][1])].push_back({a,tab[a][0]});
        zmiany[min(kon+1,a+tab[a][2]+1)].push_back({a,0});

        p=szuk(max(pocz,a-tab[a][2]),max(pocz,a-tab[a][1])).first;
        if(a-tab[a][1]>=pocz && p!=0)
            odp=max(odp,abs(tab[a][0]-p));
        p=szuk(max(pocz,a-tab[a][2]),max(pocz,a-tab[a][1])).second;
        if(a-tab[a][1]>=pocz && p!=0)
            odp=max(odp,abs(tab[a][0]-p));
    }
    for(int i=0; i<zmiany[kon+1].size(); i++)
        dod(zmiany[kon+1][i].first,zmiany[kon+1][i].second);
    zmiany[kon+1].clear();
    
    for(int a=0; a<=200'001; a++)
        zmiany[a].clear();
    for(int a=0; a<=roz*2; a++){
        tree[a][0]=0;
        tree[a][1]=0;
    }
    
    return odp;
}

main()
{

    int n, m, p, p2;
    cin>>n;
    for(int a=0; a<n; a++)
        for(int i=0; i<3; i++)
            cin>>tab[a][i];
    cin>>m;
    for(int a=0; a<m; a++)
    {
        cin>>p>>p2;
        cout<<fun(p-1,p2-1)<<"\n";
    }
}

Compilation message (stderr)

antennas.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main()
      | ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65