Submission #568407

#	Time	Username	Problem	Language	Result	Execution time	Memory
568407		Ooops_sorry	New Home (APIO18_new_home)	C++17	100 / 100	4807 ms	342992 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld double
#define ll __int128

mt19937 rnd(51);

const int INF = 1e9;

struct st{
    vector<int> t_min, t_max;
    vector<multiset<int>> t;
    int n;
    void build(int n_) {
        n = n_;
        t_min.clear(), t_max.clear(), t.clear();
        t_min.resize(2 * n, INF);
        t_max.resize(2 * n, -INF);
        t.resize(2 * n);
    }
    void upd(int v) {
        if (t[v].size() == 0) {
            t_min[v] = INF;
            t_max[v] = -INF;
            return;
        }
        t_min[v] = *t[v].begin();
        t_max[v] = *t[v].rbegin();
    }
    void update(int i, int val, bool add) {
        i += n;
        if (add) {
            t[i].insert(val);
        } else {
            t[i].erase(t[i].find(val));
        }
        upd(i);
        for (; i > 1; i /= 2) {
            t_min[i / 2] = min(t_min[i], t_min[i ^ 1]);
            t_max[i / 2] = max(t_max[i], t_max[i ^ 1]);
        }
    }
    int get_min(int l, int r) {
        l += n, r += n + 1;
        int ans = INF;
        while (l < r) {
            if (l & 1) {
                ans = min(ans, t_min[l++]);
            }
            if (r & 1) {
                ans = min(ans, t_min[--r]);
            }
            l /= 2, r /= 2;
        }
        return ans;
    }
    int get_max(int l, int r) {
        l += n, r += n + 1;
        int ans = -INF;
        while (l < r) {
            if (l & 1) {
                ans = max(ans, t_max[l++]);
            }
            if (r & 1) {
                ans = max(ans, t_max[--r]);
            }
            l /= 2, r /= 2;
        }
        return ans;
    }
};

vector<multiset<int>> pos;
vector<int> u2;

st L, R;
int sz;

void add(int a, int b) {
    int need = (a + b) / 2;
    int pos = upper_bound(u2.begin(), u2.end(), need) - u2.begin() - 1;
    int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
    L.update(pos, a, 1);
    R.update(pos + 1, b, 1);
}

void del(int a, int b) {
    int need = (a + b) / 2;
    int pos = upper_bound(u2.begin(), u2.end(), need) - u2.begin() - 1;
    int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
    L.update(pos, a, 0);
    R.update(pos + 1, b, 0);
}

void func(int i, int j, int need) {
    if (need) {
        if (pos[i].find(j) != pos[i].end()) {
            pos[i].insert(j);
            return;
        }
        int pre = *prev(pos[i].lower_bound(j));
        int nxt = *pos[i].upper_bound(j);
        del(pre, nxt);
        add(pre, j);
        add(j, nxt);
        pos[i].insert(j);
    } else {
        pos[i].erase(pos[i].find(j));
        if (pos[i].find(j) != pos[i].end()) return;
        int pre = *prev(pos[i].lower_bound(j));
        int nxt = *pos[i].upper_bound(j);
        del(pre, j);
        del(j, nxt);
        add(pre, nxt);
    }
}

vector<int> solve(int n, int k, int q, vector<int> x, vector<int> t, vector<int> a, vector<int> b, vector<int> l, vector<int> y) {
    u2.clear();
    u2.pb(-INF);
    u2.pb(INF);
    vector<vector<int>> ind(k);
    pos.clear();
    pos.resize(k);
    vector<int> ans(q);
    for (int i = 0; i < n; i++) {
        ind[t[i]].pb(x[i]);
        u2.pb(x[i]);
    }
    for (int i = 0; i < k; i++) {
        ind[i].pb(-INF);
        ind[i].pb(INF);
        sort(ind[i].begin(), ind[i].end());
    }
    for (int i = 0; i < q; i++) {
        u2.pb(l[i]);
    }
    sort(u2.begin(), u2.end());
    u2.erase(unique(u2.begin(), u2.end()), u2.end());
    vector<vector<int>> qu;
    for (int i = 0; i < n; i++) {
        qu.pb({a[i], -1, t[i], x[i]});
        qu.pb({b[i], 1, t[i], x[i]});
    }
    for (int i = 0; i < q; i++) {
        qu.pb({y[i], 0, l[i], i});
    }
    sz = u2.size();
    bool bad = 0;
    L.build(sz);
    R.build(sz);
    for (int i = 0; i < k; i++) {
        if (ind[i].size() == 2) bad = 1;
        pos[i].insert(-INF);
        pos[i].insert(INF);
        add(-INF, INF);
    }
    sort(qu.begin(), qu.end());
    set<int> st;
    for (int i = 0; i < k; i++) st.insert(i);
    for (int i = 0; i < qu.size(); i++) {
        if (qu[i][1] == -1) {
            if (pos[qu[i][2]].size() == 2) st.erase(qu[i][2]);
            func(qu[i][2], qu[i][3], 1);
        } else if (qu[i][1] == 0) {
            int j = lower_bound(u2.begin(), u2.end(), qu[i][2]) - u2.begin();
            int mx = L.get_min(j, sz - 1), mn = R.get_max(0, j);
            if (st.size() > 0) {
                ans[qu[i][3]] = -1;
            } else {
                ans[qu[i][3]] = max(qu[i][2] - mx, mn - qu[i][2]);
            }
        } else {
            func(qu[i][2], qu[i][3], 0);
            if (pos[qu[i][2]].size() == 2) st.insert(qu[i][2]);
        }
    }
    return ans;
}

vector<int> solvee(int n, int k, int q, vector<int> x, vector<int> t, vector<int> a, vector<int> b, vector<int> l, vector<int> y) {
    vector<int> ans;
    for (int i = 0; i < q; i++) {
        vector<int> bst(k, INF);
        for (int j = 0; j < n; j++) {
            if (a[j] <= y[i] && y[i] <= b[j]) {
                bst[t[j]] = min(bst[t[j]], abs(x[j] - l[i]));
            }
        }
        if (*max_element(bst.begin(), bst.end()) == INF) ans.pb(-1);
        else ans.pb(*max_element(bst.begin(), bst.end()));
    }
    return ans;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (1) {
        int n, k, q;
        cin >> n >> k >> q;
        vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> t[i] >> a[i] >> b[i];
            t[i]--;
        }
        for (int i = 0; i < q; i++) {
            cin >> l[i] >> y[i];
        }
        vector<int> ans = solve(n, k, q, x, t, a, b, l, y);
        for (auto to : ans) {
            cout << to << '\n';
        }
        return 0;
    }
    while (1) {
        int n = rnd() % 5 + 1, k = rnd() % 5 + 1, q = rnd() % 1 + 1;
        vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
        for (int i = 0; i < n; i++) {
            x[i] = rnd() % 10 + 1;
            t[i] = rnd() % k;
            a[i] = rnd() % 10 + 1;
            b[i] = rnd() % 10 + 1;
            if (a[i] > b[i]) swap(a[i], b[i]);
        }
        for (int i = 0; i < q; i++) {
            l[i] = rnd() % 10 + 1;
            y[i] = rnd() % 10 + 1;
        }
        auto res = solve(n, k, q, x, t, a, b, l, y), res2 = solvee(n, k, q, x, t, a, b, l, y);
        if (res != res2) {
            cout << n << ' ' << k << ' ' << q << endl;
            for (int i = 0; i < n; i++) {
                cout << x[i] << ' ' <<  t[i] + 1 << ' ' << a[i] << ' ' << b[i] << endl;
            }
            for (int i = 0; i < q; i++) {
                cout << l[i] << ' ' << y[i] << endl;
            }
            cout << "Bad" << endl;
            for (int i = 0; i < q; i++) {
                cout << res[i] << ' ' << res2[i] << endl;
            }
            return 0;
        }
        cout << "ok" << endl;
    }
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void add(int, int)':
new_home.cpp:85:9: warning: unused variable 'I' [-Wunused-variable]
   85 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |         ^
new_home.cpp:85:64: warning: unused variable 'J' [-Wunused-variable]
   85 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |                                                                ^
new_home.cpp: In function 'void del(int, int)':
new_home.cpp:93:9: warning: unused variable 'I' [-Wunused-variable]
   93 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |         ^
new_home.cpp:93:64: warning: unused variable 'J' [-Wunused-variable]
   93 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |                                                                ^
new_home.cpp: In function 'std::vector<int> solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
new_home.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int i = 0; i < qu.size(); i++) {
      |                     ~~^~~~~~~~~~~
new_home.cpp:152:10: warning: variable 'bad' set but not used [-Wunused-but-set-variable]
  152 |     bool bad = 0;
      |          ^~~

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