oj.uz

Submission #1017881

# Submission time Handle Problem Language Result Execution time Memory
1017881 2024-07-09T10:59:20 Z andrei_iorgulescu Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 28300 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]];
}

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 4584 KB Output is correct
4 Correct 2 ms 4812 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4596 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4576 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 1 ms 2408 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4588 KB Output is correct
6 Correct 1 ms 4572 KB Output is correct
7 Correct 2 ms 4584 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 14 ms 5896 KB Output is correct
13 Correct 224 ms 28300 KB Output is correct
14 Correct 68 ms 7028 KB Output is correct
15 Correct 113 ms 18456 KB Output is correct
16 Correct 20 ms 6140 KB Output is correct
17 Correct 144 ms 28244 KB Output is correct
18 Correct 126 ms 28244 KB Output is correct
19 Correct 163 ms 27196 KB Output is correct
20 Correct 19 ms 6224 KB Output is correct
21 Correct 136 ms 28208 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.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 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4572 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4556 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 34 ms 4572 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4444 KB Output is correct
18 Correct 5 ms 4672 KB Output is correct
19 Correct 1 ms 4580 KB Output is correct
20 Correct 28 ms 4696 KB Output is correct
21 Correct 20 ms 4820 KB Output is correct
22 Correct 30 ms 4812 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 29 ms 4696 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2508 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 4 ms 4444 KB Output is correct
15 Correct 33 ms 4696 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 3 ms 4444 KB Output is correct
18 Correct 6 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 40 ms 4808 KB Output is correct
21 Correct 22 ms 4700 KB Output is correct
22 Correct 30 ms 4804 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 29 ms 676 KB Output is correct
25 Correct 14 ms 2908 KB Output is correct
26 Correct 407 ms 2812 KB Output is correct
27 Execution timed out 2027 ms 24656 KB Time limit exceeded
28 Halted 0 ms 0 KB -