Submission #952248

#	Time	Username	Problem	Language	Result	Execution time	Memory
952248		Itamar	New Home (APIO18_new_home)	C++14	0 / 100	4452 ms	1048580 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];
map<int, int> m;
int K;
struct node {
    int l, r, mid, maxi;
    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 == r && l == 0) {
            for (int i = 0; i < K; i++)s.insert(3e8+1);
        }
    }
    void open() {
        if (l < r) {
            sl = new node(l, mid);
            sr = new node(mid + 1, r);
        }
    }
    int query(int a, int b) {
        if (a > r || b < l)return 0;
        if (a <= l && b >= r)return maxi;
        int ans = 0;
        if (sl != NULL)ans = sl->query(a, b);
        if (sr != NULL)ans = max(ans, sr->query(a, b));
    }
    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);
        }
    }
};

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 });
    }
    sort(ev.begin(), ev.end());
    node* seg = new node(0, 3e8 + 3);
    for (vi v : ev) {
        if (v.size() == 2) {
            int l = v[1];
            int a = 0, b = 1e8 + 3;
            while (a < b) {
                int mid = (a + b) / 2;
                int ans = seg->query(0, min((int)1e8+1,max(l - mid - 1, 0)));
                if (ans <= mid + l) {
                    b = mid;
                }
                else {
                    a = mid+1;
                }
            }
            if (b == 1e8 + 3)cout << -1 << "\n";
            else cout << b << "\n";
        }
        else {
            int x = v[2], t = v[3];
            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(it);
            else col[t].insert(x);
            
            seg->update(*it2, x, v[1]);
            seg->update(*it2, *it1, !v[1]);
            seg->update(x, *it1, v[1]);
        }
    }
}
/*
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
*/

Compilation message (stderr)

new_home.cpp: In member function 'int node::query(int, int)':
new_home.cpp:46:5: warning: control reaches end of non-void function [-Wreturn-type]
   46 |     }
      |     ^

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