Submission #1166030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166030		anmattroi	New Home (APIO18_new_home)	C++20	15 / 100	5095 ms	317200 KiB

new_home

#include <bits/stdc++.h>
#define maxn 300005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

const int MAX = 1'00'000'000;

int n, k, q;

struct store {int x, t, a, b;} stores[maxn];
struct query {int l, y;} queries[maxn];

int years[maxn]; int ysz = 0;

map<int, int> stor[maxn];

int bit[maxn], tib[maxn];

int coordinates[maxn], csz = 0;

struct node {
    int val = 0;
    vector<ii> TraceL, TraceR;
    node() {}
    node(int _val) : val(_val) {}
};

struct curry {
    int type, store_type, pos;
    curry() {}
    curry(int _type, int _store_type, int _pos) : type(_type), store_type(_store_type), pos(_pos) {}
};


void upd_negative_slope(int pos, node &t) {
    int p = lower_bound(coordinates+1,coordinates+csz+1, pos) - coordinates;
    for (int i = p; i <= csz; i++) if (bit[i] < pos+t.val) {
        t.TraceL.emplace_back(i, bit[i]);
        bit[i] = pos+t.val;
    }
}

void upd_positive_slope(int pos, node &t) {
    int p = upper_bound(coordinates+1,coordinates+csz+1, pos) - coordinates-1;
    for (int i = p; i >= 1; i--) if (tib[i] < t.val-pos) {
        t.TraceR.emplace_back(i, tib[i]);
        tib[i] = t.val-pos;
    }
}

void add_negative_slope(int p, int h) {
    int o = lower_bound(coordinates+1,coordinates+csz+1, p) - coordinates;
    for (int i = o; i <= csz; i += i & -i) bit[i] = max(bit[i], p+h);
}

void add_positive_slope(int p, int h) {
    int o = upper_bound(coordinates+1,coordinates+csz+1, p) - coordinates - 1;
    for (int i = o; i >    0; i -= i & -i) tib[i] = max(tib[i], h-p);
}

vector<curry> st[4*maxn];
vector<node>  it[4*maxn];

void add_update(int u, int v, const curry &t, int r = 1, int lo = 1, int hi = ysz) {
    if (u <= lo && hi <= v) {
        st[r].emplace_back(t);
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) add_update(u, v, t, r<<1, lo, mid);
    if (v  > mid) add_update(u, v, t, r<<1|1,mid+1,hi);
}


int number_of_available;

int ans[maxn];

int get_bit(int u) {
    int kq = INT_MIN/10;
    for (int i = u; i > 0; i -= i & -i) kq = max(kq, bit[i]);
    return kq;
}

int get_tib(int u) {
    int kq = INT_MIN/10;
    for (int i = u; i <= csz; i += i & -i) kq = max(kq, tib[i]);
    return kq;
}

void dfs(int r = 1, int lo = 1, int hi = ysz) {
    for (curry &cur : st[r])
        if (cur.type == 1) {
            map<int, int> &cr = stor[cur.store_type];
            if (--cr[cur.pos] > 0) continue;
            cr.erase(cur.pos);
            if (cr.empty()) {
                --number_of_available;
                continue;
            }
            auto ptr = cr.lower_bound(cur.pos);
            if (ptr == cr.end()) {
                --ptr;
                it[r].emplace_back(MAX-ptr->fi);
                upd_positive_slope(MAX, it[r].back());
            } else if (ptr == cr.begin()) {
                it[r].emplace_back(ptr->fi-1);
                upd_negative_slope(1, it[r].back());
            } else {
                int A = prev(ptr)->fi, B = ptr->fi;
                int mid = (A+B)>>1;
                it[r].emplace_back(mid-A);
                upd_positive_slope(mid, it[r].back());
                it[r].back().val = B-(mid+1);
                upd_negative_slope(mid+1, it[r].back());
            }
        } else {
            if (number_of_available != k) {
                ans[cur.store_type] = -1;
                continue;
            }
            int p = lower_bound(coordinates+1,coordinates+csz+1, cur.pos)-coordinates;
            ans[cur.store_type] = max(get_bit(p)-cur.pos, cur.pos+get_tib(p));
        }

    if (lo != hi) {
        int mid = (lo + hi) >> 1;
        dfs(r<<1, lo, mid);
        dfs(r<<1|1, mid+1, hi);
    }
    int sz = it[r].size();
    for (int i = sz-1; i >= 0; i--) {
        for (auto [pos, oldval] : it[r][i].TraceL) bit[pos] = oldval;
        for (auto [pos, oldval] : it[r][i].TraceR) tib[pos] = oldval;
    }
    for (curry &cur : st[r])
        if (cur.type == 1) {
            if (stor[cur.store_type].empty()) ++number_of_available;
            ++stor[cur.store_type][cur.pos];
        }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    coordinates[++csz] = 1;
    coordinates[++csz] = MAX;

    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) {
        cin >> stores[i].x >> stores[i].t >> stores[i].a >> stores[i].b;
        ++stor[stores[i].t][stores[i].x];
    }
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].l >> queries[i].y;
        years[++ysz] = queries[i].y;
        coordinates[++csz] = queries[i].l;
    }
    sort(years + 1, years + ysz + 1);
    ysz = unique(years + 1, years + ysz + 1) - years - 1;

    sort(coordinates + 1, coordinates + csz + 1);
    csz = unique(coordinates + 1, coordinates + csz + 1) - coordinates - 1;

    for (int i = 1; i <= csz; i++) bit[i] = tib[i] = INT_MIN/10;

    for (int type = 1; type <= k; type++) {
        if (stor[type].empty()) {
            for (int i = 1; i <= q; i++) cout << "-1\n";
            exit(0);
        }
        for (auto it = next(stor[type].begin()); it != stor[type].end(); it++) {
            int A = prev(it)->fi, B = it->fi;
            int mid = (A + B) >> 1;
            add_positive_slope(mid, mid-A);
            add_negative_slope(mid+1, B-(mid+1));
        }

        if (1) {
            int B = stor[type].begin()->fi;
            add_negative_slope(1, B-1);
        }

        if (1) {
            int B = stor[type].rbegin()->fi;
            add_positive_slope(MAX, MAX-B);
        }
    }

    number_of_available = k;
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(years + 1, years + ysz + 1, stores[i].a) - years - 1,
            q = upper_bound(years + 1, years + ysz + 1, stores[i].b) - years;
        if (p + 1 == q) {
            add_update(1, ysz, curry(1, stores[i].t, stores[i].x));
            continue;
        }
        if (1<=  p) add_update(1, p, curry(1, stores[i].t, stores[i].x));
        if (q<=ysz) add_update(q,ysz,curry(1, stores[i].t, stores[i].x));
    }
    for (int i = 1; i <= q; i++) {
        int p = lower_bound(years + 1, years + ysz + 1, queries[i].y) - years;
        add_update(p, p, curry(2, i, queries[i].l));
    }
    dfs();

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";

}

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