Submission #107440

#	Time	Username	Problem	Language	Result	Execution time	Memory
107440		lyc	New Home (APIO18_new_home)	C++14	100 / 100	3743 ms	109996 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 3e5+10;
const int MAXK = 3e5+10;
const int MAXQ = 3e5+10;

const int MX_X = 1e8+10;
const int MX_Y = 1e8+10;

// Input Data
struct Store {
    int i, x, t, a, b;
} stores[MAXN];
struct Query {
    int i, l, y, ans;
} queries[MAXQ];

//
struct StoreEvent {
    int x, y, type;
    // type: 0 (open), 1 (close) };
};

vector<StoreEvent> events[MAXK];

struct OpenStore {
    int cnt, negRay, posRay;

    OpenStore(): cnt(1) {}
};

struct Ray {
    int h, xh, xi, a, b;

    Ray(int x1, int x2, int m, int y) {
        a = y; b = -1;
        h = (x2-x1)/2;
        if (m > 0) xi = x1;
        else xi = x2;
        xh = xi + h*m;
    }

    void close(int y) { b = y-1; }
};

struct Seg {
    int s, e, m, v[2];
    Seg *l, *r;
    Seg(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), l(nullptr), r(nullptr) {
        v[0] = v[1] = -MX_X * 2;
        if (s != e) {
            l = new Seg(s, m);
            r = new Seg(m+1, e);
        }
    }

    void update(int x, int y, int val, int t) {
        //cout << "UPDATE " << x << " " << y << " of " << s << " " << e << endl;
        if (y < x) return;

        if (s == x and e == y) v[t] = max(v[t], val);
        else if (y <= m) l->update(x, y, val, t);
        else if (x >  m) r->update(x, y, val, t);
        else l->update(x, m, val, t), r->update(m+1, y, val, t);
    } 

    int query(int x, int t) {
        if (s == e) return v[t];
        else if (x <= m) return max(v[t], l->query(x, t));
        else return max(v[t], r->query(x, t));
    }
} *root;

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, q; cin >> n >> k >> q;
    FOR(i,0,n-1){
        stores[i].i = i;
        cin >> stores[i].x >> stores[i].t >> stores[i].a >> stores[i].b;
    }

    vector<int> times;
    FOR(i,0,q-1){
        queries[i].i = i;
        queries[i].ans = -1;
        cin >> queries[i].l >> queries[i].y;

        times.push_back(queries[i].y);
    }

    times.push_back(0);
    times.push_back(MX_Y);
    // Discretize time
    sort(ALL(times));
    times.resize(unique(ALL(times))-times.begin());
    FOR(i,0,n-1){
        stores[i].a = lower_bound(ALL(times), stores[i].a) - times.begin();     // earliest ok
        stores[i].b = upper_bound(ALL(times), stores[i].b) - times.begin() - 1; // last ok
    }
    FOR(i,0,q-1){
        queries[i].y = lower_bound(ALL(times), queries[i].y) - times.begin();   // find its index
    }

    // Construct and sort all the store events by time for each type
    FOR(i,0,n-1){
        if (stores[i].b < stores[i].a) continue;

        events[stores[i].t].push_back({stores[i].x, stores[i].a, 0});
        events[stores[i].t].push_back({stores[i].x, stores[i].b+1, 1});
    }
    FOR(i,1,k){
        sort(ALL(events[i]), [](const StoreEvent &a, const StoreEvent &b) {
                    if (a.y == b.y) return a.type > b.type; // closing first
                    return a.y < b.y;
                });
    }
    //cout << "maybe" << endl;
    //FOR(i,1,k){
    //    for (StoreEvent e : events[i]) {
    //        cout << e.x << " " << e.y << " :: " << e.type << endl;
    //    }
    //    cout << endl;
    //}

    // Build the max function for each type, preserving each ray's time interval
    vector<Ray> negRays, posRays;   // stores all the rays
    FOR(i,1,k){
        map<int, OpenStore> openStores;
        openStores[-MX_X] = OpenStore();
        openStores[2*MX_X]= OpenStore();

        openStores[-MX_X].posRay = (int)posRays.size();
        posRays.push_back( Ray(-MX_X, 2*MX_X, 1, 0) );

        openStores[2*MX_X].negRay = (int)negRays.size();
        negRays.push_back( Ray(-MX_X, 2*MX_X, -1, 0) );
        //cout << "OK " << i << " :: " << negRays.size() << " " << posRays.size() << endl;

        for (StoreEvent e : events[i]) {
            auto it = openStores.lower_bound(e.x);
            //cout << "PROCESS " << e.x << " " << e.y << " type " << e.type << endl;

            //cout << "At time " << e.y << endl;
            //cout << '\t';
            //for (auto x : openStores) { cout << x.fi << " "; } cout << endl;
            if (e.type == 0) { // opening event
                if (it->fi == e.x) {
                    // store already exist. just increment counter
                    ++it->sc.cnt;
                } else {
                    assert(it != openStores.begin());   auto prv = prev(it);
                    assert(it != openStores.end());     auto nxt = it;

                    // no stores open here yet. create one
                    openStores[e.x] =  OpenStore();

                    openStores[e.x].negRay = (int)negRays.size();
                    negRays.push_back( Ray(prv->fi, e.x, -1, e.y) );
                    openStores[e.x].posRay = (int)posRays.size();
                    posRays.push_back( Ray(e.x, nxt->fi, 1, e.y) );

                    negRays[nxt->sc.negRay].close(e.y);
                    //cout << "CLOSE " << e.y << " NEG " << nxt->sc.negRay << endl;
                    nxt->sc.negRay = (int)negRays.size();
                    negRays.push_back( Ray(e.x, nxt->fi, -1, e.y) );

                    posRays[prv->sc.posRay].close(e.y);
                    //cout << "CLOSE " << e.y << " POS " << prv->sc.posRay << endl;
                    prv->sc.posRay = (int)posRays.size();
                    posRays.push_back( Ray(prv->fi, e.x, 1, e.y) );
                }
            } else {
                assert(it->fi == e.x);  // a store should exist
                if (it->sc.cnt > 1) {
                    // won't delete any rays
                    --it->sc.cnt;
                } else {
                    assert(it != openStores.begin());   auto prv = prev(it);
                    assert(next(it) != openStores.end());     auto nxt = next(it);

                    // get rid of the store here
                    negRays[it->sc.negRay].close(e.y);
                    posRays[it->sc.posRay].close(e.y);
                    //cout << "CLOSE " << e.y << " HERE NEG " << it->sc.negRay << endl;
                    //cout << "CLOSE " << e.y << " HERE POS " << it->sc.posRay << endl;

                    openStores.erase(it);

                    negRays[nxt->sc.negRay].close(e.y);
                    //cout << "CLOSE " << e.y << " NEG " << nxt->sc.negRay << endl;
                    nxt->sc.negRay = (int)negRays.size();
                    negRays.push_back( Ray(prv->fi, nxt->fi, -1, e.y) );

                    posRays[prv->sc.posRay].close(e.y);
                    //cout << "CLOSE " << e.y << " POS " << prv->sc.posRay << endl;
                    prv->sc.posRay = (int)posRays.size();
                    posRays.push_back( Ray(prv->fi, nxt->fi, 1, e.y) );
                }
            }
        }

        //cout << "CLOSE " << times.size()-1 << " POS " << openStores[-MX_X].posRay << endl;
        //cout << "CLOSE " << times.size()-1 << " NEG " << openStores[2*MX_X].negRay << endl;
        posRays[openStores[-MX_X].posRay].close((int)times.size()-1);
        negRays[openStores[2*MX_X].negRay].close((int)times.size()-1);
        //cout << openStores.size() << endl;
        //cout << "SHOULD CLOSE UP TO " << negRays.size() << " " << posRays.size() << endl;
    }

    // Now process the queries
    root = new Seg(0, (int)times.size()-1);
    sort(ALL(negRays), [](const Ray &a, const Ray &b) { return a.xh < b.xh; });
    sort(queries, queries+q, [](const Query &a, const Query &b) { return a.l < b.l; });

    //for (Ray r : negRays) {
    //    cout << "neg ray " << r.xh << " " << r.xi << " from time " << r.a << " to " << r.b << endl;
    //}
    //for (Ray r : posRays) {
    //    cout << "pos ray " << r.xh << " " << r.xi << " from time " << r.a << " to " << r.b << endl;
    //}

    auto it = negRays.begin();
    FOR(i,0,q-1){
        while (it != negRays.end() && it->xh <= queries[i].l) {
            if (it->a <= it->b) {
                //cout << "UPDATE TIME " << it->a << " - " << it->b << " by " << it->xi << endl;
                root->update(it->a, it->b, it->xi, 0);
            }
            ++it;
        }
        //cout << "QUERY " << queries[i].y << " RAY " << root->query(queries[i].y, 0) << endl;
        queries[i].ans = root->query(queries[i].y, 0) - queries[i].l;
    }

    sort(ALL(posRays), [](const Ray &a, const Ray &b) { return a.xh > b.xh; });
    sort(queries, queries+q, [](const Query &a, const Query &b) { return a.l > b.l; });

    it = posRays.begin();
    FOR(i,0,q-1){
        while (it != posRays.end() && it->xh >= queries[i].l) {
            if (it->a <= it->b) {
                root->update(it->a, it->b, -it->xi, 1);
            }
            ++it;
        }
        queries[i].ans = max(queries[i].ans, queries[i].l + root->query(queries[i].y, 1));
    }

    sort(queries, queries+q, [](const Query &a, const Query &b) { return a.i < b.i; });
    FOR(i,0,q-1){
        cout << (queries[i].ans < MX_X ? queries[i].ans : -1) << endl;
    }
}

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