Submission #1074574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074574		phong	Two Antennas (JOI19_antennas)	C++17	100 / 100	435 ms	59852 KiB

antennas

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n,q;
pii a[nmax], b[nmax];
int c[nmax];
vector<int> adj[nmax];
vector<pii> Q[nmax];
bool tr[nmax << 2];
struct node{
    int ma, mi, ans;
}tree[nmax << 2];
pii st[nmax << 2];
pii lz[nmax << 2];
void combine(int id){
    tree[id].ans = max(tree[id << 1 | 1].ans, tree[id << 1].ans);
    tr[id] = tr[id << 1] | tr[id << 1 | 1];
    if(tree[id << 1].ma == -1) tree[id].ma = tree[id << 1 | 1].ma;
    else if(tree[id << 1 | 1].ma == -1) tree[id].ma = tree[id << 1].ma;
    else tree[id].ma = max(tree[id << 1].ma, tree[id << 1| 1].ma);
    if(tree[id << 1].mi == -1) tree[id].mi = tree[id << 1 | 1].mi;
    else if(tree[id << 1 | 1].mi == -1) tree[id].mi = tree[id << 1].mi;
    else tree[id].mi = min(tree[id << 1].mi, tree[id << 1| 1].mi);
}
void build(int id, int l, int r){
    tree[id].ma = tree[id].mi = -1;
    tree[id].ans = -oo;
//    cout << id << ' ' << tree[id].ans << endl;
    lz[id] = {-1, -1};
    if(l != r){
        int mid = r + l >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
}
void fix(int id, pii val){
//    cout << tr[id] << ' ' << val.fi << endl;
    if(!tr[id] || val.fi == -1) return;
    if(tree[id].ma != -1){
        tree[id].ans = max(tree[id].ans, abs(val.fi - tree[id].ma));
        tree[id].ans = max(tree[id].ans, abs(val.se - tree[id].ma));
    }
    if(tree[id].mi != -1){
        tree[id].ans = max(tree[id].ans, abs(val.fi - tree[id].mi));
        tree[id].ans = max(tree[id].ans, abs(val.se - tree[id].mi));
    }
    if(lz[id].fi == -1) lz[id].fi = val.fi;
    else lz[id].fi = max(lz[id].fi, val.fi);
    if(lz[id].se == -1) lz[id].se = val.se;
    else lz[id].se = min(lz[id].se, val.se);
}
void down(int id){
    fix(id << 1, lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = {-1, -1};
}

void update_1(int id, int l, int r, int u, int idx){
    if(l > u || r < u) return;
    if(l == r){
        tr[id] = idx;
        if(idx == 1){
            tree[id].ma = tree[id].mi = c[l];
        }
        else tree[id].ma = tree[id].mi = -1;
        return;
    }
    down(id);
    int mid = r + l >> 1;
    update_1(id << 1, l, mid, u, idx);
    update_1(id << 1| 1, mid + 1, r, u, idx);
    combine(id);
}

void update_2(int id, int l, int r, int u, int v, int val){
    if(l > v || r < u || u > v) return;
    if(l >= u && r <= v) return fix(id, {val, val});
    down(id);
    int mid = r + l >> 1;
    update_2(id << 1, l, mid,u, v, val);
    update_2(id << 1 | 1, mid + 1, r, u, v, val);
    combine(id);
}
int get(int id, int l, int r, int u, int v){
//    cout<< id << ' ' << tree[id].ans << endl;
    if(l >= u && r <= v) return tree[id].ans;
    down(id);
    int mid = r + l >> 1;
    if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
    if(mid + 1 > v) return get(id << 1, l, mid, u, v);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
int ans[nmax];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> c[i] >> a[i].fi >> a[i].se;
        int l = i + a[i].fi;
        int r = min(n, i + a[i].se);
        if(l <= r){
            Q[l].push_back({i, 1});
            Q[r + 1].push_back({i, 0});
        }
    }
    cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> b[i].fi >> b[i].se;
        adj[b[i].se].push_back(i);
    }
    build(1, 1, n);
    for(int i = 1; i <= n; ++i){
        for(auto [p, idx] : Q[i]){
            update_1(1, 1, n, p, idx);
        }
        int l = max(1ll, i - a[i].se);
        int r = i - a[i].fi;
        if(l <= r) update_2(1, 1, n, l, r, c[i]);
        for(auto p : adj[i]){
            ans[p] =  get(1, 1, n, b[p].fi, i);
        }
    }
    for(int i = 1; i <= q; ++i){
        if(ans[i] == -oo) cout << -1 << endl;
        else cout << ans[i] << endl;
    }



}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
1
1 3
*/

Compilation message (stderr)

antennas.cpp: In function 'void build(long long int, long long int, long long int)':
antennas.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = r + l >> 1;
      |                   ~~^~~
antennas.cpp: In function 'void update_1(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = r + l >> 1;
      |               ~~^~~
antennas.cpp: In function 'void update_2(long long int, long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     int mid = r + l >> 1;
      |               ~~^~~
antennas.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = r + l >> 1;
      |               ~~^~~
antennas.cpp: At global scope:
antennas.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main(){
      | ^~~~

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