Submission #49313

#	Time	Username	Problem	Language	Result	Execution time	Memory
49313		BThero	New Home (APIO18_new_home)	C++17	10 / 100	726 ms	33892 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;
    }

    bool operator < (shop &other) const {
        return x < other.x;
    }
} arr[300005];

struct que {
    int x, t, id;

    que() {
        x = t = id = 0;
    }

    bool operator < (que &other) const {
        return x < other.x;
    }
} req[300005];

vector < pair <int, int> > S;

vector <int> vv[300005];

int ans[300005];

int n, k, q;

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);
        req[i].id = i; req[i].x += req[i].x;
    }

    sort(arr + 1, arr + n + 1);
    sort(req + 1, req + q + 1);

    for (int i = 1; i <= k; ++i) {
        vv[i].pb(-INF);
    }

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

    for (int i = 1; i <= k; ++i) {
        vv[i].pb(INF);
    }

    bool bad = 0;

    for (int i = 1; i <= k; ++i) {
        if (vv[i].size() == 1) {
            bad = 1;
        }
    }

    if (bad) {
        for (int i = 1; i <= q; ++i) {
            printf("-1\n");
        }

        return;
    }

    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j + 1 < vv[i].size(); ++j) {
            int x = vv[i][j + 1] + vv[i][j];
            int y = vv[i][j + 1] - vv[i][j];
            S.pb(mp(x, y));
        }
    }

    sort(all(S));

    {
        int cur = S[0].se;
        int ptr = 1;

        for (int i = 1; i < S.size(); ++i) {
            while (ptr <= q && req[ptr].x < S[i].fi) {
                int diff = req[ptr].x - S[i - 1].fi;
                int ps = req[ptr++].id;
                ans[ps] = max(ans[ps], cur - diff);
            }

            int diff = S[i].fi - S[i - 1].fi;
            cur = max(S[i].se, cur - diff);
        }
    }

    {
        reverse(all(S));
        reverse(req + 1, req + q + 1);

        int cur = S[0].se;
        int ptr = 1;

        for (int i = 1; i < S.size(); ++i) {
            while (ptr <= q && req[ptr].x > S[i].fi) {
                int diff = S[i - 1].fi - req[ptr].x;
                int ps = req[ptr++].id;
                ans[ps] = max(ans[ps], cur - diff);
            }

            int diff = S[i - 1].fi - S[i].fi;
            cur = max(S[i].se, cur - diff);
        }

        reverse(all(S));
        reverse(req + 1, req + q + 1);
    }

    for (int i = 1; i <= q; ++i) {
        printf("%d ", (ans[i] >> 1));
    }
}

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:95:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j + 1 < vv[i].size(); ++j) {
                         ~~~~~~^~~~~~~~~~~~~~
new_home.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < S.size(); ++i) {
                         ~~^~~~~~~~~~
new_home.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < S.size(); ++i) {
                         ~~^~~~~~~~~~
new_home.cpp:51: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:54: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:55: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:59: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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20