Submission #1118897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118897		OI_Account	New Home (APIO18_new_home)	C++17	47 / 100	5064 ms	389116 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, qq, len, mark[N + 10];
int f[N + 10], g[N + 10], p[2][N + 10], q[2][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];
vector<int> query[S + 10], cmpTim;
vector<int> vec[N + 10];

void readInput() {
    cin >> n >> k >> qq;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> t[i] >> a[i] >> b[i];
    for (int i = 1; i <= qq; 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 <= qq; 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 <= qq; 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 checkL(int t) {
    upd(p[0][t], q[0][t], -INF, -1);
    p[0][t] = -INF;
    int val = s1[t].lower_bound({-INF + 1, -1}) -> first;
    q[0][t] = (-INF + val) / 2;
    upd(p[0][t], q[0][t], -INF, 1);
}

void checkR(int t) {
    upd(p[1][t], q[1][t], INF, -1);
    q[1][t] = INF;
    int val = -(s2[t].lower_bound({-INF + 1, -1}) -> first);
    p[1][t] = (INF + val) / 2 + 1;
    upd(p[1][t], q[1][t], INF, 1);
}

void check(int id, int type) {
    if (id > n) {
        if (id == n + 1)
            checkL(type);
        else
            checkR(type);
        return;
    }
    if (mark[id])
        upd(f[id], g[id], x[id], -1);
    int i = getL(id), j = getR(id);
    int midL = (x[i] + x[id]) / 2;
    int midR = (x[id] + x[j]) / 2;
    f[id] = midL + 1;
    g[id] = midR;
    upd(f[id], g[id], x[id], 1);
}

void add(int id) {
    //cout << "add " << id << endl;
    int i = getL(id), j = getR(id);
    //cout << "idx " << i << ' ' << j << endl;
    s[t[id]].insert({x[id], {b[id], id}});
    s1[t[id]].insert({x[id], id});
    s2[t[id]].insert({-x[id], id});
    check(id, t[id]);
    check(i, t[id]);
    check(j, t[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;
    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;
    upd(f[id], g[id], x[id], -1);
    check(i, t[id]);
    check(j, t[id]);
    //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(-INF, 0, -INF, 1);
        upd(1, INF, INF, 1);
        p[0][i] = -INF; q[0][i] = 0;
        p[1][i] = 1; q[1][i] = INF;
    }
}
    
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 <= qq; i++)
        cout << ans[i] << '\n';
    cout.flush();
}
    
bool isSub3() {
    for (int i = 1; i <= qq; i++)
        if (a[i] != 1 || b[i] != 100'000'000)
            return false;
    return true;
}

int mx[4 * S + 10];
int mn[4 * S + 10];

void updateMax(int st, int en, int val, int id = 1, int l = 0, int r = len + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        mx[id] = max(mx[id], val);
        return;
    }
    int mid = (l + r) >> 1;
    updateMax(st, en, val, id << 1, l, mid);
    updateMax(st, en, val, id << 1 | 1, mid, r);
}

int getMax(int idx, int id = 1, int l = 0, int r = len + 1) {
    if (idx < l || r <= idx)
        return -INF;
    if (l + 1 == r)
        return mx[id];
    int mid = (l + r) >> 1;
    return max({mx[id], getMax(idx, id << 1, l, mid), getMax(idx, id << 1 | 1, mid, r)});
}

void updateMin(int st, int en, int val, int id = 1, int l = 0, int r = len + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        mn[id] = min(mn[id], val);
        return;
    }
    int mid = (l + r) >> 1;
    updateMin(st, en, val, id << 1, l, mid);
    updateMin(st, en, val, id << 1 | 1, mid, r);
}

int getMin(int idx, int id = 1, int l = 0, int r = len + 1) {
    if (idx < l || r <= idx)
        return +INF;
    if (l + 1 == r)
        return mn[id];
    int mid = (l + r) >> 1;
    return min({mn[id], getMin(idx, id << 1, l, mid), getMin(idx, id << 1 | 1, mid, r)});
}

void addd(int l, int r, int val) {
    int idxL = getLow(l);
    int idxR = getLow(r + 1);
    updateMax(idxL, idxR, val);
    updateMin(idxL, idxR, val);
}

void solveSub3() {
    for (int i = 1; i <= n; i++)
        vec[t[i]].push_back(x[i]);
    for (int i = 1; i <= k; i++) {
        vec[i].push_back(-INF);
        vec[i].push_back(+INF);
        sort(vec[i].begin(), vec[i].end());
        vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
        for (int j = 1; j < vec[i].size(); j++) {
            int l = vec[i][j - 1], r = vec[i][j];
            int mid = (l + r) / 2;
            addd(l, mid, l);
            addd(mid + 1, r, r);
        }
    }
    for (int i = 1; i <= qq; i++) {
        int p = getMin(getLow(l[i]));
        int q = getMax(getLow(l[i]));
        if (p == -INF || q == INF)
            ans[i] = -1;
        else
            ans[i] = max(abs(l[i] - q), abs(l[i] - p));
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcCmp();
    calcVec();
    if (isSub3()) {
        solveSub3();
        writeOutput();
        return 0;
    }
    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:213:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for (int i = 0; i < cmpTim.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
new_home.cpp: In function 'void solveSub3()':
new_home.cpp:297:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  297 |         for (int j = 1; j < vec[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

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