Submission #209634

#	Time	Username	Problem	Language	Result	Execution time	Memory
209634		erd1	Two Antennas (JOI19_antennas)	C++14	100 / 100	1915 ms	44636 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
template<typename It>
ostream& _out(ostream& out, It b, It e){
    for(It i = b; i != e; i++)
        out << (i==b?"":" ") << *i;
    return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> a){
    return out << '(' << a.ff << ", " << a.ss << ')';
}
template<typename T, size_t N>
ostream& operator<<(ostream& out, array<T, N> a){
    return _out(out << '[', all(a)) << ']';
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> a){
    return _out(out << '[', all(a)) << ']';
}

struct node{
    node *L, *R;
    int lt = 1050000000, ans = -1, maxh = -1050000000,
        l, r;
    node(int ll, int rr){
        l = ll, r = rr;
        if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
    }
    void update(int x){
        if(lt <= x)return;
        lt = x;
        ans = max(ans, maxh-lt);
        //cout << "upd" << l<<r<<lt << " " << ans << endl;
    }
    void down(){
        //cout << lt << endl;
        L->update(lt), R->update(lt);
        lt = 1050000000;
        //cout << (array<int, 5>){l, r, ans ,L->ans, R->ans} << endl;
        assert(max(L->ans, R->ans) >= ans);
    }
    void up(){
        maxh = max(L->maxh, R->maxh);
        //assert(max(L->ans, R->ans) >= ans);
        ans = max(L->ans, R->ans);
    }
    void modify(int x, int val){
        if(l == r)return (void) (maxh = val, lt = 1050000000);
        down();
        (x <= (l+r>>1)?L:R)->modify(x, val);
        up();
        //cout << l << r << " " << maxh << endl;
    }
    int query(int ll, int rr){
        if(ll <= l && r <= rr)return ans;
        if(ll > r || rr < l)return -1;
        down();
        return max(L->query(ll, rr), R->query(ll, rr));
    }
    void modifyr(int ll, int rr, int x){
        if(ll <= l && r <= rr)return (void) update(x);
        if(ll > r || rr < l)return;
        down();
        L->modifyr(ll, rr, x);
        R->modifyr(ll, rr, x);
        up();
        //cout << l << r << "  " << ans << endl;
    }
    void clear(){
        lt = 1050000000, ans = -1, maxh = -1050000000;
        if(l != r)L->clear(), R->clear();
    }
} *root;
vector<array<int, 5>> events; // pos, type, (pos, val) / (l, id)
vector<int> qans;
signed main(){
    #ifdef LOCAL
    freopen("jizz.in","r",stdin);
    #endif
    int n, q;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int w, a, b;
        cin >> w >> a >> b;
        events.pb({i+a, 0, i, w, 0});
        events.pb({i+b, 3, i, 0, 0});
        events.pb({i, 1, i-b, i-a, w});
    }
    cin >> q; qans.resize(q, -1);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        events.pb({r, 2, l, i});
    }
    sort(all(events));
    root = new node(1, n);
    for(auto i: events){
        //cout << i << endl;
        switch(i[1]){
            case 0:
                root->modify(i[2], i[3]);
                break;
            case 1:
                root->modifyr(i[2],i[3], i[4]);
                break;
            case 2:
                qans[i[3]] = max(qans[i[3]], root->query(i[2],i[0]));
                break;
            case 3:
                root->modify(i[2], -1050000000);
                break;
        }
    }
    root->clear();
    for(auto i: events){
        switch(i[1]){
            case 0:
                root->modify(i[2], -i[3]);
                break;
            case 1:
                root->modifyr(i[2],i[3], -i[4]);
                break;
            case 2:
                qans[i[3]] = max(qans[i[3]], root->query(i[2],i[0]));
                break;
            case 3:
                root->modify(i[2], -1050000000);
                break;
        }
    }
    for(auto i: qans)cout << i << endl;
}

Compilation message (stderr)

antennas.cpp: In constructor 'node::node(int, int)':
antennas.cpp:32:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
                                   ~^~
antennas.cpp:32:59: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         if(l != r)L = new node(l, l+r>>1), R = new node((l+r>>1)+1, r);
                                                          ~^~
antennas.cpp: In member function 'void node::modify(int, int)':
antennas.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         (x <= (l+r>>1)?L:R)->modify(x, val);
                ~^~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65