oj.uz

Submission #210717

# Submission time Handle Problem Language Result Execution time Memory
210717 2020-03-18T06:59:08 Z mhy908 Two Antennas (JOI19_antennas) C++14
0 / 100
 597 ms 46440 KB 
#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]=max(lazy[num], qu);
            x[num]=max(x[num], lazy[num]-c[num]);
            return;
        }
        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(e<a||s>b)return -llinf;
        if(a<=s&&e<=b)return x[num];
        propogate(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);
        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]*=-1;
    solve();
    for(int i=1; i<=q; i++)printf("%lld\n", ans[i]);
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:107: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:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
antennas.cpp:111: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.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 40908 KB Output is correct
2 Correct 555 ms 46364 KB Output is correct
3 Correct 332 ms 39912 KB Output is correct
4 Correct 561 ms 46200 KB Output is correct
5 Correct 253 ms 36844 KB Output is correct
6 Correct 597 ms 46308 KB Output is correct
7 Correct 468 ms 42080 KB Output is correct
8 Correct 549 ms 46180 KB Output is correct
9 Correct 75 ms 31220 KB Output is correct
10 Correct 535 ms 46440 KB Output is correct
11 Correct 290 ms 38892 KB Output is correct
12 Correct 533 ms 46308 KB Output is correct
13 Incorrect 374 ms 42724 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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