Submission #1170472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170472		Zbyszek99	Two Antennas (JOI19_antennas)	C++20	0 / 100	231 ms	31484 KiB

antennas

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int tree_siz = 1024*512-1;
int min_on[tree_siz];
int max_M[tree_siz];
int max_ans[tree_siz];
bool is_spych[tree_siz];

void spych(int v)
{
    if(is_spych[v-1])
    {
        max_M[v*2-1] = max(max_M[v*2-1],max_M[v-1]);
        max_M[v*2] = max(max_M[v*2],max_M[v-1]);
        max_ans[v*2-1] = max(max_ans[v*2-1],max_M[v*2-1] - min_on[v*2-1]);
        max_ans[v*2] = max(max_ans[v*2],max_M[v*2] - min_on[v*2]);
        is_spych[v*2-1] = 1;
        is_spych[v*2] = 1;
    }
    is_spych[v-1] = 0;
}

void upd(int v)
{
    min_on[v-1] = min(min_on[v*2-1],min_on[v*2]);
    max_ans[v-1] = max(max_ans[v*2-1],max_ans[v*2]);
}

void set_max(int akt, int p1, int p2, int s1, int s2, int H)
{
    if(p2 < s1 || p1 > s2) return;
    if(p1 >= s1 && p2 <= s2)
    {
        max_M[akt-1] = max(max_M[akt-1],H);
        max_ans[akt-1] = max(max_ans[akt-1],H-min_on[akt-1]);
        is_spych[akt-1] = 1;
        return;
    }
    spych(akt);
    set_max(akt*2,p1,(p1+p2)/2,s1,s2,H);
    set_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2,H);
    upd(akt);
}

int get_max(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return -1;
    if(p1 >= s1 && p2 <= s2)
    {
        return max_ans[akt-1];
    }
    spych(akt);
    int w = max(get_max(akt*2,p1,(p1+p2)/2,s1,s2),get_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
    upd(akt);
    return w;
}

void set_on(int akt, int l, int r, int poz, int H)
{
    if(l == r)
    {
        min_on[akt-1] = H;
        return;
    }
    spych(akt);
    if(poz <= (l+r)/2)
    {
        set_on(akt*2,l,(l+r)/2,poz,H);
    }
    else
    {
        set_on(akt*2+1,(l+r)/2+1,r,poz,H);
    }
    upd(akt);
}

int query_ans[200'001];
vi start_events[200'001];
vi end_events[200'001];
vi queries[200'001];

void solve(int n, vi H, vi A, vi B, int q, vi L, vi R)
{
    rep(i,tree_siz)
    {
        min_on[i] = 1e9+1;
        max_M[i] = -1;
        max_ans[i] = -1;
        is_spych[i] = 0;
    }
    rep(i,n)
    {
        start_events[i] = {};
        end_events[i] = {};
        queries[i] = {};
    }
    rep(i,q)
    {
        queries[R[i]].pb(i);
    }
    rep(i,n)
    {
        if(i + A[i] < n)
        {
            start_events[i+A[i]].pb(i);
        }
        if(i + B[i] +1 < n)
        {
            end_events[i+B[i]+1].pb(i);
        }
    }
    rep(i,n)
    {
     //   cout << i << " i\n";
        forall(it,start_events[i])
        {
      //      cout << it << " start\n";
            set_on(1,0,tree_siz/2,it,H[it]);
        }
        forall(it,end_events[i])
        {
       //     cout << it << " end\n";
            set_on(1,0,tree_siz/2,it,1e9+1);
        }
        if(i - A[i] >= 0)
        {
            set_max(1,0,tree_siz/2,max(0,i-B[i]),i-A[i],H[i]);
        }
        forall(it,queries[i])
        {
            query_ans[it] = max(query_ans[it],get_max(1,0,tree_siz/2,L[it],R[it]-1));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n;
    cin >> n;
    vi H(n);
    vi A(n);
    vi B(n);
    rep(i,n)
    {
        cin >> H[i] >> A[i] >> B[i];
    }
    int q;
    cin >> q;
    vi L(q);
    vi R(q);
    rep(i,q)
    {
        query_ans[i] = -1;
        cin >> L[i] >> R[i];
        L[i]--;
        R[i]--;
    }
    solve(n,H,A,B,q,L,R);
   // cout << "\n\nrev\n\n";
    reverse(all(H));
    reverse(all(A));
    reverse(all(B));
    rep(i,q)
    {
        L[i] = n-L[i]-1;
        R[i] = n-R[i]-1;
        swap(L[i],R[i]);
    }
    solve(n,H,A,B,q,L,R);
    rep(i,q)
    {
        cout << query_ans[i] << "\n";
    }
}

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