oj.uz

Submission #579031

# Submission time Handle Problem Language Result Execution time Memory
579031 2022-06-18T10:15:27 Z mousebeaver Two Antennas (JOI19_antennas) C++14
22 / 100
 302 ms 14712 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 < n && 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)
            {
                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

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1992 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1992 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 14316 KB Output is correct
2 Correct 281 ms 14660 KB Output is correct
3 Correct 171 ms 12560 KB Output is correct
4 Correct 232 ms 14576 KB Output is correct
5 Correct 102 ms 7396 KB Output is correct
6 Correct 278 ms 14564 KB Output is correct
7 Correct 201 ms 13136 KB Output is correct
8 Correct 249 ms 14584 KB Output is correct
9 Correct 38 ms 2260 KB Output is correct
10 Correct 302 ms 14664 KB Output is correct
11 Correct 135 ms 8000 KB Output is correct
12 Correct 239 ms 14564 KB Output is correct
13 Correct 226 ms 14704 KB Output is correct
14 Correct 173 ms 14684 KB Output is correct
15 Correct 181 ms 13568 KB Output is correct
16 Correct 207 ms 13544 KB Output is correct
17 Correct 178 ms 14648 KB Output is correct
18 Correct 185 ms 13544 KB Output is correct
19 Correct 173 ms 14712 KB Output is correct
20 Correct 176 ms 14608 KB Output is correct
21 Correct 258 ms 14704 KB Output is correct
22 Correct 183 ms 14688 KB Output is correct
23 Correct 178 ms 13616 KB Output is correct
24 Correct 231 ms 13536 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1992 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -