oj.uz

Submission #585620

# Submission time Handle Problem Language Result Execution time Memory
585620 2022-06-29T06:29:25 Z tamthegod Palembang Bridges (APIO15_bridge) C++14
100 / 100
 854 ms 65024 KB 
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int k, n;
int res = 0;
int m = 0;
vector<int> vc;
map<int, int> mp;
int c = 0;
struct TCitizen
{
    char p;
    int s;
    char q;
    int t;
} a[maxN];
map<int, int> nerf, origin;
void ReadInput()
{
    cin >> k >> n;
    int cnt = 0, cnt1 = 0;
    for(int i=1; i<=n; i++)
    {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
       // if(s == t) c++;
        vc.pb((s + t) / 2);
        if(p == q)
        {
            res += abs(s - t);
            continue;
        }
        if(s == 0) cnt++;
        else cnt1++;
        vc.pb(s);
        vc.pb(t);
        if(s > t)
            swap(s, t);
        a[++m] = {p, s, q, t};
    }
    vector<int> vc;
    for(int i=1; i<=m; i++)
    {
        vc.pb(a[i].s);
        vc.pb(a[i].t);
        vc.pb((a[i].s + a[i].t) / 2);
    }
    sort(vc.begin(), vc.end());
    int p = 0;
    for(int v : vc)
    {
        if(nerf[v]) continue;
        nerf[v] = ++p;
        origin[p] = v;
    }
 //   cout << cnt << " " << cnt1;exit(0);
  //  cout << c;exit(0);
}
struct BIT
{
    int n;
    vector<int> bit;
    BIT(int _n)
    {
        n = _n * 3;
        bit.resize(n + 1);
    }
    void reset()
    {
        for(int i=1; i<=n; i++) bit[i] = 0;
    }
    void update(int pos, int val)
    {
        for(; pos <= n; pos += (pos & (-pos)))
            bit[pos] += val;
    }
    int get(int pos)
    {
        int res = 0;
        for(; pos; pos -= (pos & (-pos)))
            res += bit[pos];
        return res;
    }
};
pair<int, int> bit[maxN];
void update(int pos, int val)
{
    while(pos <= n * 3)
    {
        bit[pos].fi += val;
        bit[pos].se++;
        pos += (pos & (-pos));
    }
}
pair<int, int> get(int pos)
{
    pair<int, int> res;
    while(pos)
    {
        res.fi += bit[pos].fi;
        res.se += bit[pos].se;
        pos -= (pos & (-pos));
    }
    return res;
}
pair<int, int> get_range(int l, int r)
{
    pair<int, int> val1 = get(r), val2 = get(l - 1);
    return {val1.fi - val2.fi, val1.se - val2.se};
}
void sub1()
{
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.s < q.s;
    });
    int p = 1;
    int sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].s <= x)
        {
            sum += a[p].s;
            p++;
        }
        mp[x] += x * (p - 1) - sum;
    }
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.t < q.t;
    });
    p = 1;
    sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].t <= x)
        {
            sum += a[p].t;
            p++;
        }
        mp[x] += x * (p - 1) - sum;
    }
    reverse(vc.begin(), vc.end());
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.s > q.s;
    });
    p = 1;
    sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].s >= x)
        {
            sum += a[p].s;
            p++;
        }
        mp[x] += -(x * (p - 1) - sum);
    }
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.t > q.t;
    });
    p = 1;
    sum = 0;
    for(int x : vc)
    {
        while(p <= m && a[p].t >= x)
        {
            sum += a[p].t;
            p++;
        }
        mp[x] += -(x * (p - 1) - sum);
    }
    int _min = oo;
    for(pair<int, int> v : mp)
        _min = min(_min, v.se);
    _min += m;
    cout << res + _min;
}
pair<int, int> ans[maxN];
void sub2()
{
    BIT bit1(n);
    sort(a + 1, a + m + 1, [](TCitizen p, TCitizen q)
    {
        return p.s + p.t < q.s + q.t;
    });
    for(int i=1; i<=m; i++)
    {
        bit1.update(nerf[a[i].s], 1);
        bit1.update(nerf[a[i].t], 1);
        int low = 1, high = n * 3, mid;
        while(low <= high)
        {
            mid = (low + high) / 2;
            int val = bit1.get(mid);
            if(val >= i) high = mid - 1;
            else low = mid + 1;
        }
        update(nerf[a[i].s], a[i].s);
        update(nerf[a[i].t], a[i].t);
        //cout << get_range(3, 3).fi;return;
        pair<int, int> val1 = get_range(1, low);
        ans[i].fi += origin[low] * val1.se - val1.fi;
        pair<int, int> val2 = get_range(low, n * 3);
        ans[i].fi += val2.fi - origin[low] * val2.se;
       // cout << origin[mid] << '\n';
      //  cout << ans[i].fi << " ";
    }
  //  return;
  //  return;
    memset(bit, 0, sizeof bit);
    bit1.reset();
    for(int i=m; i>=1; i--)
    {
        bit1.update(nerf[a[i].s], 1);
        bit1.update(nerf[a[i].t], 1);
        int low = 1, high = n * 3, mid;
     //   cout << bit1.get(15);return;
        while(low <= high)
        {
            mid = (low + high) / 2;
            int val = bit1.get(mid);
            if(val >= (m - i + 1)) high = mid - 1;
            else low = mid + 1;
        }
        update(nerf[a[i].s], a[i].s);
        update(nerf[a[i].t], a[i].t);
        pair<int, int> val1 = get_range(1, low);
        ans[i].se += origin[low] * val1.se - val1.fi;
        pair<int, int> val2 = get_range(low, n * 3);
        ans[i].se += val2.fi - origin[low] * val2.se;
       // cout << ans[i].se << " ";
    }
    assert(m);
   // return;
    int _min = oo;
    for(int i=0; i<=m; i++)
    {
        _min = min(_min, ans[i].fi + ans[i + 1].se);
    }
    cout << res + m + _min;
}
void Solve()
{
    //cout << res;return;
    if(!m)
    {
        cout << res;
        return;
    }
    if(k == 1)
    {
        sub1();
    }
    else
        sub2();

}
int32_t main()
{
    //freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message

bridge.cpp: In function 'void sub2()':
bridge.cpp:226:30: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
  226 |     memset(bit, 0, sizeof bit);
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from bridge.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 38 ms 11976 KB Output is correct
13 Correct 514 ms 62164 KB Output is correct
14 Correct 103 ms 11336 KB Output is correct
15 Correct 257 ms 36680 KB Output is correct
16 Correct 43 ms 11968 KB Output is correct
17 Correct 431 ms 62128 KB Output is correct
18 Correct 284 ms 43420 KB Output is correct
19 Correct 404 ms 56968 KB Output is correct
20 Correct 49 ms 11976 KB Output is correct
21 Correct 292 ms 43292 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 7 ms 15960 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15976 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15968 KB Output is correct
9 Correct 8 ms 15960 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 16084 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 15924 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 16032 KB Output is correct
6 Correct 8 ms 15888 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 7 ms 15944 KB Output is correct
10 Correct 7 ms 15960 KB Output is correct
11 Correct 8 ms 16012 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 7 ms 16096 KB Output is correct
14 Correct 8 ms 16096 KB Output is correct
15 Correct 11 ms 16412 KB Output is correct
16 Correct 7 ms 15960 KB Output is correct
17 Correct 7 ms 16084 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 8 ms 16084 KB Output is correct
20 Correct 9 ms 16468 KB Output is correct
21 Correct 9 ms 16340 KB Output is correct
22 Correct 9 ms 16404 KB Output is correct
23 Correct 7 ms 16084 KB Output is correct
24 Correct 9 ms 16288 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 9 ms 15960 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 7 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 9 ms 15956 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 8 ms 16084 KB Output is correct
14 Correct 7 ms 16132 KB Output is correct
15 Correct 10 ms 16496 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 7 ms 16084 KB Output is correct
20 Correct 10 ms 16484 KB Output is correct
21 Correct 9 ms 16360 KB Output is correct
22 Correct 10 ms 16468 KB Output is correct
23 Correct 8 ms 16152 KB Output is correct
24 Correct 9 ms 16340 KB Output is correct
25 Correct 91 ms 25988 KB Output is correct
26 Correct 115 ms 26272 KB Output is correct
27 Correct 799 ms 59252 KB Output is correct
28 Correct 824 ms 64812 KB Output is correct
29 Correct 854 ms 65024 KB Output is correct
30 Correct 368 ms 41980 KB Output is correct
31 Correct 96 ms 26668 KB Output is correct
32 Correct 440 ms 64888 KB Output is correct
33 Correct 351 ms 51932 KB Output is correct
34 Correct 455 ms 61344 KB Output is correct
35 Correct 107 ms 26820 KB Output is correct
36 Correct 369 ms 52136 KB Output is correct
37 Correct 91 ms 26116 KB Output is correct