Submission #53757

#	Time	Username	Problem	Language	Result	Execution time	Memory
53757		aquablitz11	New Home (APIO18_new_home)	C++14	12 / 100	3717 ms	305668 KiB

new_home

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define F first
#define S second
#define forx(i, x, y) for (int i = (x); i <= (y); ++i)
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define for1(i, n) for (int i = 1; i <= (n); ++i)
#define rofx(i, x, y) for (int i = x; i >= y; --i)
#define rofn(i, n) for (int i = n-1; i >= 0; --i)
#define rof1(i, n) for (int i = n; i >= 1; --i)
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fora(x, v) for (auto x : v)

struct Event
{
    int type; // 0 = add, 1 = query, 2 = remove
    int tim; // time
    int v1; // location
    int v2; // query index or building type
    bool operator<(const Event &rhs) const {
        if (tim != rhs.tim) return tim < rhs.tim;
        if (type != rhs.type) return type < rhs.type;
        if (v1 != rhs.v1) v1 < rhs.v1;
        return v2 < rhs.v2;
    }
};

const int N = 6e5+10;

vector<Event> events;
int ans[N];

vector<int> coor;
int c;
struct node {
    int sum;
    node *l, *r;
    node(int s) : sum(s), l(NULL), r(NULL) {}
    node(node *l, node *r) : l(l), r(r), sum(l->sum + r->sum) {}
};
node *root[N];

int found[N];

node *build(int b=1, int e=c)
{
    if (b == e)
        return new node(0);
    int m = (b+e)/2;
    return new node(build(b, m), build(m+1, e));
}

int query(int l, int r, node *p, int b=1, int e=c)
{
    if (b >= l && e <= r)
        return p->sum;
    if (b > r || e < l)
        return 0;
    int m = (b+e)/2;
    return query(l, r, p->l, b, m) + query(l, r, p->r, m+1, e);
}

node *update(int i, int x, node *p, int b=1, int e=c)
{
    if (b == e)
        return new node(p->sum + x);
    int m = (b+e)/2;
    if (i <= m)
        return new node(update(i, x, p->l, b, m), p->r);
    else
        return new node(p->l, update(i, x, p->r, m+1, e));
}

int main()
{
    int n, k, q;
    scanf("%d%d%d", &n, &k, &q);

    bool skip = false;
    // subtask 1, 2
    if (k <= 400 && !skip) {

        forn(i, n) {
            int x, t, a, b;
            scanf("%d%d%d%d", &x, &t, &a, &b);
            events.pb({0, a, x, t});
            events.pb({2, b, x, t});
        }
        forn(i, q) {
            int l, y;
            scanf("%d%d", &l, &y);
            events.pb({1, y, l, i});
        }
        sort(all(events));

        vector<multiset<int>> pos(k+1, multiset<int>());
        for1(i, k) {
            pos[i].insert(-1e9);
            pos[i].insert(1e9);
        }
        fora(e, events) {
            if (e.type == 0) { // add
                pos[e.v2].insert(e.v1);
            } else if (e.type == 1) { // answer query

                int a = 0;
                for1(i, k) {
                    auto r = pos[i].lower_bound(e.v1);
                    auto l = prev(r);
                    a = max(a, min(abs(*l-e.v1), abs(*r-e.v1)));
                }
                if (a > 1e8)
                    a = -1;
                ans[e.v2] = a;

            } else { // remove
                pos[e.v2].erase(pos[e.v2].find(e.v1));
            }
        }

        forn(i, q)
            printf("%d\n", ans[i]);

    } else { // subtask 3

        vector<pii> st; // stores (position, type)
        forn(i, n) {
            int x, t, a, b;
            scanf("%d%d%d%d", &x, &t, &a, &b);
            st.pb({x, t});
            coor.pb(x);
        }
        sort(all(st));
        sort(all(coor));
        coor.resize(unique(all(coor))-coor.begin());
        c = coor.size();

        for1(i, n) root[i] = NULL;
        root[0] = build();
        fora(at, st) {
            int x = at.F, t = at.S;
            int p = lower_bound(all(coor), x) - coor.begin() + 1;
            root[p] = root[p-1];
            if (found[t] == 0)
                root[p] = update(found[t], -1, root[p]);
            found[t] = p;
            root[p] = update(p, 1, root[p]);
        }
        
        forn(i, q) {
            int x, y;
            scanf("%d%d", &x, &y);
            //printf("\nquery %d\n", x);
            int b = 0;
            int e = 1e8;
            while (b < e) {
                int m = (b+e)/2;
                int lp = lower_bound(all(coor), x-m) - coor.begin() + 1;
                int rp = upper_bound(all(coor), x+m)-1 - coor.begin() + 1;
                //printf("try m=%d, l=%d (%d), r=%d (%d)", m, x-m, lp, x+m, rp);
                int q = query(lp, rp, root[rp]);
                //printf("got %d\n", q);
                if (q == k)
                    e = m;
                else
                    b = m+1;
            }
            if (b > 1e8) b = -1;
            printf("%d\n", b);
        }

    }

    return 0;
}

Compilation message (stderr)

new_home.cpp: In member function 'bool Event::operator<(const Event&) const':
new_home.cpp:29:30: warning: statement has no effect [-Wunused-value]
         if (v1 != rhs.v1) v1 < rhs.v1;
                           ~~~^~~~~~~~
new_home.cpp: In constructor 'node::node(node*, node*)':
new_home.cpp:43:15: warning: 'node::r' will be initialized after [-Wreorder]
     node *l, *r;
               ^
new_home.cpp:42:9: warning:   'int node::sum' [-Wreorder]
     int sum;
         ^~~
new_home.cpp:45:5: warning:   when initialized here [-Wreorder]
     node(node *l, node *r) : l(l), r(r), sum(l->sum + r->sum) {}
     ^~~~
new_home.cpp: In function 'int main()':
new_home.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d%d", &x, &t, &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &l, &y);
             ~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:135:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d%d", &x, &t, &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:158:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

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