Submission #1060215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060215		jerzyk	모임들 (IOI18_meetings)	C++14	36 / 100	2811 ms	18380 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
ll tab[N], l[N];
int drz[2 * N], lazy[2 * N];
pair<pair<int, int>, int> que[N];
ll answer[N];

void Add(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        ++drz[v]; ++lazy[v];
        return;
    }
    Add(v * 2, p, (p + k) / 2, pz, kz);
    Add(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    drz[v] = max(drz[v * 2], drz[v * 2 + 1]) + lazy[v];
}

int Query(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return 0;
    if(p >= pz && k <= kz)
        return drz[v];
    int ans;
    ans = Query(v * 2, p, (p + k) / 2, pz, kz);
    ans = max(ans, Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz));
    return ans + lazy[v];
}

void DoQ(int n, int q)
{
    int j = q + 1, l = n;
    sort(que + 1, que + 1 + q);
    for(int i = n; i >= 1; --i)
    {
        if(tab[i] == 2)
            l = i - 1;
        if(tab[i] == 1)
            Add(1, 0, N - 1, i, l);
        while(que[j - 1].st.st == i)
        {
            --j;
            int x = Query(1, 0, N - 1, que[j].st.st, que[j].st.nd), d = que[j].st.nd - que[j].st.st + 1;
            //cerr << l << " " << "query: " << i << " " << x << " " << d << "\n";
            answer[que[j].nd] = 2 * d - x;
        }
    }
}

ll Ans(int a, int b)
{
    ll ans = I;
    vector<pair<ll, int>> kol;
    kol.pb(make_pair(I, a - 1));
    ll s = 0LL;
    l[a - 1] = 0LL;
    for(int i = a; i <= b; ++i)
    {
        while(kol.back().st <= tab[i])
        {
            int r = (int)kol.size() - 1;
            s -= (ll)(kol[r].nd - kol[r - 1].nd) * kol[r].st;
            kol.pop_back();
        }
        s += (ll)(i - kol.back().nd) * tab[i];
        kol.pb(make_pair(tab[i], i));
        l[i] = s;
    }
    kol.clear();
    kol.pb(make_pair(I, b + 1));
    s = 0LL;
    for(int i = b; i >= a; --i)
    {
        while(kol.back().st <= tab[i])
        {
            int r = (int)kol.size() - 1;
            s -= (ll)(kol[r - 1].nd - kol[r].nd) * kol[r].st;
            kol.pop_back();
        }
        s += (ll)(kol.back().nd - i) * tab[i];
        ans = min(l[i] - tab[i] + s, ans);
        kol.pb(make_pair(tab[i], i));
    }
    return ans;
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) 
{
    vector<ll> ans;
    int n = H.size(), q = L.size();
    for(int i = 1; i <= n; ++i) tab[i] = H[i - 1];
    for(int i = 1; i <= q; ++i)
        que[i] = make_pair(make_pair(L[i - 1] + 1, R[i - 1] + 1), i);
    if(n > 50000)
    {
        DoQ(n, q);
        for(int i = 1; i <= q; ++i)
            ans.pb(answer[i]);
        return ans;
    }
    for(int i = 1; i <= q; ++i)
        ans.pb(Ans(que[i].st.st, que[i].st.nd));
    return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40