Submission #698641

#	Time	Username	Problem	Language	Result	Execution time	Memory
698641		vjudge1	New Home (APIO18_new_home)	C++17	5 / 100	5089 ms	18668 KiB

new_home

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#define int long long
#define endl '\n'
#define mod 1000000007;
using namespace std;

int seg[1000001][2];
int fin[1000001];
int N,Left,Right,T;

void Update(int Pos, int Val, int Type){
    int ind = N + Pos - 1 ;
    if(Type) {
        seg[ind][Type] = min(seg[ind][Type], Val);
        cout << seg[ind][Type] << endl;
        while(ind /= 2) seg[ind][Type] = min(seg[ind * 2][Type], seg[ind * 2 + 1][Type]);
    }
    else {
        seg[ind][Type] = max(seg[ind][Type], Val);
        while(ind /= 2) seg[ind][Type] = max(seg[ind * 2][Type], seg[ind * 2 + 1][Type]);
    }
}



int Query(int l = 1, int r = N, int ind = 1){
    if(l > Right or r < Left){
        if(T) return 1e18;
        else return -1;
    }
    if(l >= Left && r <= Right) return seg[ind][T];
    int mid = (l + r) / 2;
    if(T) return min(Query(l, mid, ind * 2), Query(mid + 1, r, ind * 2 + 1));
    else return max(Query(l, mid, ind * 2), Query(mid + 1, r, ind * 2 + 1));
}
using namespace std;
signed main() {
    int n,k,q; cin >> n >> k >> q;
    vector<pair<pair<int,int>,pair<int,int>>>x(n);
    vector<pair<int,pair<int,int>>>y;
    
    
    int cnt = 0;
    set<int>u;
    map<int,int>o;
    for(int i = 0; i < n; i++){
        cin >> x[i].first.first >> x[i].first.second >> x[i].second.first >> x[i].second.second;
        u.insert(x[i].first.second);
    }
    for(auto s: u) o[s] = cnt++;
    
    for(int i = 0; i < q; i++){
        int a,b; cin >> a >> b;
        vector<int>y(n, 1e18);
        int ans = -1;
        for(int j = 0; j < n; j++){
            if(b >= x[j].second.first && b <= x[j].second.second){
                int tt = o[x[j].first.second];
                if(abs(a - x[j].first.first) < abs(y[tt] - a)) y[tt] = x[j].first.first;
            }
        }
        int cnt = 0;
        for(int j = 0; j < n; j++){
            if(y[j] == 1e18) {
                y[j] = a;
                continue;
            }
            ans = max(ans, abs(a - y[j]));
            cnt++;
        }
        if(cnt < k) ans = -1;
        cout << ans << endl;
    }
    /*for(int i = 0; i < n; i++){
        int a,b,c,d; cin >> a >> b >> c >> d;
        x.push_back({{c, a}, {b, -1}});
        x.push_back({{d, a}, {b, 1}});
    }
    for(int i = 0; i < q; i++){
        int a,b; cin >> a >> b;
        y.push_back({b, {a, i}});
        vector<pair<int,int>>d;
        for(int j = 0; j < n; j++){
            if(a >= x[j].first.second
        }
    }*/
    
    /*sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    vector<set<int>>d(k);
    set<pair<int,int>>u;
    
    int j = 0, i = 0;
    while(i < q){
        while(j < n && x[j].first.first <= y[j].first){
            if(x[j].second.second < 0){ // add
                d[k].insert({x[j].first.second});
            }
            j++;
        }
       
    }
    for(int i = 0; i < q; i++) cout << fin[i] << endl;*/
    
    
    return 0;
    
}

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