Submission #1105454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105454		jerzyk	Nile (IOI24_nile)	C++17	100 / 100	74 ms	11596 KiB

nile

#include <bits/stdc++.h>
#include "nile.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 int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<17;

int fau[N], mi[N][2], l[N], r[N];
int cst[N]; ll cans = 0LL;

pair<int, int> joi[N];
pair<int, int> upd[N];

pair<int, int> tab[N];

pair<int, int> que[N];
vector<ll> answer;

int Find(int v)
{
    if(fau[v] == v) return v;
    return (fau[v] = Find(fau[v]));
}

inline void Calc(int a)
{
    cst[a] = 0;
    if(l[a] % 2 == r[a] % 2)
        cst[a] += mi[a][l[a] % 2];
}

void Union(int a, int b)
{
    a = Find(a); b = Find(b);
    cans -= (ll)(cst[a] + cst[b]);
    fau[b] = a;
    mi[a][0] = min(mi[a][0], mi[b][0]);
    mi[a][1] = min(mi[a][1], mi[b][1]);
    r[a] = r[b];
    Calc(a);
    cans += (ll)cst[a];
}

void Upd(int v)
{
    int x = tab[v].nd;
    v = Find(v);
    mi[v][0] = min(mi[v][0], x);
    mi[v][1] = min(mi[v][1], x);

    cans -= (ll)cst[v];
    Calc(v);
    cans += (ll)cst[v];
}

void Ans(int n, int q)
{
    for(int i = 1; i <= n; ++i)
    {
        mi[i][0] = II; mi[i][1] = II;
        mi[i][i % 2] = tab[i].nd;
        l[i] = i; r[i] = i; fau[i] = i;
        Calc(i);
        cans += cst[i];

        if(i < n)
            joi[i] = make_pair(tab[i + 1].st - tab[i].st, i);
        if(i > 1 && i < n)
            upd[i - 1] = make_pair(tab[i + 1].st - tab[i - 1].st, i);
    }
    //cerr << "Init: " << cans << "\n";
    if(n > 1)
        sort(joi + 1, joi + 1 + (n - 1));
    if(n > 2)
        sort(upd + 1, upd + 1 + (n - 2));
    int j1 = 0, j2 = 0;
    for(int i = 1; i <= q; ++i)
    {
        while(j1 < n - 1 && joi[j1 + 1].st <= que[i].st)
        {
            ++j1;
            Union(joi[j1].nd, joi[j1].nd + 1);
        }
        while(j2 < n - 2 && upd[j2 + 1].st <= que[i].st)
        {
            ++j2;
            Upd(upd[j2].nd);
        }
        answer[que[i].nd] += cans;
    }
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int>E)
{
    int n = W.size(), q = E.size();
    ll bans = 0LL;
    for(int i = 1; i <= n; ++i)
    {
        tab[i] = make_pair(W[i - 1], (ll)(A[i - 1] - B[i - 1]));
        bans += B[i - 1];
    }
    for(int i = 0; i < q; ++i)
    {answer.pb(bans); que[i + 1] = make_pair(E[i], i);}
    sort(tab + 1, tab + 1 + n);
    sort(que + 1, que + 1 + q);
    Ans(n, q);

    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18