Submission #375830

#	Time	Username	Problem	Language	Result	Execution time	Memory
375830		daniel920712	Two Antennas (JOI19_antennas)	C++14	35 / 100	3081 ms	168096 KiB

antennas

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>

using namespace std;
struct A
{

    int l,r;
    int nxl,nxr;
    pair < int , int > ans;
    map < int , int > all;
}Node[1000005];
int all[200005],now=1;
int ans[200005];
int l[200005],r[200005];
vector < pair < int , int > > query[200005];
int x[200005],y[200005];
vector < pair < int , int > > in[200005];
vector < pair < int , int > > out[200005];
vector < pair < int , int > > out2[200005];


pair < int , int > operator+(pair < int , int > a,pair < int , int > b)
{
    return make_pair(max(a.first,b.first),min(a.second,b.second));
}
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].all[-1]++;
    if(l==r)
    {
        Node[here].ans=make_pair(0,2e9);
        return;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
void cha(int where,pair < int , int > con,int here)
{
    if(where==Node[here].l&&where==Node[here].r)
    {
        Node[here].ans=con;
        return;
    }
    if(where<=(Node[here].l+Node[here].r)/2) cha(where,con,Node[here].nxl);
    else cha(where,con,Node[here].nxr);
    Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
void add(int where,int how,int here)
{
    Node[here].all[how]++;
    //printf("aa %d %d %d\n",where,how,here);
    if(where==Node[here].l&&where==Node[here].r) return;
    if(where<=(Node[here].l+Node[here].r)/2) add(where,how,Node[here].nxl);
    else add(where,how,Node[here].nxr);

}
void del(int where,int how,int here)
{
    //printf("%d\n",how);
    Node[here].all[how]--;
    if(Node[here].all[how]==0) Node[here].all.erase(how);
    if(where==Node[here].l&&where==Node[here].r) return;
    if(where<=(Node[here].l+Node[here].r)/2) del(where,how,Node[here].nxl);
    else del(where,how,Node[here].nxr);
}

int Find2(int l,int r,int here)
{
    if(l==Node[here].l&&r==Node[here].r)
    {
        //printf("%d %d %d %d\n",l,r,prev(Node[here].all.end())->first,prev(Node[here].all.end())->second);
        return prev(Node[here].all.end())->first;
    }
    if(r<=(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxr);
    else return max(Find2(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find2((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
pair < int , int > Find(int l,int r,int here)
{
    if(l==Node[here].l&&r==Node[here].r) return Node[here].ans;
    if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
    else return Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl)+Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr);
}
pair < int , int > tt;
int main()
{
    int N,M,ok=0,i,j;
    scanf("%d",&N);
    for(i=1;i<=N;i++)
    {
        scanf("%d %d %d",&all[i],&l[i],&r[i]);
        if(i-l[i]>=1)
        {
            in[max(1,i-r[i])].push_back(make_pair(i,all[i]));
            out[i-l[i]+1].push_back(make_pair(i,all[i]));
        }
    }
    scanf("%d",&M);
    for(i=0;i<M;i++)
    {
        scanf("%d %d",&x[i],&y[i]);
        query[x[i]].push_back(make_pair(y[i],i));
        ans[i]=-1;
    }
    build(1,N,0);
    if(N<=2000)
    {
        for(i=1;i<=N;i++)
        {
            for(j=i+1;j<=N;j++)
            {
                if(i+l[i]<=j&&i+r[i]>=j&&j-r[j]<=i&&j-l[j]>=i)
                {
                    //printf("%d %d %d\n",i,j,abs(all[i]-all[j]));
                    out2[i+1].push_back(make_pair(j,abs(all[i]-all[j])));
                    add(j,abs(all[i]-all[j]),0);
                }
            }
        }

        for(i=1;i<=N;i++)
        {
            //for(auto j:in[i]) add(j.first,j.second,0);
            for(auto j:out2[i]) del(j.first,j.second,0);
            for(auto j:query[i]) ans[j.second]=Find2(i,j.first,0);

        }

    }
    else
    {
        for(i=1;i<=N;i++)
        {
            for(auto j:in[i]) cha(j.first,make_pair(j.second,j.second),0);
            for(auto j:out[i]) cha(j.first,make_pair(0,2e9),0);
            for(j=0;j<M;j++)
            {
                if(i>=x[j]&&i+l[i]<=y[j])
                {
                    tt=Find(i+l[i],min(y[j],i+r[i]),0);
                    if(tt.first) ans[j]=max(ans[j],abs(all[i]-tt.first));
                    if(tt.second!=2000000000) ans[j]=max(ans[j],abs(all[i]-tt.second));
                }
            }
        }

    }


    for(j=0;j<M;j++) printf("%d\n",ans[j]);


    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:97:13: warning: unused variable 'ok' [-Wunused-variable]
   97 |     int N,M,ok=0,i,j;
      |             ^~
antennas.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
antennas.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |         scanf("%d %d %d",&all[i],&l[i],&r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |     scanf("%d",&M);
      |     ~~~~~^~~~~~~~~
antennas.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         scanf("%d %d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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