oj.uz

Submission #216032

# Submission time Handle Problem Language Result Execution time Memory
216032 2020-03-26T16:33:22 Z Alexa2001 Two Antennas (JOI19_antennas) C++17
22 / 100
 516 ms 55592 KB 
#include <bits/stdc++.h>
#define yes { cout << "YES" << endl; exit(0); }
#define no { cout << "NO" << endl; exit(0); }
#define impossible { cout << "Impossible" << endl; exit(0); }

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;

const int inf = 1e9;
const int Nmax = 4e5 + 5;

int L[Nmax], R[Nmax], ans[Nmax], H[Nmax], A[Nmax], B[Nmax];
int n, q;

vector<int> when[Nmax], add[Nmax], er[Nmax];


#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


class SegTree
{
    int val[Nmax<<2], best[Nmax<<2], lazy[Nmax<<2];

    void propag(int node)
    {
        if(lazy[node] == inf) return;
        
        lazy[left_son] = min(lazy[left_son], lazy[node]);
        best[left_son] = max(best[left_son], val[left_son] - lazy[left_son]);

        lazy[right_son] = min(lazy[right_son], lazy[node]);
        best[right_son] = max(best[right_son], val[right_son] - lazy[right_son]);
        
        lazy[node] = inf;
    }

public:
    void init(int node, int st, int dr)
    {
        best[node] = -inf;
        val[node] = -inf;
        lazy[node] = inf;
        
        if(st == dr) return;

        init(left_son, st, mid);
        init(right_son, mid+1, dr);
    }

    void upd1(int node, int st, int dr, int pos, int mxVal)
    {
        if(st == dr)
        {
            val[node] = mxVal;
       //     best[node] = max(best[node], val[node] - lazy[node]);
            lazy[node] = inf;
            return;
        }

        propag(node);

        if(pos <= mid) upd1(left_son, st, mid, pos, mxVal);
            else upd1(right_son, mid+1, dr, pos, mxVal);

        val[node] = max(val[left_son], val[right_son]);
        best[node] = max(best[left_son], best[right_son]);
    }

    void upd2(int node, int st, int dr, int L, int R, int mnVal)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] = min(lazy[node], mnVal);
            best[node] = max(best[node], val[node] - lazy[node]);
            return;
        }

        propag(node);

        if(L <= mid) upd2(left_son, st, mid, L, R, mnVal);
        if(mid < R) upd2(right_son, mid+1, dr, L, R, mnVal);

    //    val[node] = max(val[left_son], val[right_son]);
        best[node] = max(best[left_son], best[right_son]);
    }

    int query(int node, int st, int dr, int L, int R)
    {
        if(L > dr || R < st) return -inf;
        if(L <= st && dr <= R) return best[node];

        propag(node);
        return max( query(left_son, st, mid, L, R), query(right_son, mid+1, dr, L, R) );
    }
} aint;


void solve()
{
    aint.init(1, 1, n);

    int i;
    for(i=1; i<=n; ++i) 
    {
        add[i+A[i]].push_back(i);
        er[i+B[i]].push_back(i);
    }

    for(i=1; i<=q; ++i)
        when[R[i]].push_back(i);

    for(i=1; i<=n; ++i)
    {
        for(auto it : add[i])
            aint.upd1(1, 1, n, it, H[it]);
        
        int l, r;
        l = max(1, i - B[i]);
        r = max(1, i - A[i]);

        aint.upd2(1, 1, n, l, r, H[i]);

        for(auto it : when[i])
            ans[it] = max(ans[it], aint.query(1, 1, n, L[it], i));

        for(auto it : er[i])
            aint.upd1(1, 1, n, it, -inf);
    }
}

void clr()
{
    int i;
    for(i=1; i<=n; ++i)
    {
        when[i].clear();
        add[i].clear();
        er[i].clear();
    }
}

int main()
{
    cin.sync_with_stdio(false); cin.tie(0);
    
    int i;
    cin >> n;
    for(i=1; i<=n; ++i) cin >> H[i] >> A[i] >> B[i];
    
    cin >> q;
    for(i=1; i<=q; ++i)
    {
        ans[i] = -1;
        cin >> L[i] >> R[i];
    }    

    solve();
    clr();

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

    reverse(H+1, H+n+1);
    reverse(A+1, A+n+1);
    reverse(B+1, B+n+1);

    solve();

    for(i=1; i<=q; ++i) cout << ans[i] << '\n';

    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 28544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 28544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 53492 KB Output is correct
2 Correct 516 ms 55592 KB Output is correct
3 Correct 356 ms 49400 KB Output is correct
4 Correct 513 ms 55496 KB Output is correct
5 Correct 235 ms 41208 KB Output is correct
6 Correct 512 ms 55544 KB Output is correct
7 Correct 479 ms 52692 KB Output is correct
8 Correct 510 ms 55456 KB Output is correct
9 Correct 84 ms 32760 KB Output is correct
10 Correct 502 ms 55548 KB Output is correct
11 Correct 294 ms 44664 KB Output is correct
12 Correct 508 ms 55556 KB Output is correct
13 Correct 270 ms 50800 KB Output is correct
14 Correct 263 ms 50240 KB Output is correct
15 Correct 266 ms 50036 KB Output is correct
16 Correct 252 ms 50804 KB Output is correct
17 Correct 270 ms 51092 KB Output is correct
18 Correct 282 ms 50172 KB Output is correct
19 Correct 270 ms 50304 KB Output is correct
20 Correct 263 ms 50500 KB Output is correct
21 Correct 266 ms 51452 KB Output is correct
22 Correct 268 ms 50548 KB Output is correct
23 Correct 281 ms 50468 KB Output is correct
24 Correct 260 ms 49912 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 28544 KB Output isn't correct
2 Halted 0 ms 0 KB -