Submission #551189

#	Time	Username	Problem	Language	Result	Execution time	Memory
551189		wenqi	Two Antennas (JOI19_antennas)	C++17	100 / 100	616 ms	43084 KiB

antennas

// trans rights

#include <bits/extc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;

#ifdef DEBUG
#define D(...) fprintf(stderr, __VA_ARGS__)
#else
#define D(...)
#endif

int N, Q;
int H[200069], A[200069], B[200069], answer[200069];

constexpr int NUKE = 1012345678;

struct Node
{
    int l, r;
    Node *lc, *rc;
    int um_mn, um_mx;
    int t_mn, t_mx, per;
    Node(int l, int r) : l(l), r(r), lc(0), rc(0), um_mn(NUKE), um_mx(-NUKE), t_mn(NUKE), t_mx(-NUKE), per(-NUKE)
    {
        if (l != r)
        {
            int m = l + (r - l) / 2;
            lc = new Node(l, m);
            rc = new Node(m + 1, r);
        }
    }
    void clean()
    {
        per = max(per, max(t_mx - um_mn, um_mx - t_mn));
        if (lc)
        {
            lc->t_mn = min(lc->t_mn, t_mn);
            rc->t_mn = min(rc->t_mn, t_mn);
            lc->t_mx = max(lc->t_mx, t_mx);
            rc->t_mx = max(rc->t_mx, t_mx);
        }
        t_mn = NUKE;
        t_mx = -NUKE;
    }
    void unmask(int p, int x)
    {
        clean();
        if (l == r)
        {
            um_mn = um_mx = x;
            clean();
            return;
        }
        if (p <= lc->r)
            lc->unmask(p, x);
        else
            rc->unmask(p, x);
        um_mn = min(lc->um_mn, rc->um_mn);
        um_mx = max(lc->um_mx, rc->um_mx);
    }
    void mask(int p)
    {
        clean();
        if (l == r)
        {
            um_mn = NUKE;
            um_mx = -NUKE;
            return;
        }
        if (p <= lc->r)
            lc->mask(p);
        else
            rc->mask(p);
        um_mn = min(lc->um_mn, rc->um_mn);
        um_mx = max(lc->um_mx, rc->um_mx);
    }
    void update(int ql, int qr, int x)
    {
        clean();
        if (qr < l or ql > r)
            return;
        if (ql <= l and qr >= r)
        {
            t_mn = t_mx = x;
            clean();
            return;
        }
        lc->update(ql, qr, x);
        rc->update(ql, qr, x);
        per = max(per, max(lc->per, rc->per));
    }
    int query(int ql, int qr)
    {
        clean();
        if (qr < l or ql > r)
            return -NUKE;
        if (ql <= l and qr >= r)
            return per;
        return max(lc->query(ql, qr), rc->query(ql, qr));
    }
};

int main(int argc, const char *argv[])
{
    scanf("%d", &N);
    vector<pair<int, int>> events;
    vector<tuple<int, int, int>> queries;
    for (int i = 1; i <= N; i++)
    {
        int h, a, b;
        scanf("%d%d%d", &h, &a, &b);
        H[i] = h, A[i] = a, B[i] = b;

        events.push_back({i + A[i], i});
        events.push_back({i + B[i] + 1, i});
    }
    scanf("%d", &Q);
    for (int k = 0; k < Q; k++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        queries.push_back({r, l, k});
    }
    sort(events.begin(), events.end());
    sort(queries.begin(), queries.end());

    int next_event = 0;
    int next_rock = 0;
    Node *root = new Node(1, N);
    for (auto &q : queries)
    {
        auto [r, l, qid] = q;
        while (next_rock <= r)
        {
            while (next_event < events.size() and events[next_event].first <= next_rock)
            {
                auto [p, i] = events[next_event];
                D("e: %d %d\n", i, p);
                if (i + B[i] + 1 == p)
                {
                    root->mask(i);
                }else{
                    root->unmask(i, H[i]);
                }
                next_event++;
            }
            int a = next_rock - B[next_rock];
            int b = next_rock - A[next_rock];
            D("u: %d %d %d\n", next_rock, a, b);
            root->update(a, b, H[next_rock]);
            next_rock++;
        }
        D("------\n");
        answer[qid] = root->query(l, r);

        if (answer[qid] < 0)
            answer[qid] = -1;
    }
    for (int qid = 0; qid < Q; qid++)
        printf("%d\n", answer[qid]);
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main(int, const char**)':
antennas.cpp:138:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             while (next_event < events.size() and events[next_event].first <= next_rock)
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~~~
antennas.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%d%d%d", &h, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%d%d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65