Submission #952291

#	Time	Username	Problem	Language	Result	Execution time	Memory
952291		Itamar	New Home (APIO18_new_home)	C++17	47 / 100	5065 ms	635648 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 a, int b) {
        if (a > r || b < l || maxi==0)return 0;
        if (a <= l && b >= r)return maxi;
        if (p)return max(sl->query(a, b), sr->query(a, b));
        return 0;
    }
    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 a = 0, b = 1e8 + 3;
            while (a < b) {
                int mid = (a + b) / 2;
                int ans = seg->query(0, max(l - mid - 1, 0));
                if (ans <= mid + l) {
                    b = mid;
                }
                else {
                    a = mid+1;
                }
            }
            if (b == 1e8 + 3)ans[v[2]] = -1;
            else ans[v[2]] = b;
        }
        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: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20