oj.uz

답안 #107435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107435 2019-04-24T09:59:45 Z lyc 새 집 (APIO18_new_home) C++14
33 / 100
 3141 ms 119348 KB 
#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){
        if (stores[i].a >= stores[i].b) continue;
        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) {
            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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Runtime error 21 ms 14620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Runtime error 21 ms 14620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1948 ms 97980 KB Output is correct
2 Correct 2005 ms 91392 KB Output is correct
3 Correct 2066 ms 106656 KB Output is correct
4 Correct 2021 ms 99312 KB Output is correct
5 Correct 2459 ms 90828 KB Output is correct
6 Correct 2601 ms 91440 KB Output is correct
7 Correct 1965 ms 106304 KB Output is correct
8 Correct 1899 ms 98568 KB Output is correct
9 Correct 1908 ms 96196 KB Output is correct
10 Correct 2059 ms 93292 KB Output is correct
11 Correct 1578 ms 90772 KB Output is correct
12 Correct 1508 ms 93064 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3092 ms 94476 KB Output is correct
2 Correct 725 ms 33380 KB Output is correct
3 Correct 3007 ms 103892 KB Output is correct
4 Correct 2977 ms 118180 KB Output is correct
5 Correct 2879 ms 109540 KB Output is correct
6 Correct 2975 ms 111052 KB Output is correct
7 Correct 3141 ms 102972 KB Output is correct
8 Correct 2699 ms 103712 KB Output is correct
9 Correct 2729 ms 119348 KB Output is correct
10 Correct 2623 ms 111472 KB Output is correct
11 Correct 2596 ms 108660 KB Output is correct
12 Correct 2654 ms 105544 KB Output is correct
13 Correct 1582 ms 101932 KB Output is correct
14 Correct 1540 ms 101320 KB Output is correct
15 Correct 1654 ms 103168 KB Output is correct
16 Correct 1727 ms 105684 KB Output is correct
17 Correct 1908 ms 102456 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Runtime error 21 ms 14620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Runtime error 21 ms 14620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -