Submission #131762

#	Time	Username	Problem	Language	Result	Execution time	Memory
131762		Bodo171	Two Antennas (JOI19_antennas)	C++14	0 / 100	553 ms	32788 KiB

antennas

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=200005;
vector< pair<int,int> > q[nmax],upd[nmax],pairs[nmax];
int a[nmax],b[nmax],h[nmax],l[nmax],r[nmax],ans[nmax];
int n,i,j,Q;
struct node
{
    int nd,ll,rr;
}stv[100];
struct aint
{
    int arb[4*nmax];
    void update(int nod,int l,int r,int poz,int val)
    {
        if(l==r)
        {
            arb[nod]=val;
            return;
        }
        int m=(l+r)/2;
        if(poz<=m) update(2*nod,l,m,poz,val);
        else update(2*nod+1,m+1,r,poz,val);
        arb[nod]=min(arb[2*nod],arb[2*nod+1]);
    }
    int st,dr,mn;
    void query(int nod,int l,int r)
    {
        if(st<=l&&r<=dr)
        {
            mn=min(mn,arb[nod]);
            return;
        }
        int m=(l+r)/2;
        if(st<=m) query(2*nod,l,m);
        if(m<dr) query(2*nod+1,m+1,r);
    }
    int calc(int S,int D)
    {
        st=S;dr=D;mn=(1<<30);
        query(1,1,n);
        return mn;
    }
    int nr;
    void gt(int nod,int l,int r)
    {
        if(st<=l&&r<=dr)
        {
            stv[++nr]={nod,l,r};
            return;
        }
        int m=(l+r)/2;
        if(st<=m) gt(2*nod,l,m);
        if(m<dr) gt(2*nod+1,m+1,r);
    }
    int saved,where;
    void cb(int nod,int l,int r,int cat)
    {
        if(l==r)
        {
            saved=arb[nod];
            where=l;
            return;
        }
        int m=(l+r)/2;
        if(arb[2*nod+1]<=cat) cb(2*nod+1,m+1,r,cat);
        else cb(2*nod,l,m,cat);
    }
    void roll(int source,int S,int D,int val)
    {
        int wanted=val-1;
        bool ok=1;
        while(ok&&S<=D)
        {
            if(calc(S,D)>wanted) ok=0;
            else
            {
                st=S;dr=D;nr=0;
                gt(1,1,n);
                int it;
                for(it=nr;it>=1&&arb[stv[it].nd]>wanted;it--);
                cb(stv[it].nd,stv[it].ll,stv[it].rr,wanted);
                wanted=val-2*(val-saved);D=where-1;
                pairs[source].push_back({where,val-saved});
            }
        }
    }
}mn,mx;
void solve()
{
    for(i=1;i<=n;i++)
    {
        q[i].clear();
        upd[i].clear();
        pairs[i].clear();
    }
    for(i=1;i<=n;i++)
      mn.update(1,1,n,i,(1<<30)),mx.update(1,1,n,i,(1<<30));
    for(i=1;i<=n;i++)
    {
        if(i+a[i]<=n)upd[i+a[i]].push_back({i,h[i]});
        if(i+b[i]+1<=n)upd[i+b[i]+1].push_back({i,(1<<30)});
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<upd[i].size();j++)
        {
            mn.update(1,1,n,upd[i][j].first,upd[i][j].second);
        }
        mn.roll(i,max(i-b[i],1),i-a[i],h[i]);
    }
    for(i=1;i<=Q;i++)
    {
        q[r[i]].push_back({l[i],i});
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<pairs[i].size();j++)
        {
            mx.update(1,1,n,pairs[i][j].first,-pairs[i][j].second);
        }
        for(j=0;j<q[i].size();j++)
        {
            int gt=-mx.calc(q[i][j].first,i);
            if(gt>ans[q[i][j].second]) ans[q[i][j].second]=gt;
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>h[i]>>a[i]>>b[i];
    }
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        cin>>l[i]>>r[i];
        ans[i]=-1;
    }
    solve();
    reverse(h+1,h+n+1);
    reverse(a+1,a+n+1);
    reverse(b+1,b+n+1);
    for(i=1;i<=Q;i++)
    {
        l[i]=n-l[i]+1;
        r[i]=n-r[i]+1;
        swap(l[i],r[i]);
    }
    solve();
    for(i=1;i<=Q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void solve()':
antennas.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<upd[i].size();j++)
                 ~^~~~~~~~~~~~~~
antennas.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<pairs[i].size();j++)
                 ~^~~~~~~~~~~~~~~~
antennas.cpp:125:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<q[i].size();j++)
                 ~^~~~~~~~~~~~

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