oj.uz

Submission #653174

# Submission time Handle Problem Language Result Execution time Memory
653174 2022-10-26T01:24:24 Z perchuts Two Antennas (JOI19_antennas) C++17
22 / 100
 758 ms 30876 KB 
//https://codeforces.com/blog/entry/66022?#comment-500622 

//line sweep com 4 tipos de eventos: 
//1-query 
//2-inserir antena 
//3-remover antena 
//4-atualizar a resposta 

//pra processar eventos, usar seg + lazy

//o porquê de precisar processar os eventos nas 2 ordens: note que quermos selecionar dois indices i<j pra cada query, e na seg,
//ou h[i]>h[j] ou h[j]>h[i]. Daí, queremos maximizar ou h[i] ou h[j]. Com os eventos crescendo no tempo maximizamos h[i] e maximizamos
//h[j] diminuindo no tempo. Dá pra fazer tudo de uma vez, mas o código ficaria mais confuso.
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 1e9+1;
const int mod = 1e9+7;
const int maxn = 2e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

pair<int, ii> ant[maxn];

int n, ans[maxn], lazy[4*maxn], c[4*maxn], d[4*maxn];

ii qu[maxn];

void push(int i,int l,int r){
    if(lazy[i]==inf)return;

    ckmax(d[i], c[i] - lazy[i]);

    if(l!=r)ckmin(lazy[2*i], lazy[i]), ckmin(lazy[2*i+1], lazy[i]);

    lazy[i] = inf;
}

void update(int i,int l,int r,int x,int y,int k){
    if(x>y)return;
    
    push(i,l,r);

    if(l>y||r<x)return;
    
    if(x<=l&&r<=y){
        ckmin(lazy[i], k);
        push(i,l,r); 
        return;
    }

    int md = (l+r)/2;

    update(2*i, l, md, x, y, k), update(2*i+1, md+1, r, x, y, k);

    d[i] = max(d[2*i], d[2*i+1]), c[i] = max(c[2*i], c[2*i+1]);
}

int query(int i,int l,int r,int x,int y){
    push(i,l,r);

    if(l>y||r<x)return -1;

    if(x<=l&&r<=y)return d[i];

    int md = (l+r)/2;

    return max(query(2*i, l, md, x, y), query(2*i+1, md+1, r, x, y));
}

void upd(int i,int l,int r,int x,int k){
    push(i,l,r);

    if(l>x||r<x)return;

    if(l==r){
        c[i] = k;
        return;
    }   

    int md = (l+r)/2;

    upd(2*i, l, md, x, k), upd(2*i+1, md+1, r, x, k);

    d[i] = max(d[2*i], d[2*i+1]), c[i] = max(c[2*i], c[2*i+1]);
}

void init(){
    for(int i=1;i<=4*n;++i)d[i] = c[i] = -1, lazy[i] = inf;
}

int main(){_
    cin>>n;

    vector<pair<int,ii>>eventos1, eventos2;

    for(int i=0;i<n;++i){
        cin>>ant[i].first>>ant[i].second.first>>ant[i].second.second;
        
        eventos1.pb({i+ant[i].second.first, {-2, i}});
        eventos1.pb({i, {-1, i}});
        eventos1.pb({i+ant[i].second.second, {n, i}});

        eventos2.pb({i-ant[i].second.first, {n+1, i}});
        eventos2.pb({i, {n, i}});
        eventos2.pb({i-ant[i].second.second, {-1, i}});
    }

    int q;cin>>q;

    fill(ans,ans+q,-1);

    for(int i=0;i<q;++i){
        cin>>qu[i].first>>qu[i].second;
        --qu[i].first, --qu[i].second;
        eventos1.pb({qu[i].second,{i, qu[i].first}});
        eventos2.pb({qu[i].first,{i, qu[i].second}});
    }

    sort(all(eventos1)), sort(rbegin(eventos2), rend(eventos2));

    init();

    for(auto [x,p]:eventos1){
        auto [t, y] = p;
        if(t==-1){//atualizar o d (resposta)
            update(1,0,n-1, max(0, y-ant[y].second.second), y-ant[y].second.first, ant[y].first);
        }
        else if(t==-2){//inserir o y na seg
            upd(1,0,n-1, y, ant[y].first);                                          
        }
        else if(t==n){//remover o y da seg
            upd(1,0,n-1, y, -inf);
        }
        else{//responder a query de indice t
            ckmax(ans[t], query(1,0,n-1, y, x));
        }
    }

    init();

    for(auto [x,p]:eventos2){
        auto [t, y] = p;
        if(t==n){//atualizar o d (resposta)
            update(1,0,n-1, y+ant[y].second.first, min(n-1,y+ant[y].second.second), ant[y].first);
        }
        else if(t==n+1){//inserir o y na seg
            upd(1,0,n-1, y, ant[y].first);
        }
        else if(t==-1){//remover o y da seg
            upd(1,0,n-1, y, -inf);
        }
        else{//responder a query de indice t
            ckmax(ans[t], query(1,0,n-1, x, y));
        }
    }

    for(int i=0;i<q;++i)cout<<ans[i]<<endl;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 27764 KB Output is correct
2 Correct 758 ms 30792 KB Output is correct
3 Correct 460 ms 21784 KB Output is correct
4 Correct 709 ms 30844 KB Output is correct
5 Correct 281 ms 14540 KB Output is correct
6 Correct 700 ms 30796 KB Output is correct
7 Correct 634 ms 26820 KB Output is correct
8 Correct 736 ms 30784 KB Output is correct
9 Correct 91 ms 5260 KB Output is correct
10 Correct 701 ms 30876 KB Output is correct
11 Correct 394 ms 19448 KB Output is correct
12 Correct 699 ms 30792 KB Output is correct
13 Correct 447 ms 30692 KB Output is correct
14 Correct 416 ms 30704 KB Output is correct
15 Correct 432 ms 30696 KB Output is correct
16 Correct 416 ms 30692 KB Output is correct
17 Correct 453 ms 30744 KB Output is correct
18 Correct 474 ms 30772 KB Output is correct
19 Correct 421 ms 30716 KB Output is correct
20 Correct 430 ms 30740 KB Output is correct
21 Correct 434 ms 30660 KB Output is correct
22 Correct 438 ms 30792 KB Output is correct
23 Correct 441 ms 30712 KB Output is correct
24 Correct 447 ms 30708 KB Output is correct

Subtask #4
0 / 65.0

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