Submission #1136988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136988		OI_Account	New Home (APIO18_new_home)	C++17	57 / 100	5115 ms	551732 KiB

new_home

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

const int N = 300'000;
const int INF = 1'000'000'000;
const int A = 5'000'000;

int n, k, q, len;
bool mark[A + 10], isDel[N + 10];
int x[N + 10], t[N + 10], a[N + 10], b[N + 10];
int l[N + 10], y[N + 10], ans[N + 10];
vector<int> st[N + 10], en[N + 10];
set<int> s1[N + 10], s2[N + 10];
set<pair<int, int>> s[N + 10];
vector<pair<int, int>> last[N + 10];
priority_queue<pair<int, int>> mx[4 * N + 10];
priority_queue<pair<int, int>> mn[4 * N + 10];
vector<int> query[N + 10], cmpTim, cmp;
int counter, cntType[N + 10], cntZero;

void readInput() {
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> t[i] >> a[i] >> b[i];
    for (int i = 1; i <= q; i++)
        cin >> l[i] >> y[i];
}

void CMP(vector<int> &cmp) {
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
}

int getIdxVec(vector<int> &vec, int x) {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

int getIdxLast(int t, int x) {
    return lower_bound(last[t].begin(), last[t].end(), make_pair(x, 0)) - last[t].begin();
}

void calcCmp() {
    for (int i = 1; i <= q; i++) {
        cmp.push_back(l[i]);
        cmpTim.push_back(y[i]);
    }
    CMP(cmp);
    CMP(cmpTim);
    for (int i = 1; i <= q; i++) {
        l[i] = getIdxVec(cmp, l[i]);
        y[i] = getIdxVec(cmpTim, y[i]);
    }
    for (int i = 1; i <= n; i++) {
        a[i] = getIdxVec(cmpTim, a[i]);
        b[i] = getIdxVec(cmpTim, b[i] + 1);
        last[t[i]].push_back({x[i], 0});
    }
    for (int i = 1; i <= k; i++) {
        sort(last[i].begin(), last[i].end());
        last[i].resize(unique(last[i].begin(), last[i].end()) - last[i].begin());
    }
    len = (int) cmp.size() - 1;
}

void calcVec() {
    for (int i = 1; i <= n; i++)
        if (a[i] != b[i]) {
            st[a[i]].push_back(i);
            en[b[i]].push_back(i);
        }
    for (int i = 1; i <= q; i++) 
        query[y[i]].push_back(i);
}

/*void update(int st, int en, int val, int d, int id = 1, int l = 0, int r = len + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        mx[id].insert({val, d});
        return;
    }
    int mid = (l + r) >> 1;
    update(st, en, val, d, id << 1, l, mid);
    update(st, en, val, d, id << 1 | 1, mid, r);
}

void delBad(int id) {
    while (!mx[id].empty() && mark[mx[id].begin() -> second])
        mx[id].erase(mx[id].begin());
    while (!mx[id].empty() && mark[mx[id].rbegin() -> second])
        mx[id].erase(*mx[id].rbegin());
}

int calcTmp(int id, int idx) {
    delBad(id);
    int case1 = (mx[id].empty()? 0: abs(cmp[idx] - mx[id].begin() -> first));
    int case2 = (mx[id].empty()? 0: abs(cmp[idx] - mx[id].rbegin() -> first));
    return max(case1, case2);
}*/

void update(int st, int en, int val, int d, int id = 1, int l = 0, int r = len + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        mx[id].push({val, d});
        mn[id].push({-val, d});
        return;
    }
    int mid = (l + r) >> 1;
    update(st, en, val, d, id << 1, l, mid);
    update(st, en, val, d, id << 1 | 1, mid, r);
}

void delBad(int id) {
    while (!mx[id].empty() && mark[mx[id].top().second])
        mx[id].pop();
    while (!mn[id].empty() && mark[mn[id].top().second])
        mn[id].pop();
}

int calcTmp(int id, int idx) {
    delBad(id);
    int case1 = (mx[id].empty()? 0: abs(cmp[idx] - mx[id].top().first));
    int case2 = (mn[id].empty()? 0: abs(cmp[idx] + mn[id].top().first));
    return max(case1, case2);
}

int get(int idx, int id = 1, int l = 0, int r = len + 1) {
    if (idx < l || r <= idx)
        return 0;
    if (l + 1 == r)
        return calcTmp(id, idx);
    int mid = (l + r) >> 1;
    return max({calcTmp(id, idx), get(idx, id << 1, l, mid), get(idx, id << 1 | 1, mid, r)});
}

int getNext(int t, int x) {
    return *s1[t].upper_bound(x);
}

int getLast(int t, int x) {
    return -(*s2[t].upper_bound(-x));
}

pair<int, int> getSeg(int t, int x) {
    int lft = getLast(t, x);
    int rght = getNext(t, x);
    int resL = (lft == -1? 0: (lft + x + 1) / 2);
    int resR = (rght == INF? INF: (x + rght) / 2);
    return {getIdxVec(cmp, resL), getIdxVec(cmp, resR + 1)};
}

void change(int t, int x, int d) {
    if (x == -1 || x == INF)
        return;
    if (d == -1)
        mark[last[t][getIdxLast(t, x)].second] = true;
    else {
        pair<int, int> p = getSeg(t, x);
        last[t][getIdxLast(t, x)].second = ++counter;
        update(p.first, p.second, x, counter);
    }
}

void add(int t, int id) {
    int l = getLast(t, x[id]), r = getNext(t, x[id]);
    change(t, l, -1);
    change(t, r, -1);
    s[t].insert({x[id], id});
    s1[t].insert(x[id]);
    s2[t].insert(-x[id]);
    change(t, l, +1);
    change(t, r, +1);
    change(t, x[id], +1);
}

void del(int t, int id) {
    int l = getLast(t, x[id]), r = getNext(t, x[id]);
    change(t, l, -1);
    change(t, r, -1);
    change(t, x[id], -1);
    s[t].erase({x[id], id});
    s1[t].erase(x[id]);
    s2[t].erase(-x[id]);
    change(t, l, +1);
    change(t, r, +1);
    isDel[id] = true;
}

void init() {
    cntZero = k;
    for (int i = 1; i <= k; i++) {
        s1[i].insert(-1);
        s2[i].insert(1);

        s1[i].insert(INF);
        s2[i].insert(-INF);
    }
}

void changeCnt(int t, int d) {
    cntZero -= (cntType[t] == 0);
    cntType[t] += d;
    cntZero += (cntType[t] == 0);
}

void checkDel(int id) {
    changeCnt(t[id], -1);
    if (!isDel[id])
        del(t[id], id);
}

void checkAdd(int id) {
    changeCnt(t[id], +1);
    auto au = s[t[id]].lower_bound({x[id], -1});
    if (au != s[t[id]].end() && au -> first == x[id]) {
        int tmp = au -> second;
        if (b[tmp] < b[id]) {
            isDel[tmp] = true;
            s[t[id]].erase({x[tmp], tmp});
            s[t[id]].insert({x[id], id});
        }
        else
            isDel[id] = true;
    }
    else
        add(t[id], id);
}

void checkQuery(int id) {
    ans[id] = get(l[id]);
    if (cntZero)
        ans[id] = -1;
}

void calcAns() {
    for (int i = 0; i < cmpTim.size(); i++) {
        for (auto id: en[i])
            checkDel(id);
        for (auto id: st[i])
            checkAdd(id);
        for (auto id: query[i])
            checkQuery(id);
    }
}

void writeOutput() {
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcCmp();
    calcVec();
    init();
    calcAns();
    writeOutput();
    return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

/*
2 2 1
3 1 1 10
9 2 2 4
5 9
*/

/*
4 2 2
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 9
*/

/*
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

*/

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