Submission #938851

#	Time	Username	Problem	Language	Result	Execution time	Memory
938851		danikoynov	Two Antennas (JOI19_antennas)	C++14	0 / 100	3042 ms	43092 KiB

antennas

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 2e5 + 10;

struct query
{
    int l, r, idx;

    query(int _l = 0, int _r = 0, int _idx = 0)
    {
        l = _l;
        r = _r;
        idx = _idx;
    }
}task[maxn];

int n, q;
int h[maxn], a[maxn], b[maxn];
vector < query > spot[maxn];
int ans[maxn];

void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> h[i] >> a[i] >> b[i];
    }
    cin >> q;
        for (int i = 1; i <= q; i ++)
    ans[i] = -1;

    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
        spot[task[i].r].push_back(task[i]);
    }
}

const int inf = 2e9 + 10;
int act[maxn], low[maxn];
vector < int > upd[2][2 * maxn];

void sweep_line()
{
    for (int i = 1; i <= n; i ++)
    {
        low[i] = inf;
        act[i] = 0;
        upd[0][i + a[i]].push_back(i);
        upd[1][i + b[i]].push_back(i);
    }

    for (int i = 1; i <= n; i ++)
    {
        for (int cur : upd[0][i])
        {
            act[cur] = 1;
        }

        int lf = max(1, i - b[i]), rf = max(1, i - a[i]);
        for (int j = lf; j <= rf; j ++)
        {
            if (act[j])
                low[j] = min(low[j], h[i]);
        }

        for (int cur : upd[1][i])
        {
            act[cur] = 0;
        }

        for (query cur : spot[i])
        {
            for (int j = cur.l; j <= cur.r; j ++)
            {
                ans[cur.idx] = max(ans[cur.idx], h[j] - low[j]);
            }
        }
    }
}

void reverse_data()
{
    reverse(h + 1, h + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);

    for (int i = 1; i <= n; i ++)
    {
        spot[i].clear();
        upd[0][i].clear();
        upd[1][i].clear();
    }

    for (int i = 1; i <= q; i ++)
    {
        int nl = n - task[i].r + 1, nr = n - task[i].l + 1;
        task[i].l = nl;
        task[i].r = nr;
        spot[task[i].r].push_back(task[i]);
    }
}

void print()
{
    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
}
void solve()
{
    input();

    sweep_line();
    reverse_data();
    sweep_line();
    print();
}

int main()
{
    speed();
        solve();
    return 0;
}

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