Submission #122824

#	Time	Username	Problem	Language	Result	Execution time	Memory
122824		win11905	Two Antennas (JOI19_antennas)	C++11	35 / 100	3034 ms	330520 KiB

antennas

#include <bits/stdc++.h>
#define iii tuple<int, int, int>
using namespace std;

const int N = 1<<18;
const int INF = 1e9+1;

int n, m;
int H[N], x[N], y[N];
vector<int> preadd[N], predel[N];

struct node {
    int mn, mx;
    node *l, *r;
    node(int mn, int mx, node *l, node *r) : mn(mn), mx(mx), l(l), r(r) {}
};

node* newson(int mn, int mx) { return new node(mn, mx, nullptr, nullptr); }
node * newpar(node *l, node *r) { return new node(min(l->mn, r->mn), max(l->mx, r->mx), l, r); }

node* build(int l = 1, int r = n) {
    if(l == r) return newson(INF, -INF);
    int m = (l + r) >> 1;
    return newpar(build(l, m), build(m+1, r));
}

node* update(int v, bool st, node* p, int l = 1, int r = n) {
    if(l == r) {
        if(st) return newson(H[v], H[v]);
        return newson(INF, -INF);
    }
    int m = (l + r) >> 1;
    if(v <= m) return newpar(update(v, st, p->l, l, m), p->r);
    return newpar(p->l, update(v, st, p->r, m+1, r));
}

int qmin(int x, int y, node* p, int l = 1, int r = n) {
    if(x > r || l > y) return INF;
    if(x <= l && r <= y) return p->mn;
    int m = (l + r) >> 1;
    return min(qmin(x, y, p->l, l, m), qmin(x, y, p->r, m+1, r));
}

int qmax(int x, int y, node* p, int l = 1, int r = n) {
    if(x > r || l > y) return -INF;
    if(x <= l && r <= y) return p-> mx;
    int m = (l + r) >> 1;
    return max(qmax(x, y, p->l, l, m), qmax(x, y, p->r, m+1, r)); 
}

node *ver[N];
int ans[N];
const int sz = 200;
vector<iii> block[1000];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d %d %d", H+i, x+i, y+i);
        if(i + x[i] <= n) preadd[i+x[i]].emplace_back(i), predel[min(n, i+y[i]) + 1].emplace_back(i);
        if(i - x[i] >= 1) preadd[max(1, i-y[i])].emplace_back(i), predel[i-x[i] + 1].emplace_back(i);
    }
    ver[0] = ver[1] = build();
    for(int i = 1; i <= n; ++i) {
        for(int v : preadd[i]) ver[i] = update(v, true, ver[i]);//, cerr << "add -> " << i << ' ' << v << endl;
        for(int v : predel[i]) ver[i] = update(v, false, ver[i]);//, cerr << "del -> " << i << ' ' << v << endl;
        ver[i+1] = ver[i];
    }
    scanf("%d", &m);
    memset(ans, -1, sizeof ans);
    for(int i = 0, l, r; i < m; ++i) {
        scanf("%d %d", &l, &r); 
        block[l / sz].emplace_back(r, l, i);
    }
    for(int i = 0; i < sz; ++i) {
        sort(block[i].begin(), block[i].end());
        int pa = (i+1) * sz;
        int pmx = -1, ptr = pa;
        for(auto z : block[i]) {
            int l, r, idx; tie(r, l, idx) = z;
            // cerr << l << ' ' << r << endl;
            int imx = -1;
            while(ptr <= r) {
                pmx = max({pmx, H[ptr] - qmin(max(pa, ptr - y[ptr]), ptr - x[ptr], ver[ptr]), qmax(max(pa, ptr - y[ptr]), ptr - x[ptr], ver[ptr]) - H[ptr]});
                ptr++;
            }
            for(int i = min(r, pa-1); i >= l; --i) {
                imx = max({imx, H[i] - qmin(i+x[i], min(r, i+y[i]), ver[i]), qmax(i+x[i], min(r, i+y[i]), ver[i]) - H[i]});
            }
            ans[idx] = max(pmx, imx);
        }
    }
    for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", H+i, x+i, y+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
antennas.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r); 
         ~~~~~^~~~~~~~~~~~~~~~~

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