oj.uz

Submission #292095

# Submission time Handle Problem Language Result Execution time Memory
292095 2020-09-06T10:29:00 Z SamAnd Meetings (IOI18_meetings) C++17
36 / 100
 1119 ms 13320 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, qq;

vector<ll> solv2(vector<int> H, vector<int> L, vector<int> R)
{
    vector<ll> v;
    for (int ii = 0; ii < qq; ++ii)
    {
        int l = L[ii];
        int r = R[ii];

        vector<ll> ans(n);
        for (int i = l; i <= r; ++i)
            ans[i] = 0;

        stack<pair<int, int> > s;
        ll yans = 0;
        for (int i = l; i <= r; ++i)
        {
            int q = 1;
            while (!s.empty() && H[i] >= s.top().fi)
            {
                yans -= s.top().fi * 1LL * s.top().se;
                q += s.top().se;
                s.pop();
            }
            s.push(m_p(H[i], q));
            yans += s.top().fi * 1LL * s.top().se;
            ans[i] += yans;
        }

        while (!s.empty())
            s.pop();
        yans = 0;
        for (int i = r; i >= l; --i)
        {
            int q = 1;
            while (!s.empty() && H[i] >= s.top().fi)
            {
                yans -= s.top().fi * 1LL * s.top().se;
                q += s.top().se;
                s.pop();
            }
            s.push(m_p(H[i], q));
            yans += s.top().fi * 1LL * s.top().se;
            ans[i] += yans - H[i];
        }

        yans = ans[l];
        for (int i = l; i <= r; ++i)
            yans = min(yans, ans[i]);
        v.push_back(yans);
    }
    return v;
}

struct ban
{
    int l, r, ans;
    int q;
    ban()
    {
        ans = l = r = 0;
        q = 0;
    }
    ban(int x)
    {
        if (x == 1)
        {
            ans = l = r = 1;
        }
        else
        {
            ans = l = r = 0;
        }
        q = 1;
    }
};

ban t[N * 4];

ban mer(const ban& l, const ban& r)
{
    ban res;
    if (l.q == l.l)
        res.l = l.q + r.l;
    else
        res.l = l.l;
    if (r.q == r.r)
        res.r = r.q + l.r;
    else
        res.r = r.r;
    res.ans = max(l.ans, r.ans);
    res.ans = max(res.ans, l.r + r.l);
    res.q = l.q + r.q;
    return res;
}

void bil(const vector<int>& H, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(H[tl]);
        return;
    }
    int m = (tl + tr) / 2;
    bil(H, tl, m, pos * 2);
    bil(H, m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

ban qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return ban();
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return mer(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

vector<ll> solv3(vector<int> H, vector<int> L, vector<int> R)
{
    bil(H, 0, n - 1, 1);
    vector<ll> v;
    for (int ii = 0; ii < qq; ++ii)
    {
        int l = L[ii];
        int r = R[ii];
        ban u = qry(0, n - 1, l, r, 1);
        v.push_back(u.ans + (r - l + 1 - u.ans) * 2);
    }
    return v;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R)
{
    n = sz(H);
    qq = sz(L);
    if (n <= 5000 && qq <= 5000)
        return solv2(H, L, R);
    return solv3(H, L, R);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6656 KB Output is correct
3 Correct 6 ms 6656 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct
6 Correct 6 ms 6656 KB Output is correct
7 Correct 5 ms 6656 KB Output is correct
8 Correct 5 ms 6656 KB Output is correct
9 Correct 6 ms 6656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6656 KB Output is correct
3 Correct 6 ms 6656 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct
6 Correct 6 ms 6656 KB Output is correct
7 Correct 5 ms 6656 KB Output is correct
8 Correct 5 ms 6656 KB Output is correct
9 Correct 6 ms 6656 KB Output is correct
10 Correct 385 ms 6904 KB Output is correct
11 Correct 1119 ms 6996 KB Output is correct
12 Correct 384 ms 6904 KB Output is correct
13 Correct 1113 ms 6904 KB Output is correct
14 Correct 321 ms 6904 KB Output is correct
15 Correct 335 ms 6904 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 50 ms 8456 KB Output is correct
3 Correct 143 ms 11260 KB Output is correct
4 Correct 150 ms 13300 KB Output is correct
5 Correct 111 ms 13296 KB Output is correct
6 Correct 132 ms 13296 KB Output is correct
7 Correct 148 ms 13296 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 50 ms 8456 KB Output is correct
3 Correct 143 ms 11260 KB Output is correct
4 Correct 150 ms 13300 KB Output is correct
5 Correct 111 ms 13296 KB Output is correct
6 Correct 132 ms 13296 KB Output is correct
7 Correct 148 ms 13296 KB Output is correct
8 Incorrect 145 ms 13320 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6656 KB Output is correct
3 Correct 6 ms 6656 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct
6 Correct 6 ms 6656 KB Output is correct
7 Correct 5 ms 6656 KB Output is correct
8 Correct 5 ms 6656 KB Output is correct
9 Correct 6 ms 6656 KB Output is correct
10 Correct 385 ms 6904 KB Output is correct
11 Correct 1119 ms 6996 KB Output is correct
12 Correct 384 ms 6904 KB Output is correct
13 Correct 1113 ms 6904 KB Output is correct
14 Correct 321 ms 6904 KB Output is correct
15 Correct 335 ms 6904 KB Output is correct
16 Correct 4 ms 6528 KB Output is correct
17 Correct 50 ms 8456 KB Output is correct
18 Correct 143 ms 11260 KB Output is correct
19 Correct 150 ms 13300 KB Output is correct
20 Correct 111 ms 13296 KB Output is correct
21 Correct 132 ms 13296 KB Output is correct
22 Correct 148 ms 13296 KB Output is correct
23 Incorrect 145 ms 13320 KB Output isn't correct
24 Halted 0 ms 0 KB -