Submission #403111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403111	2021-05-12T18:49:41 Z	Hazem	New Home (APIO18_new_home)	C++14	10 / 100	1608 ms	282612 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Incorrect	9 ms	14412 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Incorrect	9 ms	14412 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1576 ms	251916 KB	Output is correct
2	Correct	1147 ms	281196 KB	Output is correct
3	Correct	1264 ms	186912 KB	Output is correct
4	Correct	1542 ms	252804 KB	Output is correct
5	Correct	992 ms	280324 KB	Output is correct
6	Correct	1081 ms	281140 KB	Output is correct
7	Correct	1082 ms	186972 KB	Output is correct
8	Correct	1506 ms	252728 KB	Output is correct
9	Correct	1608 ms	274544 KB	Output is correct
10	Correct	1404 ms	282612 KB	Output is correct
11	Correct	1038 ms	276728 KB	Output is correct
12	Correct	1243 ms	280764 KB	Output is correct