Submission #49313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49313	2018-05-25T15:13:37 Z	BThero	New Home (APIO18_new_home)	C++17	10 / 100	726 ms	33892 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	15648 KB	Output is correct
2	Incorrect	14 ms	15648 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	15648 KB	Output is correct
2	Incorrect	14 ms	15648 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	445 ms	26132 KB	Output is correct
2	Correct	354 ms	26132 KB	Output is correct
3	Correct	558 ms	33808 KB	Output is correct
4	Correct	441 ms	33808 KB	Output is correct
5	Correct	349 ms	33808 KB	Output is correct
6	Correct	355 ms	33808 KB	Output is correct
7	Correct	726 ms	33892 KB	Output is correct
8	Correct	535 ms	33892 KB	Output is correct
9	Correct	494 ms	33892 KB	Output is correct
10	Correct	387 ms	33892 KB	Output is correct
11	Correct	369 ms	33892 KB	Output is correct
12	Correct	351 ms	33892 KB	Output is correct