제출 #1170128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170128		jerzyk	Two Antennas (JOI19_antennas)	C++20	100 / 100	567 ms	38916 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<18;
int tab[N];
pair<int, int> ran[N];
vector<int> poc[N], kon[N];
vector<pair<int, int>> que[N];

int mi[2 * N];
int drz[2 * N], laz[2 * N];

int ans[N];

void Push(int v)
{
    for(int s = v * 2; s <= v * 2 + 1; ++s)
    {
        drz[s] = max(drz[s], laz[v] - mi[s]);
        laz[s] = max(laz[s], laz[v]);
    }
    laz[v] = (-(II / 2)) - 1;
}

void Change(int v, int x)
{
    v += N;
    vector<int> pth;
    int u = v;
    while(u > 0)
    {
        pth.pb(u);
        u /= 2;
    }
    for(int i = (int)pth.size() - 1; i > 0; --i)
        Push(pth[i]);
    mi[v] = x;
    v /= 2;
    while(v > 0)
    {
        mi[v] = min(mi[v * 2], mi[v * 2 + 1]);
        v /= 2;
    }
}

void Update(int v, int p, int k, int pz, int kz, int x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        drz[v] = max(drz[v], x - mi[v]);
        laz[v] = max(laz[v], x);
        return;
    }
    Push(v);
    Update(v * 2, p, (p + k) / 2, pz, kz, x);
    Update(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
    drz[v] = max(drz[v], max(drz[v * 2], drz[v * 2 + 1]));
}

inline void U(int a, int b, int x)
{
    if(a > b) return;
    Update(1, 0, N - 1, a, b, x);
}

int Query(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return -1;
    if(p >= pz && k <= kz) return drz[v];
    int a;
    Push(v);
    a = Query(v * 2, p, (p + k) / 2, pz, kz);
    a = max(a, Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz));
    return a;
}

inline int Q(int a, int b)
{
    if(a > b) return -1;
    return Query(1, 0, N - 1, a, b);
}

void Do(int n)
{
    for(int i = 1; i < 2 * N; ++i)
    {
        drz[i] = -1; mi[i] = II / 2 + 1;
        laz[i] = (-II / 2) - 1;
    }
    //cout << "Do:\n";
    for(int i = n; i >= 1; --i)
    {
        for(int j = 0; j < (int)poc[i].size(); ++j)
            Change(poc[i][j], tab[poc[i][j]]);

        /*for(int j = i + ran[i].st; j <= min(n, i + ran[i].nd); ++j)
        {
            dp[j] = max(dp[j], dp[j - 1]);
            if(czy[j])
                dp[j] = max(dp[j], tab[i] - tab[j]);
        }*/
        U(i + ran[i].st, min(n, i + ran[i].nd), tab[i]);

        for(int j = 0; j < (int)que[i].size(); ++j)
            ans[que[i][j].nd] = max(ans[que[i][j].nd], Q(i, que[i][j].st));
        //for(int j = 0; j < (int)que[i].size(); ++j)
            //ans[que[i][j].nd] = max(ans[que[i][j].nd], dp[que[i][j].st]);

        for(int j = 0; j < (int)kon[i].size(); ++j)
            Change(kon[i][j], II / 2 + 1);
    }
}

void Solve()
{
    int n, q, a, b;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tab[i] >> a >> b;
        ran[i] = make_pair(a, b);
        poc[max(0, i - a)].pb(i);
        kon[max(0, i - b)].pb(i);
    }
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        cin >> a >> b;
        ans[i] = -1;
        que[a].pb(make_pair(b, i));
    }
    Do(n);
    for(int i = 1; i <= n; ++i) tab[i] *= -1;
    Do(n);
    for(int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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