Submission #66480

#	Time	Username	Problem	Language	Result	Execution time	Memory
66480		Benq	New Home (APIO18_new_home)	C++14	100 / 100	4053 ms	472956 KiB

new_home

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 300001;

void checkmx(int& a, int b) { a = max(a,b); }
void checkmn(int& a, int b) { a = min(a,b); }

int getPos(vi& v, int x) { return ub(all(v),x)-v.begin()-1; }

template<int SZ> struct seg {
    vector<array<int,4>> todo; // query minimum, interval min operations
    vi num;
    int mn[SZ];
    
    void build(int ind, int L, int R) {
        mn[ind] = 2*MOD; 
        if (L == R) return;
        int M = (L+R)/2;
        build(2*ind,L,M); build(2*ind+1,M+1,R);
    }
    
    void build() {
        num.pb(-MOD);
        for (auto a: todo) num.pb(a[2]), num.pb(a[3]+1);
        sort(all(num)); num.erase(unique(all(num)),num.end());
        build(1,0,sz(num)-1);
    }
    
    void modify(int x, int y, int t, int ind, int L, int R) {
        if (R < x || y < L) return;
        if (x <= L && R <= y) { checkmn(mn[ind],t); return; }
        int M = (L+R)/2;
        modify(x,y,t,2*ind,L,M);
        modify(x,y,t,2*ind+1,M+1,R);
    }
    
    void modify(int x, int y, int t) {
        // cout << "OOPS " << x << " " << y << " " << t << " " << getPos(num,x) << " " << getPos(num,y) << "\n";
        modify(getPos(num,x),getPos(num,y),t,1,0,sz(num)-1);
    }
    
    int query(int x, int ind, int L, int R) {
        int ret = mn[ind];
        if (L != R) {
            int M = (L+R)/2;
            if (x <= M) checkmn(ret,query(x,2*ind,L,M));
            else checkmn(ret,query(x,2*ind+1,M+1,R));
        }
        return ret;
    }
    int query(int x) { 
        return query(getPos(num,x),1,0,sz(num)-1); 
    }
};

int n,k,q, ans[MX];

seg<1<<21> S[2];
map<pi,int> type[MX];
vector<array<int,5>> mod;
vector<array<int,3>> query;

ostream& operator <<(ostream& os, const pair<pi,int>& p) {
    os << p.f.f << " " << p.f.s << " " << p.s << " | ";
    return os;
}

void ins(int x, pair<pi,int> a, pair<pi,int> b) {
    // cout << x << " | " << a << b << "\n";
    if (a.f.f == -MOD && b.f.f == MOD) {
        S[0].todo.pb({MOD,-MOD,a.s,x});
        S[1].todo.pb({-MOD,MOD,a.s,x});
    } else {
        S[0].todo.pb({(a.f.f+b.f.f)/2,a.f.f,a.s,x}); // all x <= (a.f.f+b.f.f)/2
        S[1].todo.pb({(a.f.f+b.f.f)/2+1,b.f.f,a.s,x});
    }
}

pair<pi,int> getNex(auto& a, auto b) {
    b = next(b);
    if (b == a.end()) return {{MOD,-1},1};
    return *b;
}

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> q;
	F0R(i,n) {
		int x,t,a,b; cin >> x >> t >> a >> b;
		mod.pb({a,1,t,x,i});
		mod.pb({b+1,-1,t,x,i});
	}   
	FOR(i,1,k+1) type[i][{-MOD,-1}] = 1;
	sort(all(mod));
	for (auto a: mod) {
	    pi t = {a[3],a[4]};
	    if (a[1] == 1) {
	        type[a[2]][t] = 0;
	        auto it = type[a[2]].find(t);
	        ins(a[0]-1,*prev(it),getNex(type[a[2]],it));
	        prev(it)->s = it->s = a[0];
	    } else {
	        auto it = type[a[2]].find(t);
	        ins(a[0]-1,*prev(it),*it);
	        ins(a[0]-1,*it,getNex(type[a[2]],it));
	        prev(it)->s = a[0];
	        type[a[2]].erase(it);
	    }
	}
	FOR(i,1,k+1) ins(1e8,*type[i].begin(),getNex(type[i],type[i].begin()));
}

void solve0() {
	sort(query.rbegin(),query.rend());
	S[0].build();
    sort(all(S[0].todo));
    for (auto a: query) {
        while (sz(S[0].todo)) {
            auto x = S[0].todo.back();
            if (x[0] < a[0]) break;
            S[0].modify(x[2],x[3],x[1]);
            S[0].todo.pop_back();
        }
        checkmx(ans[a[2]],a[0]-S[0].query(a[1]));
    }
}

void solve1() {
    reverse(all(query));
    S[1].build();
    sort(all(S[1].todo)); reverse(all(S[1].todo));
    for (auto a: query) {
        while (sz(S[1].todo)) {
            auto x = S[1].todo.back();
            if (x[0] > a[0]) break;
            S[1].modify(x[2],x[3],-x[1]);
            S[1].todo.pop_back();
        }
        checkmx(ans[a[2]],-S[1].query(a[1])-a[0]);
    }
}

int main() {
    init();
	F0R(i,q) {
		int l,y; cin >> l >> y;
		query.pb({l,y,i});
	}
	solve0();
	solve1();
	F0R(i,q) {
	    if (ans[i] > (1e8)) cout << -1;
	    else cout << ans[i];
	    cout << "\n";
	}
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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