oj.uz

Submission #210720

# Submission time Handle Problem Language Result Execution time Memory
210720 2020-03-18T07:00:47 Z mhy908 Two Antennas (JOI19_antennas) C++14
0 / 100
 543 ms 40548 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]=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 24 ms 28536 KB Output is correct
2 Incorrect 24 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 24 ms 28536 KB Output is correct
2 Incorrect 24 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 447 ms 39780 KB Output is correct
2 Correct 506 ms 40420 KB Output is correct
3 Correct 306 ms 38116 KB Output is correct
4 Correct 499 ms 40548 KB Output is correct
5 Correct 196 ms 34152 KB Output is correct
6 Correct 542 ms 40420 KB Output is correct
7 Correct 401 ms 39396 KB Output is correct
8 Correct 543 ms 40420 KB Output is correct
9 Correct 66 ms 30832 KB Output is correct
10 Correct 491 ms 40420 KB Output is correct
11 Correct 274 ms 37608 KB Output is correct
12 Correct 501 ms 40420 KB Output is correct
13 Incorrect 353 ms 39528 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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