oj.uz

Submission #403110

# Submission time Handle Problem Language Result Execution time Memory
403110 2021-05-12T18:45:22 Z Hazem New Home (APIO18_new_home) C++14
0 / 100
 1238 ms 188284 KB 
#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++)
        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:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         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:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d%d",&pos,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 14412 KB Output is correct
2 Incorrect 9 ms 14412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1238 ms 188284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1158 ms 187660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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