Submission #210725

#	Time	Username	Problem	Language	Result	Execution time	Memory
210725		mhy908	Two Antennas (JOI19_antennas)	C++14	22 / 100	558 ms	41168 KiB

antennas

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=987654321987654321;
const int inf=2000000000;

struct SEGMENT_TREE{
    LL x[800010], c[800010], lazy[800010];
    void init(){
        for(int i=1; i<800000; i++){
            x[i]=lazy[i]=-llinf;
            c[i]=llinf;
        }
    }
    void propogate(int num){
        x[num*2]=max(x[num*2], lazy[num]-c[num*2]);
        lazy[num*2]=max(lazy[num*2], lazy[num]);
        x[num*2+1]=max(x[num*2+1], lazy[num]-c[num*2+1]);
        lazy[num*2+1]=max(lazy[num*2+1], lazy[num]);
        x[num]=max(x[num], max(x[num*2], x[num*2+1]));
        lazy[num]=-llinf;
    }
    void update(int num, int s, int e, int m, LL qu){
        if(s==e){
            c[num]=qu;
            return;
        }
        propogate(num);
        int mid=(s+e)/2;
        if(m<=mid)update(num*2, s, mid, m, qu);
        else update(num*2+1, mid+1, e, m, qu);
        c[num]=min(c[num*2], c[num*2+1]);
        x[num]=max(x[num*2], x[num*2+1]);
    }
    void alter(int num, int s, int e, int a, int b, LL qu){
        if(s!=e)propogate(num);
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            lazy[num]=qu;
            x[num]=max(x[num], lazy[num]-c[num]);
            return;
        }
        propogate(num);
        int mid=(s+e)/2;
        alter(num*2, s, mid, a, b, qu);
        alter(num*2+1, mid+1, e, a, b, qu);
        c[num]=min(c[num*2], c[num*2+1]);
        x[num]=max(x[num*2], x[num*2+1]);
    }
    LL query(int num, int s, int e, int a, int b){
        if(s!=e)propogate(num);
        if(e<a||s>b)return -llinf;
        if(a<=s&&e<=b)return x[num];
        int mid=(s+e)/2;
        LL ans=max(query(num*2, s, mid, a, b), query(num*2+1, mid+1, e, a, b));
        c[num]=min(c[num*2], c[num*2+1]);
        x[num]=max(x[num*2], x[num*2+1]);
        return ans;
    }
}seg;

int n, q;
pii range[200010];
pii query[200010];
LL ans[200010], h[200010];

vector<pii> qu[200010], upd[200010];
void solve(){
    for(int i=1; i<=n; i++){
        qu[i].clear();
        upd[i].clear();
    }
    seg.init();
    for(int i=1; i<=n; i++){
        int t1=min(i+range[i].F, n+1);
        int t2=min(n, i+range[i].S)+1;
        upd[t1].pb(mp(i, 1));
        upd[t2].pb(mp(i, 0));
    }
    for(int i=1; i<=q; i++)qu[query[i].S].pb(mp(query[i].F, i));
    for(int i=1; i<=n; i++){
        for(auto j:upd[i]){
            if(j.S)seg.update(1, 1, n, j.F, h[j.F]);
            else seg.update(1, 1, n, j.F, llinf);
        }
        if(i-range[i].F>=1){
            seg.alter(1, 1, n, max(1, i-range[i].S), i-range[i].F, h[i]);
        }
        for(auto j:qu[i]){
            ans[j.S]=max(ans[j.S], seg.query(1, 1, n, j.F, i-1));
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
        ans[i]=-1;
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++)scanf("%d %d", &query[i].F, &query[i].S);
    solve();
    for(int i=1; i<=n; i++)h[i]=1000000000-h[i];
    solve();
    for(int i=1; i<=q; i++)printf("%lld\n", ans[i]);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
antennas.cpp:112:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=q; i++)scanf("%d %d", &query[i].F, &query[i].S);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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