oj.uz

Submission #1017857

# Submission time Handle Problem Language Result Execution time Memory
1017857 2024-07-09T10:47:37 Z andrei_iorgulescu Palembang Bridges (APIO15_bridge) C++14
22 / 100
 197 ms 25684 KB 
#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]];
}

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;
    }
    return 0;
}

/*
1 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 12 ms 3432 KB Output is correct
13 Correct 197 ms 25552 KB Output is correct
14 Correct 49 ms 4432 KB Output is correct
15 Correct 92 ms 16164 KB Output is correct
16 Correct 14 ms 3416 KB Output is correct
17 Correct 118 ms 25684 KB Output is correct
18 Correct 106 ms 25680 KB Output is correct
19 Correct 151 ms 24404 KB Output is correct
20 Correct 17 ms 3420 KB Output is correct
21 Correct 116 ms 25488 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -