Submission #589334

#	Time	Username	Problem	Language	Result	Execution time	Memory
589334		snokes	Two Antennas (JOI19_antennas)	C++17	100 / 100	574 ms	45156 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL

#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())

const int INF = 1e9 + 5;

struct Op
{
    int mn, mx;
    Op()
    {
        mn = INF;
        mx = -INF;
    }
    Op(int a, int b)
    {
        mn = a;
        mx = b;
    }
    Op& operator += (Op a)
    {
        mn = min(mn, a.mn);
        mx = max(mx, a.mx);
        return *this;
    }
};

struct Node
{
    int mn, mx, best;
    Node()
    {
        mn = INF;
        mx = -INF;
        best = -INF;
    }
    Node(int _mn, int _mx, int _best = -INF)
    {
        mn = _mn;
        mx = _mx;
        best = _best;
    }
    void apply(Op op)
    {
        if(mn == INF) return;
        best = max(best, max(mx - op.mn, op.mx - mn));
    }
};

ostream& operator << (ostream& os, Node n) {return os << "(" << n.mn << ", " << n.mx << " -> " << n.best << ")";}
ostream& operator << (ostream& os, Op n) {return os << "(" << n.mn << ", " << n.mx << ")";}

bool operator != (Op a, Op b){ return a.mn != b.mn || a.mx != b.mx; }
bool operator == (Node a, Node b) {return a.mn == b.mn && a.mx == b.mx && a.best == b.best;}

Node operator + (Node a, Node b)
{
    Node ret;
    if(a == Node()) ret = b;
    else if(b == Node()) ret = a;
    else
    {
        ret.mn = min(a.mn, b.mn);
        ret.mx = max(a.mx, b.mx);
        ret.best = max(a.best, b.best);
    }
    return ret;
}



struct SegTree
{
    vt<Node> S;
    vt<Op> lazy;
    int N;
    SegTree(int _N)
    {
        N = 1;
        while(N < _N) N *= 2;
        S.resize(2 * N);
        lazy.resize(2 * N);
    }

    void push(int i)
    {
        if(lazy[i] != Op())
        {
            S[i].apply(lazy[i]);
            if(i < N)
            {
                lazy[2 * i] += lazy[i];
                lazy[2 * i + 1] += lazy[i];
            }
            lazy[i] = Op();
        }
    }

    int qry(int l, int r, int a, int b, int i)
    {
        push(i);
        if(l <= a && b <= r) return S[i].best;
        if(r < a || b < l) return -INF;
        int m = (a + b) / 2;
        return max(qry(l, r, a, m, 2 * i), qry(l, r, m + 1, b, 2 * i + 1));
    }
    int qry(int l, int r) {return qry(l, r, 1, N, 1);}

    void apply(int l, int r, Op o, int a, int b, int i)
    {
        push(i);
        if(l <= a && b <= r)
        {
            lazy[i] += o;
            push(i);
            return;
        }
        if(r < a || b < l) return;
        int m = (a + b) / 2;
        apply(l, r, o, a, m, 2 * i);
        apply(l, r, o, m + 1, b, 2 * i + 1);
        S[i] = S[2 * i] + S[2 * i + 1];
    }
    void apply(int l, int r, Op o) {apply(l, r, o, 1, N, 1);}

    void upd(int i, Node n)
    {
        qry(i, i); //Clear lazy
        int u = i + N - 1;
        S[u].mx = n.mx;
        S[u].mn = n.mn;
        //dbg(u, S[u]);
        for(u /= 2; u > 0; u /= 2)
        {
            S[u] = S[2 * u] + S[2 * u + 1];
        }
    }
};


int N, Q;
vt<int> H, A, B;
vt<pair<int, int>> queries;

vt<int> solve()
{
    vt<vt<int>> act(N + 1), deact(N + 1), qry(N + 1);
    for(int i = 0; i < N; i++)
    {
        act[min(N, i + A[i])].pb(i);
        deact[min(N, i + B[i] + 1)].pb(i);
    }

    vt<int> ans(Q);
    vt<int> lb(Q);
    for(int i = 0; i < Q; i++)
    {
        auto [L, R] = queries[i];
        qry[R].pb(i);
        lb[i] = L;
    }

    SegTree s(N);

    for(int i = 0; i < N; i++)
    {
        for(int x : deact[i]) s.upd(x + 1, Node());
        for(int x : act[i]) s.upd(x + 1, Node(H[x], H[x]));

        //Apply myself
        s.apply(1 + max(0, i - B[i]), 1 + max(-1, i - A[i]), Op(H[i], H[i]));
        //dbg(s.S);

        for(int x : qry[i]) ans[x] = s.qry(1 + lb[x], i + 1);
    }
    for(int& x : ans) x = max(-1, x);
    return ans;
}

vt<int> brute()
{
    vt<int> ans(Q);
    for(int i = 0; i < Q; i++)
    {
        int best = -1;
        for(int j = queries[i].first; j <= queries[i].second; j++)
        {
            for(int k = j + 1; k <= queries[i].second; k++)
            {
                if(j + A[j] <= k && k <= j + B[j] && k - B[k] <= j && j <= k - A[k])
                {
                    best = max(best, abs(H[j] - H[k]));
                }
            }
        }
        ans[i] = best;
    }
    return ans;
}

//#define TESTING

random_device rd;
mt19937 rng(rd());
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    #ifdef TESTING
    while(true)
    {
        N = uid(2, 100);
        H = vt<int>(N);
        A = vt<int>(N);
        B = vt<int>(N);
        for(int& x : H) x = uid(1, 1000);
        for(int i = 0; i < N; i++)
        {
            A[i] = uid(1, N - 1);
            B[i] = A[i] + uid(0, N - 1 - A[i]);
        }
        Q = uid(1, 100);
        queries = vt<pair<int, int>>(Q);
        for(int i = 0; i < Q; i++)
        {
            queries[i].first = uid(0, N - 1);
            queries[i].second = queries[i].first + uid(0, N - 1 - queries[i].first);
        }
        if(solve() != brute())
        {
            dbg(solve());
            dbg(brute());
            cout << N << "\n";
            for(int i = 0; i < N; i++) cout << H[i] << " " << A[i] << " " << B[i] << "\n";
            cout << Q << "\n";
            for(auto& [a, b] : queries) cout << 1 + a << " " << 1 + b << "\n";
            exit(0);
        }

    }
    #else
    cin >> N;
    H = vt<int>(N);
    A = vt<int>(N);
    B = vt<int>(N);
    for(int i = 0; i < N; i++) cin >> H[i] >> A[i] >> B[i];
    cin >> Q;
    queries = vt<pair<int, int>>(Q);
    for(int i = 0; i < Q; i++)
    {
        cin >> queries[i].first >> queries[i].second, --queries[i].first, --queries[i].second;
    }
    for(int x : solve()) cout << x << "\n";
    #endif // TESTING

}

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