Submission #403111

#	Time	Username	Problem	Language	Result	Execution time	Memory
403111		Hazem	New Home (APIO18_new_home)	C++14	10 / 100	1608 ms	282612 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 6e5+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 1e14;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

int x[N],t[N],a[N],b[N];
vector<int>freq[N];

struct node{

    node *l,*r;
    int mx = -INF,mn = INF;
    node():l(NULL),r(NULL),mx(-INF),mn(INF){};

};

void update(node * &v,int tl,int tr,int l,int r,int val){

    if(tl>r||tr<l)
        return ;

    if(v==NULL)
        v = new node();

    if(tl>=l&&tr<=r){
        v->mx = max(v->mx,val);
        v->mn = min(v->mn,val);
        return ;
    }

    int mid = (tl+tr)/2;
    update(v->l,tl,mid,l,r,val);
    update(v->r,mid+1,tr,l,r,val);
}

pair<int,int> get(node *v,int l,int r,int pos){

    if(v==NULL)
        return make_pair(INF,-INF);
    
    if(l==r)
        return make_pair(v->mn,v->mx);

    int mid = (l+r)/2;
    if(pos<=mid){
        pair<int,int>p = get(v->l,l,mid,pos);
        return make_pair(min(p.F,v->mn),max(p.S,v->mx));
    }
    else {
        pair<int,int>p = get(v->r,mid+1,r,pos);
        return make_pair(min(p.F,v->mn),max(p.S,v->mx));
    }
}

node *root;

int main(){

    //freopen("out.txt","w",stdout);

    int n,k,q;
    scanf("%d%d%d",&n,&k,&q);

    for(int i=1;i<=k;i++)
        freq[i].push_back(-INF);

    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d",&x[i],&t[i],&a[i],&b[i]),freq[t[i]].push_back(x[i]);

    for(int i=1;i<=k;i++)
        freq[i].push_back(INF);

    for(int i=1;i<=k;i++)
        sort(freq[i].begin(),freq[i].end());
        
    for(int i=1;i<=k;i++)
        for(int j=0;j<freq[i].size()-1;j++){
            
            int l = freq[i][j],r = freq[i][j+1];

            if(l==-INF){
                update(root,0,INF,0,r,r);
                continue;
            }

            if(r==INF){
                update(root,0,INF,l,r,l);
                continue;
            }

            int mid = (l+r)/2;
            update(root,0,INF,l,mid,l);
            update(root,0,INF,mid+1,r,r);
        }
        
    while(q--){
        int pos,y;
        scanf("%d%d",&pos,&y);
        pair<int,int>p = get(root,0,INF,pos);
        LL ans = max(abs(pos-p.F),abs(pos-p.S));
        printf("%lld\n",ans>=INF?-1:ans);
    }
}   

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j=0;j<freq[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~
new_home.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d%d",&n,&k,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%d%d%d%d",&x[i],&t[i],&a[i],&b[i]),freq[t[i]].push_back(x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d%d",&pos,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~

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