Submission #49314

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49314	2018-05-25T15:18:46 Z	BThero	New Home (APIO18_new_home)	C++17	10 / 100	683 ms	33808 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 = 5e8;

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() == 2) {
            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	15608 KB	Output is correct
2	Incorrect	15 ms	15608 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	15608 KB	Output is correct
2	Incorrect	15 ms	15608 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	466 ms	26120 KB	Output is correct
2	Correct	376 ms	26120 KB	Output is correct
3	Correct	683 ms	33740 KB	Output is correct
4	Correct	549 ms	33740 KB	Output is correct
5	Correct	542 ms	33740 KB	Output is correct
6	Correct	486 ms	33740 KB	Output is correct
7	Correct	650 ms	33808 KB	Output is correct
8	Correct	426 ms	33808 KB	Output is correct
9	Correct	412 ms	33808 KB	Output is correct
10	Correct	404 ms	33808 KB	Output is correct
11	Correct	381 ms	33808 KB	Output is correct
12	Correct	418 ms	33808 KB	Output is correct