Submission #354431

#	Time	Username	Problem	Language	Result	Execution time	Memory
354431		12tqian	New Home (APIO18_new_home)	C++17	100 / 100	3999 ms	167656 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; i++)
#define f0r(i, a) f1r(i, 0, a)
#define trav(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

typedef vector<int> vi; 
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;

const int N = 3e5 + 1;
const int M = (1 << 21);
const int INF = 1e9;

template <class T> bool ckmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, T b) { return a < b ? a = b, 1 : 0; }


int get_pos(vi& v, int x) { return upper_bound(all(v), x) - v.begin(); }

template <int N> struct SegmentTree {
    vector<array<int, 4>> todo;
    // loc to loc, time to time
    vi num;
    int mn[N];

    void build(int ind, int L, int R) {
        mn[ind] = 2 * INF;
        if (L == R) return;
        int M = (L + R) >> 1;
        build(2*ind, L, M);
        build(2*ind+1, M+1, R);
    }

    void build() {
        num.pb(-INF);
        trav(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) {
            ckmin(mn[ind], t);
            return;
        }
        int M = (L + R) >> 1;
        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) {
        modify(get_pos(num, x), get_pos(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) >> 1;
            if (x <= M) {
                ckmin(ret, query(x, 2*ind, L, M));
            } else {
                ckmin(ret, query(x, 2*ind+1, M+1, R));
            }
        }
        return ret;
    }
    int query(int x) {
        return query(get_pos(num, x), 1, 0, sz(num)-1);
    }

};


int n, k, q; 
int ans[N]; // stores answers
map<pi, int> type[N];
vector<array<int, 5>> mod; // modifications
vector<array<int, 3>> query; // queries
SegmentTree<M> S[2];


void insert(int x, pair<pi, int> a, pair<pi, int> b) {
    if (a.f.f == -INF && b.f.f == INF) {
        S[0].todo.pb({INF, -INF, a.s, x});
        S[1].todo.pb({-INF, INF, a.s, x});
    } else {
        int m = (a.f.f+b.f.f) >> 1;
        S[0].todo.pb({m, a.f.f, a.s, x});
        S[1].todo.pb({m+1, b.f.f, a.s, x});
    }
}
pair<pi, int> get_next(map<pi, int>& a, map<pi, int>::iterator b) {
    b = next(b);
    if (b == a.end()) return {{INF, -1}, 1};
    else return *b;
}

void init() {
    cin.tie(0)->sync_with_stdio();
    cin >> n >> k >> q;
    f0r(i, n) {
        int x, t, a, b; cin >> x >> t >> a >> b;
        mod.push_back({a, 1, t, x, i});
        mod.push_back({b+1, -1, t, x, i});
    }
    f1r(i, 1, k+1) {
        type[i][{-INF, -1}] = 1;
    }
    sort(all(mod));
    trav(a, mod) {
        pi t = {a[3], a[4]};
        if (a[1] == 1) { // adding something
            type[a[2]][t] = 0;
            auto it = type[a[2]].find(t);
            insert(a[0]-1, *prev(it), get_next(type[a[2]], it)); // adds the things that ended
            prev(it)->s = it->s = a[0]; // this is when they started a new thing
        } else { // removing something
            auto it = type[a[2]].find(t);
            insert(a[0]-1, *prev(it), *it); 
            insert(a[0]-1, *it, get_next(type[a[2]], it));
            prev(it)->s = a[0]; // set previous time
            type[a[2]].erase(it); // get rid of thing
        }
    }
    f1r(i, 1, k+1) {
        insert(1e8, *type[i].begin(), get_next(type[i], type[i].begin())); // set the remainder that didn't get removed, which is the negative infinity
        // this is so we don't ever have nothing?
        // figure this out
    }
    
    f0r(i, q) {
        int l, y; cin >> l >> y;
        query.pb({l, y, i});
    }
} 
void solve0() {
    sort(query.rbegin(), query.rend());
    S[0].build();
    sort(all(S[0].todo));
    trav(a, query) {
        while (sz(S[0].todo)) {
            auto x = S[0].todo.back();
            if (x[0] < a[0]) break; // doesn't affect
            S[0].modify(x[2], x[3], x[1]);
            S[0].todo.pop_back();
        }
        ckmax(ans[a[2]], a[0]-S[0].query(a[1]));
    }
}
void solve1() {
    reverse(all(query));
    S[1].build();
    sort(S[1].todo.rbegin(), S[1].todo.rend());
    trav(a, query) {
        while (sz(S[1].todo)) {
            auto x = S[1].todo.back();
            if (x[0] > a[0]) break; // doesn't apply
            S[1].modify(x[2], x[3], -x[1]);
            S[1].todo.pop_back();
        }
        ckmax(ans[a[2]], -S[1].query(a[1])-a[0]);
    }

}
int main() {
    init();
    solve0();
    solve1();
    f0r(i, q) {
        if (ans[i] > 1e8) cout << -1;
        else cout << ans[i];
        cout << '\n';
    }
    return 0;
}

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