oj.uz

Submission #1018014

# Submission time Handle Problem Language Result Execution time Memory
1018014 2024-07-09T12:51:27 Z andrei_iorgulescu Palembang Bridges (APIO15_bridge) C++14
63 / 100
 2000 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;
int tuf = (int)2e9 + 1;
const int NN = 5e6;

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

int real_value[200005];
int m;

int cate_r[200005],sum_r[200005],cate_l[200005],sum_l[200005];

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];

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

pair<int,int> 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 = (l + r) / 2;
    pair<int,int> 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 = (l + 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};
    }
}

int f(int x,int y)
{
    int 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];
    pair<int,int> p1 = query(roots1[x],0,tuf,0,real_value[x] + real_value[y]);///.first = cate, .second = suma L-urilor reale
    pair<int,int> p2 = query(roots2[y],0,tuf,real_value[x] + real_value[y] + 1,tuf);///.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;
    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);
}

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)
    {
        int devmin = inf;
        for (int i = 1; i <= m; i++)
        {
            int 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;
            int x = real_value[i];
            int 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,0,tuf,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,0,tuf,real_value[interval.first] + real_value[interval.second],real_value[interval.second]);
        }
        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
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
**/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Correct 6 ms 10128 KB Output is correct
5 Correct 7 ms 10132 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 10076 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 5 ms 10076 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 10076 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9760 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 5 ms 10072 KB Output is correct
6 Correct 4 ms 9876 KB Output is correct
7 Correct 5 ms 10076 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 4 ms 10160 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 4 ms 10076 KB Output is correct
12 Correct 19 ms 16860 KB Output is correct
13 Correct 213 ms 42524 KB Output is correct
14 Correct 58 ms 17260 KB Output is correct
15 Correct 104 ms 29368 KB Output is correct
16 Correct 23 ms 15836 KB Output is correct
17 Correct 124 ms 42580 KB Output is correct
18 Correct 117 ms 42576 KB Output is correct
19 Correct 177 ms 41184 KB Output is correct
20 Correct 24 ms 16768 KB Output is correct
21 Correct 110 ms 42428 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 10076 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 4 ms 9856 KB Output is correct
8 Correct 5 ms 10072 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 4 ms 10076 KB Output is correct
11 Correct 4 ms 10020 KB Output is correct
12 Correct 5 ms 10076 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9956 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 5 ms 10136 KB Output is correct
10 Correct 4 ms 10328 KB Output is correct
11 Correct 4 ms 10076 KB Output is correct
12 Correct 5 ms 10076 KB Output is correct
13 Correct 5 ms 10412 KB Output is correct
14 Correct 7 ms 11864 KB Output is correct
15 Correct 12 ms 12364 KB Output is correct
16 Correct 5 ms 10076 KB Output is correct
17 Correct 5 ms 10844 KB Output is correct
18 Correct 7 ms 10844 KB Output is correct
19 Correct 4 ms 9872 KB Output is correct
20 Correct 13 ms 12380 KB Output is correct
21 Correct 8 ms 12124 KB Output is correct
22 Correct 11 ms 12120 KB Output is correct
23 Correct 5 ms 11096 KB Output is correct
24 Correct 11 ms 12380 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 10076 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 4 ms 10076 KB Output is correct
11 Correct 4 ms 10076 KB Output is correct
12 Correct 5 ms 10076 KB Output is correct
13 Correct 5 ms 10328 KB Output is correct
14 Correct 6 ms 11864 KB Output is correct
15 Correct 10 ms 12124 KB Output is correct
16 Correct 4 ms 10076 KB Output is correct
17 Correct 5 ms 10840 KB Output is correct
18 Correct 7 ms 10880 KB Output is correct
19 Correct 4 ms 9816 KB Output is correct
20 Correct 10 ms 12336 KB Output is correct
21 Correct 6 ms 12340 KB Output is correct
22 Correct 10 ms 12380 KB Output is correct
23 Correct 5 ms 11096 KB Output is correct
24 Correct 11 ms 12376 KB Output is correct
25 Correct 43 ms 64304 KB Output is correct
26 Execution timed out 2309 ms 262148 KB Time limit exceeded
27 Halted 0 ms 0 KB -