Submission #1131703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131703		Cookie	New Home (APIO18_new_home)	C++20	80 / 100	4098 ms	1114112 KiB

new_home

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 6e5 + 5, mxq = 1e5 + 5, sq = 300, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
// <3;
struct Q{
    int l, r; pii cool;
    bool operator <(const Q &other){
        return(cool < other.cool);
    }
};
int n, k, q;
int x[mxn + 1], t[mxn + 1], a[mxn + 1], b[mxn + 1], l[mxn + 1], y[mxn + 1];
vt<pii>events[mxn + 1];
multiset<int>stores; 
map<pair<int, int>, pair<int, int>>open_up, open_down;
pii calc_up(int l, int r){
    return(mpp((l + r) / 2, l));
}
pii calc_down(int l, int r){
    return(mpp((l + r + 1) / 2, r));
}
vt<Q>queries_up, queries_down;
void remove(int l, int r, int t){
    pair<int, int>seg_up = calc_up(l, r), seg_down = calc_down(l, r);
    open_up[seg_up].se--;
    if(open_up[seg_up].se == 0){
        queries_up.pb({open_up[seg_up].fi, t - 1, seg_up});
        open_up.erase(seg_up);
    }
    open_down[seg_down].se--;
    if(open_down[seg_down].se == 0){
        queries_down.pb({open_down[seg_down].fi, t - 1, seg_down});
        open_down.erase(seg_down);
    }
}
void add(int l, int r, int t){
    pair<int, int>seg_up = calc_up(l, r), seg_down = calc_down(l, r);
    if(open_up.find(seg_up) == open_up.end()){
        open_up[seg_up].fi = t;
    }
    open_up[seg_up].se++;
    if(open_down.find(seg_down) == open_down.end()){
        open_down[seg_down].fi = t;
    }
    open_down[seg_down].se++;
}
struct Query{
    int tme, id, pos;
    bool operator <(const Query &other){
        return(pos < other.pos);
    }
};
vt<pii>stup[8 * mxn + 1], stdown[8 * mxn + 1];
vt<pii>qup[8 * mxn + 1], qdown[8 * mxn + 1];
void updup(int nd, int l, int r, int ql, int qr, int a, int b){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        stup[nd].pb(mpp(a, b)); return;
    }
    int mid = (l + r) >> 1;
    updup(nd << 1, l, mid, ql, qr, a, b); updup(nd << 1 | 1, mid + 1, r, ql, qr, a, b);
}
void upddown(int nd, int l , int r, int ql, int qr, int a, int b){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        stdown[nd].pb(mpp(a, b)); return;
    }
    int mid = (l + r) >> 1;
    upddown(nd << 1, l, mid, ql, qr, a, b); upddown(nd << 1 | 1, mid + 1, r, ql, qr, a, b);
}
void updqup(int nd, int l, int r, int ql, int qr, int a, int b){
    if(ql > r || qr < l)return;
    qup[nd].pb(mpp(a, b));
    if(l == r)return;
    int mid = (l + r) >> 1;
    updqup(nd << 1, l, mid, ql, qr, a, b); updqup(nd << 1 | 1, mid + 1, r, ql, qr, a, b);
}
void updqdown(int nd, int l, int r, int ql, int qr, int a, int b){
    if(ql > r || qr < l)return;
    qdown[nd].pb(mpp(a, b));
    if(l == r)return;
    int mid = (l + r) >> 1;
    updqdown(nd << 1, l, mid, ql, qr, a, b); updqdown(nd << 1 | 1, mid + 1, r, ql, qr, a, b);
}
int ans[mxn + 1];
void dfs(int s, int l, int r){
    int rp = 0, mn_xintercept = inf;
    for(auto i: qup[s]){
        while(rp < sz(stup[s]) && stup[s][rp].fi >= i.fi){
            mn_xintercept = min(mn_xintercept, stup[s][rp].se); rp++;
        }
        ans[i.se] = max(ans[i.se], i.fi - mn_xintercept);
        //cout << s << " " << i.se << " " << ans[i.se] << "\n";
    }
    rp = 0;
    
    int mx_xintercept = -inf;
    for(auto i: qdown[s]){
        while(rp < sz(stdown[s]) && stdown[s][rp].fi <= i.fi){
            mx_xintercept = max(mx_xintercept, stdown[s][rp].se); rp++;
        }
        //cout << mx_xintercept << " ";
        ans[i.se] = max(ans[i.se], mx_xintercept - i.fi);
    }
    
    if(l == r)return;
    int mid = (l + r) >> 1;
    dfs(s << 1, l, mid); dfs(s << 1 | 1, mid + 1, r);
}
void solve(){
    
    cin >> n >> k >> q;
    vt<int>cc;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> t[i] >> a[i] >> b[i]; cc.pb(a[i]); cc.pb(b[i]);
    }
    for(int i = 1; i <= q; i++){
        cin >> l[i] >> y[i];
        cc.pb(y[i]);
    }
    sort(ALL(cc)); 
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(ALL(cc), a[i]) - cc.begin() + 1;
        b[i] = lower_bound(ALL(cc), b[i]) - cc.begin() + 1;
    }
    for(int i = 1; i <= n; i++){
        events[t[i]].pb(mpp(a[i], x[i])); events[t[i]].pb(mpp(b[i] + 1, -x[i]));
    }
    for(int i = 1; i <= q; i++){
        
        y[i] = lower_bound(ALL(cc), y[i]) - cc.begin() + 1;
    }
   
    for(int colour = 1; colour <= k; colour++){
        open_up.clear(); open_down.clear();
        stores.clear(); stores.insert(-inf); stores.insert(inf); add(-inf, inf, 1);
        sort(ALL(events[colour]));
        
        for(auto [tme, pos]: events[colour]){
            if(pos > 0){
                auto itl = prev(stores.upper_bound(pos)), itr = stores.lower_bound(pos);
                remove(*itl, *itr, tme);
                add(*itl, pos, tme); add(pos, *itr, tme); stores.insert(pos);
            }else{
                pos = -pos;
                stores.erase(stores.find(pos));
                auto itl = prev(stores.upper_bound(pos)), itr = stores.lower_bound(pos);
                add(*itl, *itr, tme);
                remove(*itl, pos, tme); remove(pos, *itr, tme);
            }
        }
        for(auto i: open_up){
            queries_up.pb({i.se.fi, sz(cc), mpp(i.fi.fi, i.fi.se)});
        }
        for(auto i: open_down){
            //if(colour == 2)cout << i.fi.fi << " " << i.fi.se << " ";
            queries_down.pb({i.se.fi, sz(cc), mpp(i.fi.fi, i.fi.se)});
        }
    }
    
    
    
    sort(ALLR(queries_up)); sort(ALL(queries_down));
    for(auto [l, r, cool]: queries_up){
        updup(1, 1, sz(cc), l, r, cool.fi, cool.se);
    }
    for(auto [l, r, cool]: queries_down){
        //cout << l << " " << r << " " << cool.fi << " " << cool.se << "\n";
        upddown(1, 1, sz(cc), l, r, cool.fi, cool.se);
    }
    
    vt<Query>qqup, qqdown;
    for(int i = 1; i <= q; i++){
        qqup.pb({y[i], i, l[i]}); qqdown.pb({y[i], i, l[i]});
    }
    sort(ALLR(qqup)); sort(ALL(qqdown));
    for(auto [tme, id, pos]: qqup){
        updqup(1, 1, sz(cc), tme, tme, pos, id);
    }
    for(auto [tme, id, pos]: qqdown){
        updqdown(1, 1, sz(cc), tme, tme, pos, id);
    }
    
    dfs(1, 1, sz(cc));
    for(int i = 1; i <= q; i++){
        cout << ((ans[i] > 100000000) ? -1 : ans[i]) << "\n";
    }
    
}


signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("test.in", "r", stdin);
    //freopen("test.txt", "w", stdout);
    
    int tt; tt = 1;
    while(tt--)solve();
    return(0);
}

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