oj.uz

Submission #585743

# Submission time Handle Problem Language Result Execution time Memory
585743 2022-06-29T09:43:30 Z Huy Palembang Bridges (APIO15_bridge) C++17
100 / 100
 554 ms 25652 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,ll>
//#define fi first
//#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)1e6 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int k,n;
char P[maxN],Q[maxN];
int S[maxN],T[maxN];
vector<pii> vc;
int dak = 0;
int su = 0;
vector<int> save;
map<int,int> n_val;
vector<int> oval;
int var;

bool FA(pii a,pii b)
{
    return a.first + a.second < b.first + b.second;
}

int idbit[2][maxN];
ll sumbit[2][maxN];

void Updateid(int t,int idx,int val)
{
    while(idx <= 2 * n)
    {
        idbit[t][idx] += val;
        idx += (idx & (-idx));
    }
}

int Getid(int t,int idx)
{
    int res = 0;
    while(idx > 0)
    {
        res += idbit[t][idx];
        idx -= (idx & (-idx));
    }
    return res;
}
void Updatesum(int t,int idx,int val)
{
    while(idx <= 2 * n)
    {
        sumbit[t][idx] += val;
        idx += (idx & (-idx));
    }
}

int Getsum(int t,int idx)
{
    int res = 0;
    while(idx > 0)
    {
        res += sumbit[t][idx];
        idx -= (idx & (-idx));
    }
    return res;
}

void Read()
{
    cin >> k >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> P[i] >> S[i] >> Q[i] >> T[i];
        if(P[i] != Q[i])
        {
            if(S[i] > T[i])
                swap(S[i],T[i]);
            vc.push_back({S[i],T[i]});
            dak++;
        }
        else
        {
            su += abs(S[i]-T[i]);
        }
    }
}

void Renumb()
{
    sort(save.begin(),save.end());
    int old = -1;
    int now = 0;
    oval.push_back(-1);
    for(int i : save)
    {
        if(i > old)
        {
            old = i;
            now++;
            oval.push_back(i);
        }
        n_val[old] = now;
    }
    var = now;
}

void Solve()
{
    if(vc.empty())
    {
        cout << su;
        return;
    }
    sort(vc.begin(),vc.end(),FA);
    for(pii tmp : vc)
    {
        save.push_back(tmp.first);
        save.push_back(tmp.second);
    }
    Renumb();
    for(pii tmp : vc)
    {
        Updateid(1,n_val[tmp.first],1);
        Updateid(1,n_val[tmp.second],1);
        Updatesum(1,n_val[tmp.first],tmp.first);
        Updatesum(1,n_val[tmp.second],tmp.second);
    }

    ll res = infty;

    int low = 1;
    int high = var;
    ll  check = 0;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(Getid(1,mid) > (int)vc.size())
            high = mid - 1;
        else
            low = mid + 1;
    }
    check += oval[low] * Getid(1,low) - Getsum(1,low);
    check += (Getsum(1,2*n) - Getsum(1,low)) - oval[low] * (Getid(1,2*n)-Getid(1,low));
    res = min(res,check);

    if(k == 1) {cout << res + su + dak;return;}

    for(int i = 0; i < vc.size(); i++)
    {
        Updateid(1,n_val[vc[i].first],-1);
        Updateid(0,n_val[vc[i].first],1);
        Updateid(1,n_val[vc[i].second],-1);
        Updateid(0,n_val[vc[i].second],1);

        Updatesum(1,n_val[vc[i].first],-vc[i].first);
        Updatesum(0,n_val[vc[i].first],vc[i].first);
        Updatesum(1,n_val[vc[i].second],-vc[i].second);
        Updatesum(0,n_val[vc[i].second],vc[i].second);

        ll check = 0;

        /// med part1
        int low = 1;
        int high = var;
        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(Getid(0,mid) > i + 1)
                high = mid - 1;
            else
                low = mid + 1;
        }
        check += oval[low] * Getid(0,low) - Getsum(0,low);
        check += (Getsum(0,2*n) - Getsum(0,low)) - oval[low] * (Getid(0,2*n)-Getid(0,low));

        /// med part 2
        if(i != vc.size() - 1)
        {
            low = 1;
            high = var;
            while(low <= high)
            {
                int mid = (low + high) / 2;
                if(Getid(1,mid) > (int)vc.size()-1-i)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            check += oval[low] * Getid(1,low) - Getsum(1,low);
            check += (Getsum(1,2*n) - Getsum(1,low)) - oval[low] * (Getid(1,2*n)-Getid(1,low));
        }
        res  = min(res,check);
    }
    cout << res + su + dak;
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message

bridge.cpp: In function 'void Solve()':
bridge.cpp:173:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for(int i = 0; i < vc.size(); i++)
      |                    ~~^~~~~~~~~~~
bridge.cpp:202:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         if(i != vc.size() - 1)
      |            ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 40 ms 7492 KB Output is correct
13 Correct 224 ms 24692 KB Output is correct
14 Correct 94 ms 7620 KB Output is correct
15 Correct 131 ms 14704 KB Output is correct
16 Correct 50 ms 8384 KB Output is correct
17 Correct 112 ms 24708 KB Output is correct
18 Correct 119 ms 24388 KB Output is correct
19 Correct 133 ms 23556 KB Output is correct
20 Correct 51 ms 8648 KB Output is correct
21 Correct 115 ms 24512 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 396 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 584 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 596 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 596 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 596 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 67 ms 6720 KB Output is correct
26 Correct 110 ms 6732 KB Output is correct
27 Correct 452 ms 23736 KB Output is correct
28 Correct 554 ms 25628 KB Output is correct
29 Correct 497 ms 25632 KB Output is correct
30 Correct 231 ms 13712 KB Output is correct
31 Correct 71 ms 6692 KB Output is correct
32 Correct 240 ms 25628 KB Output is correct
33 Correct 258 ms 25504 KB Output is correct
34 Correct 253 ms 24640 KB Output is correct
35 Correct 76 ms 6640 KB Output is correct
36 Correct 263 ms 25652 KB Output is correct
37 Correct 62 ms 6732 KB Output is correct