oj.uz

Submission #210718

# Submission time Handle Problem Language Result Execution time Memory
210718 2020-03-18T06:59:46 Z mhy908 Two Antennas (JOI19_antennas) C++14
0 / 100
 499 ms 40572 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+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]*=-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 Correct 22 ms 28536 KB Output is correct
2 Incorrect 23 ms 28536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28536 KB Output is correct
2 Incorrect 23 ms 28536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 39756 KB Output is correct
2 Correct 495 ms 40548 KB Output is correct
3 Correct 308 ms 38248 KB Output is correct
4 Correct 483 ms 40548 KB Output is correct
5 Correct 191 ms 34284 KB Output is correct
6 Correct 492 ms 40572 KB Output is correct
7 Correct 399 ms 39524 KB Output is correct
8 Correct 494 ms 40548 KB Output is correct
9 Correct 69 ms 30960 KB Output is correct
10 Correct 499 ms 40548 KB Output is correct
11 Correct 268 ms 37732 KB Output is correct
12 Correct 486 ms 40552 KB Output is correct
13 Incorrect 325 ms 39652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28536 KB Output is correct
2 Incorrect 23 ms 28536 KB Output isn't correct
3 Halted 0 ms 0 KB -