Submission #1018039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018039		andrei_iorgulescu	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1584 ms	139980 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll inf = (ll)1e9 * (ll)1e9;
int tuf = (int)2e9 + 1;
const int NN = 6200000;

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

ll real_value[200005];
int m;

ll cate_r[200005],sum_r[200005],cate_l[200005],sum_l[200005];
map<int,int> huh;
vector<int> vvv;

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]];
    set<int> vls2;
    for (int i = 1; i <= n; i++)
        vls2.insert(real_value[s[i]] + real_value[t[i]]);
    itr = 0;
    for (auto it : vls2)
    {
        itr++;
        huh[it] = itr;
        vvv.push_back(it);
    }
}

int down_lpr(int x)
{
    if (x < vvv[0])
        return 0;
    int st = 0,pas = 1 << 16;
    while (pas != 0)
    {
        if (st + pas < vvv.size() and vvv[st + pas] <= x)
            st += pas;
        pas /= 2;
    }
    return st + 1;
}

int up_lpr(int x)
{
    if (x > vvv.back())
        return 0;
    int st = -1,pas = 1 << 16;
    while (pas != 0)
    {
        if (st + pas < vvv.size() and vvv[st + pas] < x)
            st += pas;
        pas /= 2;
    }
    return st + 2;
}

int y_opt[200005];

pair<int,ll> aint[NN + 5];
int fs[NN + 5],fd[NN + 5];
int roots1[200005],roots2[200005];
int cate;

pair<int,ll> query(int nod, int l, int r, int st, int dr)
{
    if (aint[nod].first == 0)
        return {0,0};
    if (r < st or dr < l)
        return {0,0};
    if (st <= l and r <= dr)
        return aint[nod];
    int mij = (ll)((ll)l + (ll)r) / 2;
    pair<int,ll> p1 = query(fs[nod],l,mij,st,dr),p2 = query(fd[nod],mij + 1,r,st,dr);
    return {p1.first + p2.first,p1.second + p2.second};
}

void update(int nod, int l, int r, int pos, int val)
{
    if (l == r)
    {
        aint[nod].first++;
        aint[nod].second += val;
    }
    else
    {
        int mij = (ll)((ll)l + (ll)r) / 2;
        if (pos <= mij)
        {
            cate++;
            aint[cate] = aint[fs[nod]];
            fs[cate] = fs[fs[nod]];
            fd[cate] = fd[fs[nod]];
            fs[nod] = cate;
            update(fs[nod],l,mij,pos,val);
        }
        else
        {
            cate++;
            aint[cate] = aint[fd[nod]];
            fs[cate] = fs[fd[nod]];
            fd[cate] = fd[fd[nod]];
            fd[nod] = cate;
            update(fd[nod],mij + 1,r,pos,val);
        }
        aint[nod] = {aint[fs[nod]].first + aint[fd[nod]].first,aint[fs[nod]].second + aint[fd[nod]].second};
    }
}

ll f(int x,int y)
{
    ll dev = 0;
    dev += real_value[x] * cate_r[x - 1] - sum_r[x - 1];
    dev += sum_l[y + 1] - real_value[y] * cate_l[y + 1];
    int cn = down_lpr(real_value[x] + real_value[y]);
    pair<int,ll> p1;
    if (cn == 0)
        p1 = {0,0};
    else
        p1 = query(roots1[x],1,n,1,cn);///.first = cate, .second = suma L-urilor reale
    cn = up_lpr(real_value[x] + real_value[y] + 1);
    pair<int,ll> p2;
    if (cn == 0)
        p2 = {0,0};
    else
        p2 = query(roots2[y],1,n,cn,n);///.first = cate, .second = suma R-urilor reale
    dev += p1.second - p1.first * real_value[x];
    dev += p2.first * real_value[y] - p2.second;
    dev *= 2;
    return dev;
}

void solve(int l, int r, int st, int dr)
{
    if (l > r)
        return;
    int mij = (l + r) / 2;
    ll bst = inf;
    for (int i = st; i <= dr; i++)
    {
        ll 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);
}

vector<pair<int,int>> cine_r[200005],cine_l[200005];

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();
    //for (int i = 1; i <= n; i++)
      //  cout << s[i] << ' ' << t[i] << endl;
    for (int i = 1; i <= n; i++)
    {
        cine_l[s[i]].push_back({s[i],t[i]});
        cine_r[t[i]].push_back({s[i],t[i]});
    }
    for (int i = 1; i <= n; i++)
    {
        cate_r[t[i]]++;
        sum_r[t[i]] += real_value[t[i]];
        cate_l[s[i]]++;
        sum_l[s[i]] += real_value[s[i]];
    }
    for (int i = 1; i <= m; i++)
    {
        cate_r[i] += cate_r[i - 1];
        sum_r[i] += sum_r[i - 1];
    }
    for (int i = m; i >= 1; i--)
    {
        cate_l[i] += cate_l[i + 1];
        sum_l[i] += sum_l[i + 1];
    }
    if (k == 1)
    {
        ll devmin = inf;
        for (int i = 1; i <= m; i++)
        {
            ll cr = cate_r[i - 1],sr = sum_r[i - 1],cl = cate_l[i + 1],sl = sum_l[i + 1];
            //cout << cr << ' ' << sr << ' ' << cl << ' ' << sl << endl;
            ll x = real_value[i];
            ll dev = 2 * (x * cr - sr + sl - x * cl);
            devmin = min(devmin,dev);
        }
        cout << ans + devmin;
    }
    else
    {
        cate = 2 * m;
        for (int i = 1; i <= m; i++)
            roots1[i] = i;
        for (int i = 1; i <= m; i++)
            roots2[i] = i + m;
        for (int x = m; x >= 1; x--)
        {
            aint[x] = aint[x + 1];
            fs[x] = fs[x + 1];
            fd[x] = fd[x + 1];
            for (auto interval : cine_l[x + 1])
                update(x,1,n,huh[real_value[interval.first] + real_value[interval.second]],real_value[interval.first]);
        }
        for (int y = m + 1; y <= 2 * m; y++)
        {
            if (y != m + 1)
            {
                aint[y] = aint[y - 1];
                fs[y] = fs[y - 1];
                fd[y] = fd[y - 1];
            }
            for (auto interval : cine_r[y - m - 1])
                update(y,1,n,huh[real_value[interval.first] + real_value[interval.second]],real_value[interval.second]);
        }
        solve(1,m,1,m);
        ll devmin = inf;
        for (int i = 1; i <= m; i++)
            devmin = min(devmin,f(i,y_opt[i]));
        cout << ans + devmin;
    }
    return 0;
}

/*
2 5
A 0 B 2
A 6 B 8
A 11 B 13
A 9 B 15
A 13 B 19
*/

/**
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 = r[x] + r[y] (omit / 2 ca nu conteaza) si m = r[L] + r[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)
Pai nu am update-uri sau ceva, deci pot sa ma uit asa:
- pentru alea cu R < x, doar imi tin ceva cate_r[x] si sum_r[x] (cate r < x si suma valorilor lor reale)
- pentru alea cu L > y, ceva analog pe sufixe
- pentru cate L > x si m <= mij, dat fiind ca nu am update-uri pot sa ma uit in versiunea x si sa intreb chestii pe m <= mij
Adica sa imi tin un aint persistent in care merg cu x de la m la 1 si imi tin pentru fiecare, structura pe alea cu L mai mare
-pentru R < y, m > mij, tot asa, un aint persistent de merg cu y de la 1 la m si tin strucura pe m cu alea cu R < y

Astfel, am o precalculare O(NlogN) timp si memorie si O(logN) timp pe query, deci Nlog^2 total

Hai ca mai stie cineva sa implementeze aint persistent
**/

Compilation message (stderr)

bridge.cpp: In function 'int down_lpr(int)':
bridge.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if (st + pas < vvv.size() and vvv[st + pas] <= x)
      |             ~~~~~~~~~^~~~~~~~~~~~
bridge.cpp: In function 'int up_lpr(int)':
bridge.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if (st + pas < vvv.size() and vvv[st + pas] < x)
      |             ~~~~~~~~~^~~~~~~~~~~~

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