oj.uz

Submission #836277

# Submission time Handle Problem Language Result Execution time Memory
836277 2023-08-24T09:41:38 Z mousebeaver Meetings (IOI18_meetings) C++14
17 / 100
 86 ms 13520 KB 
#define ll long long
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

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

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

struct node
{
    ll bleft;
    ll bright;
    ll bmax;
    ll len;
};

node combine(node l, node r)
{
    node output = {0, 0, 0, 0};

    if(l.bleft == l.len)
    {
        output.bleft = l.bleft + r.bleft;
    }
    else
    {
        output.bleft = l.bleft;
    }

    if(r.bright == r.len)
    {
        output.bright = r.bright+l.bright;
    }
    else
    {
        output.bright = r.bright;
    }

    output.bmax = max(max(r.bmax, l.bmax), r.bleft + l.bright);
    output.len = l.len+r.len;
    return output;
}

node query(ll i, vector<node>& s, ll a, ll b, ll l, ll r)
{
    if(l <= a && b <= r)
    {
        return s[i];
    }
    if(r < a || b < l)
    {
        return {0, 0, 0, 0};
    }

    ll mid = (a+b)/2;
    return combine(query(left(i), s, a, mid, l, r), query(right(i), s, mid+1, b, l, r));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) 
{
    ll n = H.size();
    ll segnodes = 1;
    while(2*n > segnodes)
    {
        segnodes *= 2;
    }
    vector<node> s(segnodes, {0, 0, 0, 1});

    for(ll i = 0; i < n; i++)
    {
        if(H[i] == 1)
        {
            s[i+segnodes/2] = {1, 1, 1, 1};
        }
    }
    for(ll i = segnodes/2-1; i > 0; i--)
    {
        s[i] = combine(s[left(i)], s[right(i)]);
    }

    vector<ll> output(0);
    for(ll i = 0; i < (ll) L.size(); i++)
    {
        ll mountains = R[i]+1-L[i];
        output.push_back(2*mountains - query(1, s, 1, segnodes/2, L[i]+1, R[i]+1).bmax);
    }
    return output;
}

Subtask #1
0 / 4.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 / 15.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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 28 ms 2760 KB Output is correct
3 Correct 82 ms 12468 KB Output is correct
4 Correct 86 ms 13480 KB Output is correct
5 Correct 60 ms 13492 KB Output is correct
6 Correct 72 ms 13508 KB Output is correct
7 Correct 81 ms 13520 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 28 ms 2760 KB Output is correct
3 Correct 82 ms 12468 KB Output is correct
4 Correct 86 ms 13480 KB Output is correct
5 Correct 60 ms 13492 KB Output is correct
6 Correct 72 ms 13508 KB Output is correct
7 Correct 81 ms 13520 KB Output is correct
8 Incorrect 79 ms 13508 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

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