Submission #106106

#	Time	Username	Problem	Language	Result	Execution time	Memory
106106		antimirage	Two Antennas (JOI19_antennas)	C++14	100 / 100	1344 ms	48476 KiB

antennas

#include<bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5 + 5;

int n, c[N], a[N], b[N], ans[N], L[N], R[N], q;

struct tree{
    int val, sc, must;
    tree(){
        val = -1;
        sc = -1e9;
        must = 1e9;
    }
};

tree t[N * 4];

void push (int v, int tl, int tr){

    t[v].val = max( t[v].val, t[v].sc - t[v].must );

    if (tl != tr){
        t[v + v].must = min( t[v + v].must, t[v].must );
        t[v + v + 1].must = min( t[v + v + 1].must, t[v].must );
    }
    t[v].must = 1e9;
}

void update2 (int pos, int val, int v = 1, int tl = 1, int tr = n)
{
    push(v, tl, tr);

    if (tl == tr){
        t[v].sc = val;
    }
    else{

        int tm = (tl + tr) >> 1;

        if (pos <= tm)
            update2( pos, val, v + v, tl, tm );
        else
            update2( pos, val, v + v + 1, tm + 1, tr );

        t[v].sc = max(t[v + v].sc, t[v + v + 1].sc);
    }
}
void update1 (int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
    push(v, tl, tr);

    if (l > r || tl > r || l > tr) return;

    if (l <= tl && tr <= r){

        t[v].must = min( t[v].must, val );
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) >> 1;

    update1(l, r, val, v + v, tl, tm);
    update1(l, r, val, v + v + 1, tm + 1, tr);

    t[v].val = max( t[v + v].val, t[v + v + 1].val );
}
int get (int l, int r, int v = 1, int tl = 1, int tr = n)
{
    if (tl > r || l > tr) return -1;

    push(v, tl, tr);

    if (l <= tl && tr <= r)
        return t[v].val;

    int tm = (tl + tr) >> 1;

    return max( get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr) );
}
vector <int> add[N], del[N], calc[N];

void solve (){

    for (int i = 1; i <= n; i++)
        add[i].clear(),
        del[i].clear(),
        calc[i].clear();

    for (int i = 1; i <= q; i++){
        calc[ R[i] ].pb(i);
    }

    for (int i = 1; i <= n; i++){

        for (auto it : add[i]){
            update2( it, c[it] );
        }
        for (auto it : del[i]){
            update2( it, -1e9 );
        }
        update1( max(1, i - b[i]), i - a[i], c[i] );

        if (i + a[i] <= n)
            add[ i + a[i] ].pb( i );

        if (i + b[i] + 1 <= n)
            del[ i + b[i] + 1 ].pb( i );

        for (auto it : calc[i]){
            ans[it] = max( ans[it], get( L[it], i ) );
        }
    }
    for (int i = 0; i < 4 * N; i++)
        t[i] = tree();
}

main(){

    memset(ans, -1, sizeof(ans));

    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d%d%d", &c[i], &a[i], &b[i]);
    }
    cin >> q;
    for (int i = 1; i <= q; i++){
        scanf("%d%d", &L[i], &R[i]);
    }
    solve();

    for (int i = 1; i <= q; i++){
        L[i] = n - L[i] + 1;
        R[i] = n - R[i] + 1;
        swap(L[i], R[i]);
    }
    reverse(c + 1, c + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);

    solve();

    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
}
/**
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
**/

Compilation message (stderr)

antennas.cpp:125:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
antennas.cpp: In function 'int main()':
antennas.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &c[i], &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &L[i], &R[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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