oj.uz

답안 #938851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938851 2024-03-05T16:56:49 Z danikoynov Two Antennas (JOI19_antennas) C++14
0 / 100
 3000 ms 43092 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 30808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 30808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3042 ms 43092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 30808 KB Output isn't correct
2 Halted 0 ms 0 KB -