Submission #908044

#	Time	Username	Problem	Language	Result	Execution time	Memory
908044		Trisanu_Das	New Home (APIO18_new_home)	C++17	100 / 100	1606 ms	66092 KiB

new_home

#include<bits/stdc++.h>
#define ll long long
const int inf = 1e8;
using namespace std;

int x[310005], t[610005], st[1210005], ans[310005];
vector<array<int, 2>> v1[310005];
array<int, 4> v2[1210005];
array<int, 3> qa[310005];

struct comp {
    bool operator () (const int &a, const int &b) const {
        if (x[a] == x[b])
            return a < b;
        return x[a] < x[b];
    }
};

map<int, int, comp> mp;
int u2 = 0, n, k, q;

void calc() {
    int i;
    for (i = 0; i < k; i++) {
        mp[n + 1] = 0;
        for (auto it : v1[i]) {
            auto it1 = mp.upper_bound(it[1]), it2 = it1--;
            v2[u2++] = {(x[it1->first] + x[it2->first] + 1) / 2, x[it2->first], it2->second, it[0]};
            it2->second = it[0];
            if (it1->first == it[1]) {
                it2 = it1--;
                v2[u2++] = {(x[it1->first] + x[it[1]] + 1) / 2, x[it[1]], it2->second, it[0]};
                mp.erase(it2);
            } else
                mp[it[1]] = it[0];
        }
        v2[u2++] = {0, 2 * inf, mp[n + 1], 2 * n + 1};
    }
    sort(v2, v2 + u2);
    int j = 0, e;
    for (i = 0; i < q; i++) {
        while (j < u2 && v2[j][0] <= qa[i][0]) {
            int l = v2[j][2] + 2 * n + 1;
            int r = v2[j][3] + 2 * n + 1;
            while (l < r) {
                if (l % 2 == 1)
                    st[l] = max(v2[j][1], st[l]);
                if (r % 2 == 1)
                    st[r - 1] = max(v2[j][1], st[r - 1]);
                ++l /= 2;
                r = r / 2;
            }
            ++j;
        }
        for (e = qa[i][2] + 2 * n + 1; e >= 1; e = e / 2)
            ans[qa[i][1]] = max(ans[qa[i][1]], st[e] - qa[i][0]);
    }
}

int main() {
    scanf("%d%d%d", &n, &k, &q);
    int i;
    for (i = 0; i < n; i++) {
        int aux;
        scanf("%d%d%d%d", &x[i], &aux, &t[2 * i], &t[2 * i + 1]);
        --aux;
        ++t[2 * i + 1];
        v1[aux].push_back({t[2 * i], i});
        v1[aux].push_back({t[2 * i + 1], i});
    }
    x[n] = -2 * inf;
    x[n + 1] = 2 * inf;
    sort(t, t + 2 * n + 1);
    for (i = 0; i < k; i++) {
        for (auto &it : v1[i])
            it[0] = lower_bound(t, t + 2 * n + 1, it[0]) - t;
        sort(v1[i].begin(), v1[i].end());
    }
    for (i = 0; i < q; i++) {
        scanf("%d%d", &qa[i][0], &qa[i][2]);
        qa[i][2] = upper_bound(t, t + 2 * n + 1, qa[i][2]) - t - 1;
        qa[i][1] = i;
    }
    sort(qa, qa + q);
    mp[n] = 0;
    calc();
    for (i = 0; i < n; i++)
        x[i] = inf - x[i];
    for (i = 0; i < q; i++)
        qa[i][0] = inf - qa[i][0];
    reverse(qa, qa + q);
    u2 = 0;
    memset(st, 0, sizeof(st));
    calc();
    for (i = 0; i < q; i++)
        if (ans[i] >= inf)
            printf("-1\n");
        else
            printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d%d%d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d%d%d%d", &x[i], &aux, &t[2 * i], &t[2 * i + 1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d%d", &qa[i][0], &qa[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20