Submission #1118798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118798		OI_Account	New Home (APIO18_new_home)	C++17	47 / 100	5070 ms	529808 KiB

new_home

#pragma GCC optimize("O2,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;

const int N = 300'000;
const int S = 3 * N;
const int INF = 1'000'000'000;

int n, k, q, len, mark[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> cmp, st[S + 10], en[S + 10];
set<pair<int, pair<int, int>>> s[N + 10];
set<pair<int, int>> s1[N + 10], s2[N + 10];
multiset<int> ms[4 * (2 * N + 1) + 10];
pair<int, pair<int, int>> p[N + 10];
vector<int> query[S + 10], cmpTim;

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 calcCmp() {
    cmp = {-INF, INF};
    for (int i = 1; i <= n; i++) {
        cmp.push_back(x[i]);
        cmpTim.push_back(a[i]);
        cmpTim.push_back(b[i]);
    }
    for (int i = 1; i <= q; i++) {
        cmp.push_back(l[i]);
        cmpTim.push_back(y[i]);
    }
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
    sort(cmpTim.begin(), cmpTim.end());
    cmpTim.resize(unique(cmpTim.begin(), cmpTim.end()) - cmpTim.begin());
    len = (int) cmp.size() - 1;
}

int getLow(int x) {
    return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}

int getLowTim(int x) {
    return lower_bound(cmpTim.begin(), cmpTim.end(), x) - cmpTim.begin();
}

void calcVec() {
    for (int i = 1; i <= n; i++) {
        st[getLowTim(a[i])].push_back(i);
        en[getLowTim(b[i])].push_back(i);
    }
    for (int i = 1; i <= q; i++)
        query[getLowTim(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) {
        if (d == 1)
            ms[id].insert(val);
        else
            ms[id].erase(ms[id].lower_bound(val));
        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);
}

int calcTmp(int id, int idx) {
    if (ms[id].size() == 0)
        return -INF;
    int mn = *ms[id].begin(), mx = *ms[id].rbegin();
    if (mn == -INF || mx == INF)
        return INF;
    return max(abs(cmp[idx] - mn), abs(cmp[idx] - mx));
}

int get(int idx, int id = 1, int l = 0, int r = len + 1) {
    if (idx < l || r <= idx)
        return -INF;
    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)});
}

void upd(int l, int r, int val, int d) {
    int idxL = getLow(l);
    int idxR = getLow(r + 1);
    update(idxL, idxR, val, d);
}

void upd(int i, int j, int d) {
    int mid = (x[i] + x[j]) / 2;
    upd(x[i], mid, x[i], d);
    upd(mid + 1, x[j], x[j], d);
}

int getR(int id) {
    return s1[t[id]].lower_bound({x[id] + 1, -1}) -> second;
}

int getL(int id) {
    return s2[t[id]].lower_bound({-x[id] + 1, -1}) -> second;
}

void add(int id) {
    //cout << "add " << id << endl;
    int i = getL(id), j = getR(id);
    //cout << "idx " << i << ' ' << j << endl;
    upd(i, j, -1);
    upd(i, id, 1);
    upd(id, j, 1);
    s[t[id]].insert({x[id], {b[id], id}});
    s1[t[id]].insert({x[id], id});
    s2[t[id]].insert({-x[id], id});
    mark[id] = true;
    //cout << "added " << endl;
}

void del(int id) {
    //cout << "del " << id << endl;
    int i = getL(id), j = getR(id);
    //cout << " idx = " << i << ' ' << j << endl;
    upd(i, id, -1);
    upd(id, j, -1);
    upd(i, j, 1);
    s[t[id]].erase({x[id], {b[id], id}});
    s1[t[id]].erase({x[id], id});
    s2[t[id]].erase({-x[id], id});
    mark[id] = false;
    //cout << "deleted" << endl;
}

void init() {
    x[n + 1] = -INF;
    x[n + 2] = +INF;
    for (int i = 1; i <= k; i++) {
        for (int j = n + 1; j <= n + 2; j++) {
            s1[i].insert({x[j], j});
            s2[i].insert({-x[j], j});
        }
        upd(n + 1, n + 2, 1);
    }
}

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

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

void calcAns() {
    for (int i = 0; i < cmpTim.size(); i++) {
        for (auto id: st[i])
            checkAdd(id);
        for (auto id: query[i])
            checkQuery(id);
        for (auto id: en[i])
            if (mark[id])
                del(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

*/

Compilation message (stderr)

new_home.cpp: In function 'void calcAns()':
new_home.cpp:175:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for (int i = 0; i < cmpTim.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

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