oj.uz

답안 #107433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107433 2019-04-24T09:52:53 Z lyc 새 집 (APIO18_new_home) C++14
10 / 100
 2405 ms 121252 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 MAXY = 3e5+10;

const int MX_X = 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(MAXY);
    // 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){
        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 9 ms 7424 KB Output is correct
2 Runtime error 17 ms 14592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1963 ms 111424 KB Output is correct
2 Correct 2203 ms 104104 KB Output is correct
3 Correct 2044 ms 120340 KB Output is correct
4 Correct 1830 ms 113048 KB Output is correct
5 Correct 2405 ms 103284 KB Output is correct
6 Correct 2139 ms 104020 KB Output is correct
7 Correct 1783 ms 120360 KB Output is correct
8 Correct 1690 ms 112264 KB Output is correct
9 Correct 2001 ms 109636 KB Output is correct
10 Correct 1831 ms 106140 KB Output is correct
11 Correct 1334 ms 103300 KB Output is correct
12 Correct 1341 ms 106016 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 690 ms 121252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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