Submission #166101

#	Time	Username	Problem	Language	Result	Execution time	Memory
166101		Akashi	Two Antennas (JOI19_antennas)	C++14	100 / 100	800 ms	33060 KiB

antennas

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

const int INF = 2e9;

struct antenna{
    int l, r, h;
};
antenna a[200005];

struct complaint{
    int l, r, p;
    bool operator < (const complaint &aux)const{
        if(r != aux.r) return r < aux.r;
        return l < aux.l;
    }
};
complaint x[200005];

int n, q;
int ans[200005];
set <pair <int, int> > s;
set <pair <int, int> > s2;

int Min[800005], Max[800005], hMax[800005], hMin[800005], Sol[800005], LazyMin[800005], LazyMax[800005];

void build(int st = 1, int dr = n, int nod = 1){
    if(st == dr){
        Min[nod] = INF; Max[nod] = 0;
        hMin[nod] = INF; hMax[nod] = 0;
        Sol[nod] = -1;
        return ;
    }

    int mij = (st + dr) / 2;
    build(st, mij, nod * 2);
    build(mij + 1, dr, nod * 2 + 1);

    Min[nod] = min(Min[nod * 2], Min[nod * 2 + 1]);
    Max[nod] = max(Max[nod * 2], Max[nod * 2 + 1]);

    hMin[nod] = min(hMin[nod * 2], hMin[nod * 2 + 1]);
    hMax[nod] = max(hMax[nod * 2], hMax[nod * 2 + 1]);

    Sol[nod] = -1; LazyMin[nod] = INF;
}

void propag(int nod){
    if(LazyMin[nod] != INF){
        Min[2 * nod] = min(Min[2 * nod], LazyMin[nod]);
        Min[2 * nod + 1] = min(Min[2 * nod + 1], LazyMin[nod]);
        LazyMin[nod * 2] = min(LazyMin[nod], LazyMin[nod * 2]);
        LazyMin[nod * 2 + 1] = min(LazyMin[nod], LazyMin[nod * 2 + 1]);
    }
    if(LazyMax[nod] != 0){
        Max[2 * nod] = max(Max[2 * nod], LazyMax[nod]);
        Max[2 * nod + 1] = max(Max[2 * nod + 1], LazyMax[nod]);
        LazyMax[nod * 2] = max(LazyMax[nod], LazyMax[nod * 2]);
        LazyMax[nod * 2 + 1] = max(LazyMax[nod], LazyMax[nod * 2 + 1]);
    }

    Sol[2 * nod] = max(Sol[2 * nod], max(hMax[2 * nod] - LazyMin[nod], LazyMax[nod] - hMin[2 * nod]));
    Sol[2 * nod + 1] = max(Sol[2 * nod + 1], max(hMax[2 * nod + 1] - LazyMin[nod], LazyMax[nod] - hMin[2 * nod + 1]));

    LazyMin[nod] = INF; LazyMax[nod] = 0;
}

void update(int x, int y, int v, int st = 1, int dr = n, int nod = 1){
    if(st != dr) propag(nod);
    if(hMin[nod] == INF) return ;

    if(x <= st && dr <= y){
        LazyMax[nod] = max(LazyMax[nod], v);
        LazyMin[nod] = min(LazyMin[nod], v);

        Min[nod] = min(Min[nod], v);
        Max[nod] = max(Max[nod], v);

        Sol[nod] = max(Sol[nod], max(hMax[nod] - v, v - hMin[nod]));

        return ;
    }

    int mij = (st + dr) / 2;

    if(x <= mij) update(x, y, v, st, mij, nod * 2);
    if(mij + 1 <= y) update(x, y, v, mij + 1, dr, nod * 2 + 1);

    Min[nod] = min(Min[nod * 2], Min[nod * 2 + 1]);
    Max[nod] = max(Max[nod * 2], Max[nod * 2 + 1]);

    hMin[nod] = min(hMin[nod * 2], hMin[nod * 2 + 1]);
    hMax[nod] = max(hMax[nod * 2], hMax[nod * 2 + 1]);

    Sol[nod] = max(Sol[nod * 2], Sol[nod * 2 + 1]);
}

void update2(int x, int v, int st = 1, int dr = n, int nod = 1){
    if(st != dr) propag(nod);
    if(st == dr){
        if(v == -2) hMin[nod] = a[st].h, hMax[nod] = a[st].h;
        else hMin[nod] = INF, hMax[nod] = 0;

        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij) update2(x, v, st, mij, nod * 2);
    else update2(x, v, mij + 1, dr, nod * 2 + 1);

    Min[nod] = min(Min[nod * 2], Min[nod * 2 + 1]);
    Max[nod] = max(Max[nod * 2], Max[nod * 2 + 1]);

    hMin[nod] = min(hMin[nod * 2], hMin[nod * 2 + 1]);
    hMax[nod] = max(hMax[nod * 2], hMax[nod * 2 + 1]);

    Sol[nod] = max(Sol[nod * 2], Sol[nod * 2 + 1]);
}

int query(int x, int y, int st = 1, int dr = n, int nod = 1){
    if(x <= st) return Sol[nod];
    if(st != dr) propag(nod);

    int mij = (st + dr) / 2, a1 = -1, a2 = -1;
    if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
    if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);

    return max(a1, a2);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%d%d%d", &a[i].h, &a[i].l, &a[i].r);

    scanf("%d", &q);
    for(int i = 1; i <= q ; ++i) scanf("%d%d", &x[i].l, &x[i].r), x[i].p = i;

    sort(x + 1, x + q + 1);

    build();

    int j = 1;
    for(int i = 1; i <= q ; ++i){
        while(j <= n && j <= x[i].r){
            while(!s2.empty() && s2.begin()->first < j){
                update2(s2.begin()->second, -2);
                s.insert({a[s2.begin()->second].r + s2.begin()->second, s2.begin()->second});
                s2.erase(s2.begin());
            }
            while(!s.empty() && s.begin()->first < j){
                update2(s.begin()->second, -1);
                s.erase(s.begin());
            }

            if(j - a[j].l >= 1) update(max(1, j - a[j].r), j - a[j].l, a[j].h);

            if(a[j].l != 1 && j + a[j].l - 1 <= n) s2.insert({j + a[j].l - 1, j});
            else if(j + a[j].l - 1 <= n){
                update2(j, -2);
                if(j + a[j].r <= n) s.insert({j + a[j].r, j});
            }
            ++j;
        }

        ans[x[i].p] = query(x[i].l, x[i].r);
    }

    for(int i = 1; i <= q ; ++i) printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].h, &a[i].l, &a[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
antennas.cpp:138:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= q ; ++i) scanf("%d%d", &x[i].l, &x[i].r), x[i].p = i;
                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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