제출 #49023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49023		BThero	New Home (APIO18_new_home)	C++17	5 / 100	5093 ms	16536 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 INF = 1e9;

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

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

struct que {
    int x, t;

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

int ans[300005];

int rl[900005];

int mn[300005];

int n, m, k, q;

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;
    }
}

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 <= q; ++i) {
        for (int j = 1; j <= k; ++j) {
            mn[j] = INF;
        }

        for (int j = 1; j <= n; ++j) {
            if (arr[j].l <= req[i].t && req[i].t <= arr[j].r) {
                mn[arr[j].tp] = min(mn[arr[j].tp], abs(rl[req[i].x] - rl[arr[j].x]));
            }
        }

        for (int j = 1; j <= k; ++j) {
            ans[i] = max(ans[i], mn[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;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'void solve()':
new_home.cpp:95: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:98: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:99: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:103: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: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20