Submission #1017881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017881		andrei_iorgulescu	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2027 ms	28300 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

struct AIB
{
    vector<int> aib;
    int mar;

    AIB (int marime)
    {
        mar = marime;
        aib.resize(marime + 1);
    }

    void update(int pos,int val)
    {
        for (int i = pos; i <= mar; i += (i & -i))
            aib[i] += val;
    }

    int query(int pos)
    {
        int rr = 0;
        for (int i = pos; i > 0; i -= (i & -i))
            rr += aib[i];
        return rr;
    }
};

int n,k;
char p[100005],q[100005];
int s[100005],t[100005];
int ans;

int real_value[200005];
int m;

void normalize()
{
    set<int> vls;
    for (int i = 1; i <= n; i++)
    {
        vls.insert(s[i]);
        vls.insert(t[i]);
    }
    map<int,int> norma;
    int itr = 0;
    for (auto it : vls)
    {
        itr++;
        norma[it] = itr;
        real_value[itr] = it;
    }
    m = itr;
    for (int i = 1; i <= n; i++)
        s[i] = norma[s[i]],t[i] = norma[t[i]];
}

int y_opt[200005];

int f(int x,int y)
{
    int dev = 0;
    for (int i = 1; i <= n; i++)
    {
        if (t[i] < x)
            dev += 2 * (real_value[x] - real_value[t[i]]);
        else if (s[i] > y)
            dev += 2 * (real_value[s[i]] - real_value[y]);
        else if (s[i] > x and t[i] < y)
            dev += 2 * min(real_value[s[i]] - real_value[x],real_value[y] - real_value[t[i]]);
    }
    return dev;
}

void solve(int l, int r, int st, int dr)
{
    if (l > r)
        return;
    int mij = (l + r) / 2;
    int bst = inf;
    for (int i = st; i <= dr; i++)
    {
        int cat = f(mij,i);
        if (cat < bst)
        {
            bst = cat;
            y_opt[mij] = i;
        }
    }
    solve(l,mij - 1,st,y_opt[mij]);
    solve(mij + 1,r,y_opt[mij],dr);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> k >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i] >> s[i] >> q[i] >> t[i];
        if (s[i] > t[i])
            swap(s[i],t[i]);
        ans += t[i] - s[i];
        if (p[i] == q[i])
            n--,i--;
    }
    ans += n;
    if (n <= k)
    {
        cout << ans << '\n';
        return 0;
    }
    normalize();
    if (k == 1)
    {
        AIB aib_cnt_r(m), aib_sum_r(m), aib_cnt_l(m), aib_sum_l(m);
        for (int i = 1; i <= n; i++)
        {
            aib_cnt_r.update(t[i],1);
            aib_sum_r.update(t[i],real_value[t[i]]);
            aib_cnt_l.update(s[i],1);
            aib_sum_l.update(s[i],real_value[s[i]]);
        }
        int devmin = inf;
        for (int i = 1; i <= m; i++)
        {
            int cr = aib_cnt_r.query(i - 1),sr = aib_sum_r.query(i - 1),cl = aib_cnt_l.query(m) - aib_cnt_l.query(i),sl = aib_sum_l.query(m) - aib_sum_l.query(i);
            int x = real_value[i];
            int dev = 2 * (x * cr - sr + sl - x * cl);
            devmin = min(devmin,dev);
        }
        cout << ans + devmin;
    }
    else
    {
        solve(1,m,1,m);
        int devmin = inf;
        for (int i = 1; i <= m; i++)
            devmin = min(devmin,f(i,y_opt[i]));
        cout << ans + devmin;
    }
    return 0;
}

/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

/**
Obs: merita sa fac pod doar unde e cv cladire, adica in O(N) locatii
Initial adun abs(S[i] - T[i]) la toate, fac S[i] <= T[i], daca P[i] = Q[i] il elimin, altfel mai adaug 1 si presupun P[i] = A, Q[i] = B
N o sa fie cate intervale au P[i] != Q[i]
K = 1 -> fixez unde fac podul, vad cate au R in stanga si suma R-urilor, cate au L in dreapta si suma L-urilor, cv formula
K = 2

Fie x si y locatiile (dintre cele O(N)) in care imi fac podurile
Cred (doamne ajuta adica) ca daca imi fixez un x, y_opt(x) e crescator (divide dp stuff)
Hai sa zicem ca am eu o functie magica f(x,y) care imi calculeaza suma devierilor daca fac poduri in x si y
Pai f(x,y) functioneaza gen: ia toate alea cu R < x si zice cate si suma, toate cu L > y si zice cate si suma etc penal
Problema apare la alea x < L <= R < y ca am min(L - x, y - R)
Aici, zic asa: fie mij = x + y (omit / 2 ca nu conteaza) si m = L + R
Daca m <= mij, L - x e minim, altfel R - y e minim

Atunci f(x,y) zice: gaseste toti aia cu L > x si m <= mij si zi cati si suma L-urilor (oricum asta imi garanteaza y < R)
Apoi, gaseste toti aia cu R < y si m > mij si zi cati si suma R-urilor (once again, asta garanteaza L > x)

In functie de chestiile alea am o formula penala pentru f(x,y)
Daca ar intra aib-ul 2D (adica Nlog^3 complexitate) atunci doar pot face divide dp-ul simplu, aflu y_opt(x) si totul e bine
Schema e asa: Hai sa incerc, pentru toti y din [st, dr], sa gasesc f-ul mergand frumos prin ei
Prima parte e: cumva sa pun mana pe toti cu L > x, m <= mij
Hai sa imi tin in cv structura (peste care voi tine aib-urile) toti cu L > x
Pai, initial pun toti cu L > x (care inca nu au fost pusi) in structura
Calculez acum doar din aib-uri partea lor de f(x,y)
Pentru cei cu R < y, m > mij: Again, cum merg cu y crescator, bag in (alta) structura cei cu R == y - 1
Din structura aia dau query de suma si de cati pentru cei cu m > mij
Astfel, doar din operatii pe aib, am calculat y_opt(x)
Schema e asa: cand dau divide in bucata din stanga, trebuie sa am toti L > x_mij, pentru ca apoi sa pun doar cei care tin de x_left
Cand dau divide in bucata dreapta, trebuie sa am pusi in structura a doua pe toti cei cu y < y_opt(x_mij)

In felul asta, complexitatea ramane Nlog^2 (holy shit cum implementez eu toata asta)

Hai sa testez mai intai daca chiar merge divide dp-ul lol
**/

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37