Submission #952312

#	Time	Username	Problem	Language	Result	Execution time	Memory
952312		Itamar	New Home (APIO18_new_home)	C++17	100 / 100	4668 ms	903500 KiB

new_home

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define pd pair<double,double>

const int siz = 3e5 + 2;
multiset<int> col[siz];
int K;
struct node {
    int l, r, mid, maxi;
    bool p=0;
    multiset<int> s;
    node* sl = NULL;
    node *sr = NULL;
    node(int li, int ri) {
        l = li, r = ri, mid = (l + r) / 2, maxi = 0;
        if (l == 0) {
            maxi = 3e8 + 1;

            if (r == 0) {
                for (int i = 0; i < K; i++)s.insert(3e8 + 1);
            }
            else open();
        }
    }
    void open() {
        
        if (sl == NULL && (l < r)) {
            p = 1;
            sl = new node(l, mid);
            sr = new node(mid + 1, r);
        }
    }
    int query(int x, int&ma) {
        open();
        if (l == r) {
            if (l > 0)return x-l;
            return maxi - x;
        }
        else {
            if (x <= mid)return sl->query(x,ma);
            if (max(ma,sl->maxi) >= 2*x - mid) {
                return sl->query(x,ma);
            }
            else {
                ma = max(ma, sl->maxi);
                return sr->query(x, ma);
            }
        }
    }
    void update(int v, int x, bool f) {
        if (l == r) {
            if (f)s.insert(v);
            else s.erase(s.find(v));
            if (s.size())maxi = *(--s.end());
            else maxi = 0;
        }
        else {
            if (sl == NULL)open();
            if (x <= mid) {
                sl->update(v, x, f);
            }
            else {
                sr->update(v, x, f);
            }
            maxi = max(sl->maxi, sr->maxi);
        }
    }
};
map<pi, int> sum;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, k, q;
    cin >> n >> k >> q;
    vector<vi> ev;
    K = k;
    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        x++;
        ev.push_back({ a,1,x,t });
        ev.push_back({b+1,0,x,t });
    }
    for (int i = 0; i < siz; i++) {
        col[i].insert(0);
        col[i].insert(3e8 + 1);
    }
    for (int i = 0; i < q; i++) {
        int l, y;
        cin >> l >> y;
        l++;
        ev.push_back({ y,l,i });
    }
    sort(ev.begin(), ev.end());
    node* seg = new node(0, 3e8 + 3);
    vi ans(q);
    for (vi v : ev) {
        if (v.size() == 3) {
            int l = v[1];
            int h = 0;
            ans[v[2]] = seg->query(l,h);
            if (ans[v[2]] > 1e8)ans[v[2]] = -1;
        }
        else {
            int x = v[2], t = v[3];
            if (v[1])sum[{x, t}]++;
            else sum[{x,t}]--;
            if (v[1] == sum[{x,t}]) {
                auto it = col[t].lower_bound(x);
                auto it1 = it, it2 = it;
                it1--; if (v[1] == 0)it2++;
                if (v[1] == 0)col[t].erase(x);
                else col[t].insert(x);

                seg->update(*it2, x, v[1]);
                seg->update(*it2, *it1, !v[1]);
                seg->update(x, *it1, v[1]);
            }
        }
    }
    for (int i = 0; i < q; i++)cout << ans[i] << "\n";
}
/*
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
*/

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