제출 #579045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579045		mousebeaver	Two Antennas (JOI19_antennas)	C++14	22 / 100	265 ms	14704 KiB

antennas

#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define ppii pair<pii, int>
#include <bits/stdc++.h>
using namespace std;

int left(int i)
{
    return 2*i;
}

int right(int i)
{
    return 2*i+1;
}

int par(int i)
{
    return i/2;
}

ll query(vector<ll>& s, int a, int b, int l, int r, int i)
{
    //cout<<"HERE: "<<i<<" => <<endl;
    if(l <= a && b <= r)
    {
        //cout<<"END"<<endl;
        return s[i];
    }
    if(r < a || b < l)
    {
        //cout<<"END"<<endl;
        return numeric_limits<ll>::min();
    }
    int m = (a+b)/2;
    return max(query(s, a, m, l, r, left(i)), query(s, m+1, b, l, r, right(i)));
}

void propagate(vector<ll>& s, int i)
{
    s[i] = max(s[left(i)], s[right(i)]);
    if(i > 1)
    {
        propagate(s, par(i));
    }
}

void update(vector<ll>& s, int i, ll v)
{
    s[i+(s.size()/2)] = v;
    propagate(s, par(i+(s.size()/2)));
}

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

    int n;
    cin>>n;
    vector<ll> h(n); //heights
    vector<pii> a(n); //Bereiche
    for(int i = 0; i < n; i++)
    {
        cin>>h[i]>>a[i].first>>a[i].second;
    }

    int segnodes = 2*pow(2, ceil(log2(n)));
    //Segtrees for max:
    vector<ll> s(segnodes, numeric_limits<ll>::min()); //positive heights
    vector<ll> ns(segnodes, numeric_limits<ll>::min()); //negative heights

    int q;
    cin>>q;
    vector<ppii> requests(q);
    for(int i = 0; i < q; i++)
    {
        int l, r;
        cin>>l>>r;
        requests[i] = {{l, r}, i};
    }
    sort(requests.begin(), requests.end());
    vector<ll> result(q);
    int qindex = 0;

    while(qindex < q)
    {
        if(requests[qindex].first.first == requests[qindex].first.second)
        {
            result[requests[qindex].second] = -1;
            qindex++;
        }
        else
        {
            int l = requests[qindex].first.first;
            ll output = -1;
            priority_queue<pii, vector<pii>, greater<pii>> st; //starts: distance, index
            priority_queue<pii, vector<pii>, greater<pii>> g; //goals: distance, index
            st.push({a[l-1].first+l, l});
            g.push({a[l-1].second+l+1, l});
            //cout<<"___________________________________NEW QUERY!!!"<<endl;

            int j = l+1;
            while(qindex < q && requests[qindex].first.first == l)
            {
                int r = requests[qindex].first.second;
                //cout<<"-------->: "<<j<<endl;
                while(!st.empty() && st.top().first == j)
                {
                    update(s, st.top().second-1, h[st.top().second-1]);
                    update(ns, st.top().second-1, 0-h[st.top().second-1]);
                    //cout<<"TAKE "<<st.top().second<<endl;
                    st.pop();
                }
                while(!g.empty() && g.top().first == j)
                {
                    update(s, g.top().second-1, numeric_limits<ll>::min());
                    update(ns, g.top().second-1, numeric_limits<ll>::min());
                    //cout<<"DROP "<<g.top().second<<endl;
                    g.pop();
                }
                st.push({a[j-1].first+j, j});
                g.push({a[j-1].second+j+1, j});
                /*cout<<"SEGTREE S: "<<endl;
                for(ll y : s)
                {
                    cout<<y<<" ";
                }
                cout<<endl;*/
                int left = max(j-a[j-1].second, l);
                int right = max(j-a[j-1].first, l);
                //cout<<"LEFT: "<<left<<", RIGHT: "<<right<<endl;
                ll biggest = query(s, 1, segnodes/2, left, right, 1);
                ll smallest = query(ns, 1, segnodes/2, left, right, 1);
                //cout<<"BIGGEST: "<<biggest<<", SMALLEST: "<<smallest<<endl;
                if(biggest > numeric_limits<ll>::min())
                {
                    //cout<<"HEREBIG"<<endl;
                    output = max(output, abs(h[j-1]-biggest));
                }
                if(smallest > numeric_limits<ll>::min())
                {
                    //cout<<"HERESMALL"<<endl;
                    output = max(output, abs(h[j-1]+smallest));
                }
                //cout<<"OUTPUT: "<<output<<endl;
                if(j == r)
                {
                    while(qindex < q && requests[qindex].first.second == r)
                    {
                        result[requests[qindex].second] = output;
                        qindex++;
                    }
                }
                j++;
            }
            s.assign(segnodes, numeric_limits<ll>::min());
            ns.assign(segnodes, numeric_limits<ll>::min());        }

    }

    for(ll i : result)
    {
        cout<<i<<"\n";
    }

    return 0;
}

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