oj.uz

Submission #621458

# Submission time Handle Problem Language Result Execution time Memory
621458 2022-08-03T20:23:54 Z arayi Palembang Bridges (APIO15_bridge) C++17
100 / 100
 649 ms 24312 KB 
// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};

const int N = 1e6 + 20;
const lli mod = 998244353;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 128;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1)
            ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream &operator<<(ostream &c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
template <class T>
void maxi(T &a, T b)
{
    a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
    a = min(a, b);
}

int n, k;
lli ans;
vector<pair<int, pir>> fp;
lli pr[N], sf[N];
lli t[N];
void upd(int q, lli v, int nl = 0, int nr = 2 * n, int nd = 1)
{
    if (q > nr || q < nl)
        return;
    if (nl == nr)
    {
        t[nd] += v;
        return;
    }
    int md = (nl + nr) / 2;
    upd(q, v, nl, md, nd * 2);
    upd(q, v, md + 1, nr, nd * 2 + 1);
    t[nd] = t[nd * 2] + t[nd * 2 + 1];
}
lli qry(int l, int r, int nl = 0, int nr = 2 * n, int nd = 1)
{
    if (l > nr || r < nl)
        return 0;
    if (l == nl && r == nr)
        return t[nd];
    int md = (nl + nr) / 2;
    return qry(l, min(md, r), nl, md, nd * 2) + qry(max(md + 1, l), r, md + 1, nr, nd * 2 + 1);
}
int main()
{
    fastio;
    cin >> k >> n;
    vector<pir> s;
    for (int i = 0; i < n; i++)
    {
        int l, r;
        char A, B;
        cin >> A >> l >> B >> r;
        if (l > r)
            swap(l, r);
        if (A == B)
            ans += r - l;
        else
        {
            ans++;
            fp.ad(MP(l + r, MP(l, i)));
            s.ad(MP(l, 2 * i));
            s.ad(MP(r, 2 * i + 1));
        }
    }
    sort(all(s));
    sort(all(fp));
    multiset<int> a, b;
    for (int i = 0; i < (int)fp.size(); i++)
    {
        int l = fp[i].sc.fr, r = fp[i].fr - fp[i].sc.fr;
        int l1 = upper_bound(all(s), MP(l, 2 * fp[i].sc.sc)) - s.begin() - 1;
        int r1 = upper_bound(all(s), MP(r, 2 * fp[i].sc.sc + 1)) - s.begin() - 1;
        // cout << l << " " << r << "-";
        upd(l1, l), upd(r1, r);
        if (i == 0)
            a.insert(l1), b.insert(r1);
        else
        {
            if (r1 < *b.begin())
                a.insert(r1);
            else
                b.insert(r1);
            if (l1 < *b.begin())
                a.insert(l1);
            else
                b.insert(l1);
        }
        if (a.size() < b.size())
        {
            a.insert(*b.begin());
            b.erase(b.begin());
        }
        else if (a.size() > b.size())
        {
            b.insert(*(--a.end()));
            a.erase(--a.end());
        }
        int i1 = *b.begin();
        // cout << i1 << "-";
        pr[i] = qry(i1, 2 * n) - qry(0, i1 - 1);
        // cout << pr[i] << endl;
    }
    memset(t, 0, sizeof(t));
    a.clear(), b.clear();
    for (int i = (int)fp.size() - 1; i >= 0; i--)
    {
        int l = fp[i].sc.fr, r = fp[i].fr - fp[i].sc.fr;
        int l1 = upper_bound(all(s), MP(l, 2 * fp[i].sc.sc)) - s.begin() - 1;
        int r1 = upper_bound(all(s), MP(r, 2 * fp[i].sc.sc + 1)) - s.begin() - 1;
        // cout << l << " " << r << "-";
        upd(l1, l), upd(r1, r);
        if (i == 0)
            a.insert(l1), b.insert(r1);
        else
        {
            if (r1 < *b.begin())
                a.insert(r1);
            else
                b.insert(r1);
            if (l1 < *b.begin())
                a.insert(l1);
            else
                b.insert(l1);
        }
        if (a.size() < b.size())
        {
            a.insert(*b.begin());
            b.erase(b.begin());
        }
        else if (a.size() > b.size())
        {
            b.insert(*(--a.end()));
            a.erase(--a.end());
        }
        int i1 = *b.begin();
        // cout << i1 << "-";
        sf[i] = qry(i1, 2 * n) - qry(0, i1 - 1);
    }
    lli sm = pr[(int)fp.size() - 1];
    if (k == 2)
    {
        for (int i = 0; i < (int)fp.size() - 1; i++)
            mini(sm, pr[i] + sf[i + 1]);
    }
    ans += sm;
    cout << ans << endl;
    return 0;
}

/*
    __
  *(><)*
    \/ /
    ||/
  --||
    ||
    /\
   /  \
  /    \

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 5 ms 8144 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 8 ms 8276 KB Output is correct
5 Correct 8 ms 8276 KB Output is correct
6 Correct 7 ms 8276 KB Output is correct
7 Correct 6 ms 8276 KB Output is correct
8 Correct 6 ms 8336 KB Output is correct
9 Correct 6 ms 8276 KB Output is correct
10 Correct 8 ms 8332 KB Output is correct
11 Correct 7 ms 8284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 8 ms 8220 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 7 ms 8280 KB Output is correct
7 Correct 5 ms 8276 KB Output is correct
8 Correct 5 ms 8316 KB Output is correct
9 Correct 8 ms 8288 KB Output is correct
10 Correct 7 ms 8296 KB Output is correct
11 Correct 6 ms 8284 KB Output is correct
12 Correct 320 ms 22540 KB Output is correct
13 Correct 583 ms 24240 KB Output is correct
14 Correct 540 ms 21592 KB Output is correct
15 Correct 322 ms 17544 KB Output is correct
16 Correct 305 ms 23556 KB Output is correct
17 Correct 388 ms 24312 KB Output is correct
18 Correct 293 ms 23720 KB Output is correct
19 Correct 313 ms 24156 KB Output is correct
20 Correct 314 ms 23744 KB Output is correct
21 Correct 327 ms 23888 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8124 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8152 KB Output is correct
4 Correct 5 ms 8144 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8144 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 5 ms 8276 KB Output is correct
14 Correct 7 ms 8300 KB Output is correct
15 Correct 6 ms 8276 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 5 ms 8148 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 7 ms 8276 KB Output is correct
20 Correct 6 ms 8276 KB Output is correct
21 Correct 7 ms 8284 KB Output is correct
22 Correct 7 ms 8340 KB Output is correct
23 Correct 7 ms 8268 KB Output is correct
24 Correct 6 ms 8280 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 5 ms 8104 KB Output is correct
7 Correct 5 ms 8144 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 7 ms 8060 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 3 ms 8148 KB Output is correct
13 Correct 6 ms 8276 KB Output is correct
14 Correct 5 ms 8280 KB Output is correct
15 Correct 6 ms 8276 KB Output is correct
16 Correct 5 ms 8148 KB Output is correct
17 Correct 7 ms 8148 KB Output is correct
18 Correct 6 ms 8148 KB Output is correct
19 Correct 7 ms 8284 KB Output is correct
20 Correct 8 ms 8276 KB Output is correct
21 Correct 6 ms 8276 KB Output is correct
22 Correct 7 ms 8328 KB Output is correct
23 Correct 6 ms 8288 KB Output is correct
24 Correct 5 ms 8276 KB Output is correct
25 Correct 338 ms 22624 KB Output is correct
26 Correct 538 ms 22760 KB Output is correct
27 Correct 625 ms 23544 KB Output is correct
28 Correct 608 ms 24272 KB Output is correct
29 Correct 649 ms 24180 KB Output is correct
30 Correct 269 ms 16580 KB Output is correct
31 Correct 310 ms 23432 KB Output is correct
32 Correct 338 ms 24092 KB Output is correct
33 Correct 274 ms 23744 KB Output is correct
34 Correct 393 ms 24144 KB Output is correct
35 Correct 328 ms 23728 KB Output is correct
36 Correct 373 ms 23940 KB Output is correct
37 Correct 339 ms 22624 KB Output is correct