oj.uz

Submission #579027

# Submission time Handle Problem Language Result Execution time Memory
579027 2022-06-18T10:09:52 Z mousebeaver Two Antennas (JOI19_antennas) C++14
22 / 100
 297 ms 14828 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 245 ms 14336 KB Output is correct
2 Correct 276 ms 14652 KB Output is correct
3 Correct 172 ms 12604 KB Output is correct
4 Correct 255 ms 14560 KB Output is correct
5 Correct 97 ms 7360 KB Output is correct
6 Correct 253 ms 14560 KB Output is correct
7 Correct 255 ms 13188 KB Output is correct
8 Correct 263 ms 14808 KB Output is correct
9 Correct 42 ms 2252 KB Output is correct
10 Correct 275 ms 14584 KB Output is correct
11 Correct 139 ms 8084 KB Output is correct
12 Correct 297 ms 14628 KB Output is correct
13 Correct 174 ms 14608 KB Output is correct
14 Correct 171 ms 14688 KB Output is correct
15 Correct 178 ms 13644 KB Output is correct
16 Correct 185 ms 13612 KB Output is correct
17 Correct 177 ms 14728 KB Output is correct
18 Correct 172 ms 13496 KB Output is correct
19 Correct 220 ms 14704 KB Output is correct
20 Correct 176 ms 14692 KB Output is correct
21 Correct 181 ms 14828 KB Output is correct
22 Correct 184 ms 14708 KB Output is correct
23 Correct 186 ms 13616 KB Output is correct
24 Correct 168 ms 13532 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 -