Submission #348366

#	Time	Username	Problem	Language	Result	Execution time	Memory
348366		denkendoemeer	New Home (APIO18_new_home)	C++14	100 / 100	2396 ms	67388 KiB

new_home

#include<bits/stdc++.h>
#define ll long long
const int inf=1e8;
using namespace std;
int x[310005],t[610005],st[1210005],ans[310005];
vector<array<int,2>>v1[310005];
array<int,4>v2[1210005];
array<int,3>qa[310005];
struct comp
{
    bool operator () (const int &a,const int &b) const
    {
        if (x[a]==x[b])
            return a<b;
        return x[a]<x[b];
    }
};
map<int,int,comp>mp;
int u2=0,n,k,q;
void calc()
{
    int i;
    for(i=0;i<k;i++){
        mp[n+1]=0;
        for(auto it:v1[i]){
            auto it1=mp.upper_bound(it[1]),it2=it1--;
            v2[u2++]={(x[it1->first]+x[it2->first]+1)/2,x[it2->first],it2->second,it[0]};
            it2->second=it[0];
            if (it1->first==it[1]){
                it2=it1--;
                v2[u2++]={(x[it1->first]+x[it[1]]+1)/2,x[it[1]],it2->second,it[0]};
                mp.erase(it2);
            }
            else
                mp[it[1]]=it[0];
        }
        v2[u2++]={0,2*inf,mp[n+1],2*n+1};
    }
    sort(v2,v2+u2);
    int j=0,e;
    for(i=0;i<q;i++){
        while(j<u2 && v2[j][0]<=qa[i][0]){
            int l=v2[j][2]+2*n+1;
            int r=v2[j][3]+2*n+1;
            while(l<r){
                if (l%2==1)
                    st[l]=max(v2[j][1],st[l]);
                if (r%2==1)
                    st[r-1]=max(v2[j][1],st[r-1]);
                ++l/=2;
                r=r/2;
            }
            ++j;
        }
        for(e=qa[i][2]+2*n+1;e>=1;e=e/2)
            ans[qa[i][1]]=max(ans[qa[i][1]],st[e]-qa[i][0]);
    }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d%d%d",&n,&k,&q);
    int i;
    for(i=0;i<n;i++){
        int aux;
        scanf("%d%d%d%d",&x[i],&aux,&t[2*i],&t[2*i+1]);
        --aux;
        ++t[2*i+1];
        v1[aux].push_back({t[2*i],i});
        v1[aux].push_back({t[2*i+1],i});
    }
    x[n]=-2*inf;
    x[n+1]=2*inf;
    sort(t,t+2*n+1);
    for(i=0;i<k;i++){
        for(auto &it:v1[i])
            it[0]=lower_bound(t,t+2*n+1,it[0])-t;
        sort(v1[i].begin(),v1[i].end());
    }
    for(i=0;i<q;i++){
        scanf("%d%d",&qa[i][0],&qa[i][2]);
        qa[i][2]=upper_bound(t,t+2*n+1,qa[i][2])-t-1;
        qa[i][1]=i;
    }
    sort(qa,qa+q);
    mp[n]=0;
    calc();
    for(i=0;i<n;i++)
        x[i]=inf-x[i];
    for(i=0;i<q;i++)
        qa[i][0]=inf-qa[i][0];
    reverse(qa,qa+q);
    u2=0;
    memset(st,0,sizeof(st));
    calc();
    for(i=0;i<q;i++)
        if (ans[i]>=inf)
            printf("-1\n");
        else
            printf("%d\n",ans[i]);
return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d%d%d",&n,&k,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         scanf("%d%d%d%d",&x[i],&aux,&t[2*i],&t[2*i+1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         scanf("%d%d",&qa[i][0],&qa[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20