oj.uz

Submission #579043

# Submission time Handle Problem Language Result Execution time Memory
579043 2022-06-18T10:30:25 Z mousebeaver Two Antennas (JOI19_antennas) C++14
22 / 100
 233 ms 14856 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++;
        }
        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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 14256 KB Output is correct
2 Correct 217 ms 14604 KB Output is correct
3 Correct 141 ms 12628 KB Output is correct
4 Correct 205 ms 14664 KB Output is correct
5 Correct 86 ms 7392 KB Output is correct
6 Correct 222 ms 14724 KB Output is correct
7 Correct 168 ms 13124 KB Output is correct
8 Correct 220 ms 14668 KB Output is correct
9 Correct 33 ms 2232 KB Output is correct
10 Correct 217 ms 14656 KB Output is correct
11 Correct 115 ms 7960 KB Output is correct
12 Correct 233 ms 14576 KB Output is correct
13 Correct 155 ms 14676 KB Output is correct
14 Correct 148 ms 14624 KB Output is correct
15 Correct 158 ms 13624 KB Output is correct
16 Correct 163 ms 13624 KB Output is correct
17 Correct 161 ms 14856 KB Output is correct
18 Correct 157 ms 13520 KB Output is correct
19 Correct 165 ms 14688 KB Output is correct
20 Correct 152 ms 14676 KB Output is correct
21 Correct 157 ms 14704 KB Output is correct
22 Correct 154 ms 14604 KB Output is correct
23 Correct 161 ms 13712 KB Output is correct
24 Correct 144 ms 13532 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -