제출 #465585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465585		amirmohammad_nezami	새 집 (APIO18_new_home)	C++17	0 / 100	2308 ms	192848 KiB

new_home

//                                                          In the name of God 
//                                           We are everywhere while we are nowhere(Haj NEZAM...)
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define lc 2 * v
#define nt(v) v ^ 1
#define rc 2 * v + 1
#define PB push_back
#define MP make_pair
#define ll long long
#define int long long
#define ld long double
#define mid (s + e) / 2
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define pll pair <long long , long long>
#define piii pair <int , pair <int , int> >
#define FAST ios::sync_with_stdio(0);cin.tie(0)
#define UNI(e) e.resize(unique(_all(e)) - e.begin())
 
#define kill(e) cout << e << '\n'
 
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,avx")
#pragma GCC optimize("O3,unroll-loops")

const int maxn = 6e5 + 5 , N = 400 + 5 , SQ = 55 , base = 879169 , mod = 1e9 + 7 , INF = 1e9 + 5 , lg = 11;
const ld eps = 1e-6;

struct node {
    int mnL = INF , mxR = -INF;
};

node seg[4 * maxn];

int x[maxn] , t[maxn] , a[maxn] , b[maxn] , ql[maxn] , qx[maxn];
int n , k , q , SZ , cnt_zero , res[maxn] , L[maxn] , R[maxn];
set <pii> active[maxn];
vector <int> vec[maxn];
vector <int> add[maxn];
vector <int> rem[maxn];
vector <piii> comp1;
vector <int> comp2;

void compress() {
    sort(_all(comp1)) , sort(_all(comp2)); 
    UNI(comp2);
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(_all(comp2) , a[i]) - comp2.begin();
        b[i] = lower_bound(_all(comp2) , b[i]) - comp2.begin();
        add[a[i]].PB(i) , rem[b[i]].PB(i);
    }
    for (int i = 0; i < q; ++i) {
        ql[i] = lower_bound(_all(comp2) , ql[i]) - comp2.begin();
        vec[ql[i]].PB(i);
    }
    for (int i = 0; i < n + q; ++i) {
        if(!comp1[i].S.F) x[comp1[i].S.S] = i;
        else qx[comp1[i].S.S] = i;
    }
}

void modify_L(int p , int r , int v = 1 , int s = 0 , int e = SZ) {
    if(e - s == 1) {
        seg[v].mnL = L[s] = r;
        return ;
    }
    if(p < mid) modify_L(p , r , lc , s , mid);
    else modify_L(p , r , rc , mid , e);
    seg[v].mnL = min(seg[lc].mnL , seg[rc].mnL);
}

void modify_R(int p , int r , int v = 1 , int s = 0 , int e = SZ) {
    if(e - s == 1) {
        seg[v].mxR = R[s] = r;
        return ;
    }
    if(p < mid) modify_R(p , r , lc , s , mid);
    else modify_R(p , r , rc , mid , e);
    seg[v].mxR = max(seg[lc].mxR , seg[rc].mxR);
}

int get_L(int l , int r , int p , int v = 1 , int s = 0 , int e = SZ) {
    if(l >= e || s >= r || seg[v].mnL >= p) return -1;
    if(e - s == 1) return s;

    int res = get_L(l , r , p , rc , mid , e);
    return (res != -1 ? res : get_L(l , r , p , lc , s , mid));
}

int get_R(int l , int r , int p , int v = 1 , int s = 0 , int e = SZ) {
    if(l >= e || s >= r || seg[v].mxR <= p) return -1;
    if(e - s == 1) return s;

    int res = get_R(l , r , p , lc , s , mid);
    return (res != -1 ? res : get_R(l , r , p , rc , mid , e));
}

void add_store(int st) {
    // cout << "ADD STORE " << st << ' ' << x[st] << endl;
    if(!_sz(active[t[st]])) cnt_zero--;

    set <pii> ::iterator it = active[t[st]].lower_bound({x[st] , -1});
    R[x[st]] = (it != active[t[st]].end() ? it -> F : INF);
    L[x[st]] = (it != active[t[st]].begin() ? (--it) -> F : -INF);
    active[t[st]].insert({x[st] , st});

    modify_L(x[st] , L[x[st]]) , modify_R(x[st] , R[x[st]]);
    if(R[x[st]] != INF) modify_L(R[x[st]] , x[st]);
    if(L[x[st]] != -INF) modify_R(L[x[st]] , x[st]);
}

void rem_store(int st) {
    // cout << "REM STORE " << st << ' ' << x[st] << endl;
    if(R[x[st]] != INF) modify_L(R[x[st]] , L[x[st]]);
    if(L[x[st]] != -INF) modify_R(L[x[st]] , R[x[st]]);
    modify_L(x[st] , INF) , modify_R(x[st] , -INF);
    active[t[st]].erase({x[st] , st});

    if(!_sz(active[t[st]])) cnt_zero++;
}

int32_t main() {
    FAST;
    cin >> n >> k >> q;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        comp1.PB({x[i] , {0 , i}}) , comp2.PB(a[i]) , comp2.PB(b[i]);
    }
    for (int i = 0; i < q; ++i) {
        cin >> qx[i] >> ql[i];
        comp1.PB({qx[i] , {1 , i}}) , comp2.PB(ql[i]);
    }
    compress();

    cnt_zero = k;
    SZ = _sz(comp1);
    fill(L , L + maxn , INF);
    fill(R , R + maxn , -INF);

    for (int i = 0; i < maxn; ++i) {
        for (auto st : add[i]) add_store(st);
        for (auto qu : vec[i]) {
            if(cnt_zero) {
                res[qu] = -1; continue;
            }
            // cout << qu << ' ' << qx[qu] << ' ' << R[0] << ' ' << L[3] << endl;
            int pos1 = get_R(0 , qx[qu] + 1 , qx[qu]);
            int pos2 = get_L(qx[qu] , SZ , qx[qu]);

            int val1 = (pos1 == -1 ? INF : comp1[pos1].F);
            int val2 = (pos2 == -1 ? -INF : comp1[pos2].F);

            // cout << pos1 << ' ' << pos2 << ' ' << val1 << ' ' << val2 << endl;
            res[qu] = max(0ll , max(comp1[qx[qu]].F - val1 , val2 - comp1[qx[qu]].F));
        }
        for (auto st : rem[i]) rem_store(st);
    }

    for (int i = 0; i < q; ++i) {
        cout << res[i] << '\n';
    }
}

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