Submission #49312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49312	2018-05-25T15:11:24 Z	BThero	New Home (APIO18_new_home)	C++17	10 / 100	694 ms	41880 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 <double, double> > S;

vector <int> vv[300005];

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

    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 * 0.5, y * 0.5));
        }
    }

    sort(all(S));

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

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

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

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

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

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

            double 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 ", (int)floor(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

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	17 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	17 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	528 ms	30160 KB	Output is correct
2	Correct	420 ms	30160 KB	Output is correct
3	Correct	693 ms	41744 KB	Output is correct
4	Correct	671 ms	41744 KB	Output is correct
5	Correct	543 ms	41744 KB	Output is correct
6	Correct	409 ms	41744 KB	Output is correct
7	Correct	694 ms	41880 KB	Output is correct
8	Correct	586 ms	41880 KB	Output is correct
9	Correct	493 ms	41880 KB	Output is correct
10	Correct	430 ms	41880 KB	Output is correct
11	Correct	478 ms	41880 KB	Output is correct
12	Correct	382 ms	41880 KB	Output is correct