oj.uz

Submission #210723

# Submission time Handle Problem Language Result Execution time Memory
210723 2020-03-18T07:06:23 Z mhy908 Two Antennas (JOI19_antennas) C++14
0 / 100
 491 ms 40552 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(qu, lazy[num]);
            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(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

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 440 ms 39652 KB Output is correct
2 Correct 476 ms 40420 KB Output is correct
3 Correct 320 ms 38116 KB Output is correct
4 Correct 491 ms 40424 KB Output is correct
5 Correct 197 ms 34152 KB Output is correct
6 Correct 485 ms 40420 KB Output is correct
7 Correct 420 ms 39396 KB Output is correct
8 Correct 473 ms 40424 KB Output is correct
9 Correct 69 ms 30832 KB Output is correct
10 Correct 476 ms 40420 KB Output is correct
11 Correct 280 ms 37608 KB Output is correct
12 Correct 478 ms 40552 KB Output is correct
13 Incorrect 335 ms 39524 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 -