Submission #262390

#	Time	Username	Problem	Language	Result	Execution time	Memory
262390		CaroLinda	New Home (APIO18_new_home)	C++14	12 / 100	3447 ms	12448 KiB

new_home

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a; i < b ; i++)
#define ff first
#define ss second
#define pb emplace_back
#define ll long long
#define mk make_pair
#define sz(x) x.size()
#define pii pair<int,int>
#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()

const int MAXN = 6e4+10 ;
const int inf = 1e9+10 ;

using namespace std ;

struct Event
{

    int type , tempo , id ;

    Event(int a = 0 , int b = 0 , int c = 0 ) : type(a) , tempo(b) , id(c) {}
    bool operator < (Event other) const
    {
        if( tempo == other.tempo ) return type < other.type ;
        return tempo < other.tempo ;
    }

};

int N , Q , K ;
int loja[MAXN] , x_loja[MAXN] , x_query[MAXN] , ans[MAXN] ;
multiset<int> s[MAXN] ;
vector<Event> sweep ;

int main()
{

    scanf("%d%d%d", &N , &K , &Q )  ;
    assert( K <= 400 ) ;

    for(int i = 1 , a , b ; i <= N ; i++ )
    {
        scanf("%d%d%d%d", &x_loja[i] , &loja[i] , &a, &b ) ;
        sweep.pb( Event(0, a, i) ) ;
        sweep.pb( Event(2, b, i) ) ;
    }
    for(int i = 1 , a , b ; i <= Q ; i++ )
    {
        scanf("%d%d", &x_query[i], &a ) ;
        sweep.pb( Event(1, a, i) ) ;
    }

    sort(all(sweep)) ;

    for(auto e : sweep )
    {
        int type = e.type ;
        int id = e.id ;

        if(type == 0)
        {
            s[ loja[id] ].insert( x_loja[id] ) ;
            continue ;
        }
        if(type == 2)
        {
            auto it = s[ loja[id] ].find( x_loja[id] ) ;
            s[ loja[id] ].erase(it) ;
            continue ;
        }

        for(int i = 1 ;i  <= K ; i++ )
        {

            if(sz(s[i]) == 0 || ans[id] == -1 ) { ans[id] = -1 ; continue ; }

            auto it_menor = s[i].lower_bound( x_query[id] ) ;
            if(it_menor != s[i].begin() ) it_menor -- ;
            auto it_maior = s[i].lower_bound( x_query[id] ) ;

            int dist = inf ;
            if(it_menor != s[i].end() ) dist = min(dist, abs(x_query[id] - *it_menor )) ;
            if( it_maior != s[i].end() ) dist = min( dist, abs(*it_maior - x_query[id]) );


            ans[id] = max(ans[id] , dist ) ;

        }


    }

    for(int i = 1 ; i <= Q ; i++ ) printf("%d\n" , ans[i]) ;

}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:51:25: warning: unused variable 'b' [-Wunused-variable]
   51 |     for(int i = 1 , a , b ; i <= Q ; i++ )
      |                         ^
new_home.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     scanf("%d%d%d", &N , &K , &Q )  ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d%d%d%d", &x_loja[i] , &loja[i] , &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d%d", &x_query[i], &a ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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