oj.uz

답안 #579040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579040 2022-06-18T10:26:05 Z mousebeaver Two Antennas (JOI19_antennas) C++14
22 / 100
 361 ms 15056 KB 
#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)
    {
        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++;
        }
        while(!g.empty())
        {
            update(s, g.top().second-1, numeric_limits<ll>::min());
            update(ns, g.top().second-1, numeric_limits<ll>::min());
            g.pop();
        }
    }

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

    return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 15056 KB Output is correct
2 Correct 293 ms 14912 KB Output is correct
3 Correct 179 ms 12932 KB Output is correct
4 Correct 342 ms 14832 KB Output is correct
5 Correct 96 ms 7656 KB Output is correct
6 Correct 245 ms 14856 KB Output is correct
7 Correct 219 ms 13400 KB Output is correct
8 Correct 251 ms 14904 KB Output is correct
9 Correct 34 ms 2476 KB Output is correct
10 Correct 271 ms 14888 KB Output is correct
11 Correct 138 ms 8256 KB Output is correct
12 Correct 248 ms 14832 KB Output is correct
13 Correct 211 ms 14944 KB Output is correct
14 Correct 168 ms 14952 KB Output is correct
15 Correct 183 ms 13920 KB Output is correct
16 Correct 184 ms 13792 KB Output is correct
17 Correct 175 ms 15012 KB Output is correct
18 Correct 175 ms 13724 KB Output is correct
19 Correct 198 ms 14932 KB Output is correct
20 Correct 178 ms 14904 KB Output is correct
21 Correct 190 ms 14948 KB Output is correct
22 Correct 182 ms 14968 KB Output is correct
23 Correct 187 ms 13788 KB Output is correct
24 Correct 176 ms 13896 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -