Submission #49024

#	Time	Username	Problem	Language	Result	Execution time	Memory
49024		BThero	새 집 (APIO18_new_home)	C++17	12 / 100	5109 ms	124048 KiB

new_home

// Why am I so stupid? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

typedef long long ll;

using namespace std;

const int MAXN = 3e5+5;

const int INF = 1e9;

struct shop {
    int x, tp, l, r;

    shop() {
        x = tp = l = r = 0;
    }
} arr[MAXN];

struct que {
    int x, t;

    que() {
        x = t = 0;
    }
} req[MAXN];

vector < pair <int, int> > addEl[MAXN * 3];

vector < pair <int, int> > delEl[MAXN * 3];

vector < pair <int, int> > reqEl[MAXN * 3];

multiset <int> ms[MAXN];

int rl[MAXN * 3];

int n, m, k, q;

int ans[MAXN];

int mn[MAXN];

void compressTime() {
    vector <int> vv;

    for (int i = 1; i <= n; ++i) {
        vv.pb(arr[i].l);
        vv.pb(arr[i].r);
    }

    for (int i = 1; i <= q; ++i) {
        vv.pb(req[i].t);
    }

    sort(all(vv));
    vv.resize(unique(all(vv)) - vv.begin());

    m = vv.size();

    for (int i = 1; i <= n; ++i) {
        arr[i].l = upper_bound(all(vv), arr[i].l) - vv.begin();
        arr[i].r = upper_bound(all(vv), arr[i].r) - vv.begin();
    }

    for (int i = 1; i <= q; ++i) {
        req[i].t = upper_bound(all(vv), req[i].t) - vv.begin();
    }
}

void compressX() {
    vector <int> vv;

    for (int i = 1; i <= n; ++i) {
        vv.pb(arr[i].x);
    }

    for (int i = 1; i <= q; ++i) {
        vv.pb(req[i].x);
    }

    sort(all(vv));
    vv.resize(unique(all(vv)) - vv.begin());

    for (int i = 1, ps; i <= n; ++i) {
        ps = upper_bound(all(vv), arr[i].x) - vv.begin();
        rl[ps] = arr[i].x; arr[i].x = ps;
    }

    for (int i = 1, ps; i <= q; ++i) {
        ps = upper_bound(all(vv), req[i].x) - vv.begin();
        rl[ps] = req[i].x; req[i].x = ps;
    }
}

int dist(int x, int tp) {
    auto it = ms[tp].upper_bound(x);
    int ret = INF;

    if (it != ms[tp].end()) {
        ret = min(ret, rl[*it] - rl[x]);
    }

    if (it != ms[tp].begin()) {
        ret = min(ret, rl[x] - rl[*(--it)]);
    }

    return ret;
}

void solve() {
    scanf("%d %d %d", &n, &k, &q);

    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &arr[i].x, &arr[i].tp);
        scanf("%d %d", &arr[i].l, &arr[i].r);
    }

    for (int i = 1; i <= q; ++i) {
        scanf("%d %d", &req[i].x, &req[i].t);
    }

    compressTime();
    compressX();

    for (int i = 1; i <= n; ++i) {
        addEl[arr[i].l].pb(mp(arr[i].x, arr[i].tp));
        delEl[arr[i].r + 1].pb(mp(arr[i].x, arr[i].tp));
    }

    for (int i = 1; i <= q; ++i) {
        reqEl[req[i].t].pb(mp(req[i].x, i));
    }

    for (int i = 1; i <= m; ++i) {
        for (auto it : addEl[i]) {
            ms[it.se].insert(it.fi);
        }

        for (auto it : delEl[i]) {
            ms[it.se].erase(ms[it.se].find(it.fi));
        }

        for (auto it : reqEl[i]) {
            for (int j = 1; j <= k; ++j) {
                ans[it.se] = max(ans[it.se], dist(it.fi, j));
            }
        }
    }

    for (int i = 1; i <= q; ++i) {
        if (ans[i] == INF) {
            ans[i] = -1;
        }

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

int main() {
#ifdef BThero
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // BThero

    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:120: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:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &arr[i].x, &arr[i].tp);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &arr[i].l, &arr[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &req[i].x, &req[i].t);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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