Submission #1148326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148326		sbendy	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	328 KiB

bridge

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef __int128 lll;
//typedef __float128 fl;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<lll> vlll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
const ll INF = LONG_LONG_MAX - 1;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const double PI = 3.14159265358979323846;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define print(a) cout << (a) << "\n";
#define printPair(a) cout << (a).first << " " << (a).second << "\n";

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )



//Mint fact[MAXN + 3];
//Mint inv[MAXN + 3];



double TOL = 1e-7;

void preload(){
    //  sieve(MAXN);
}


ll bS(const vector<ll>& b, const vector<ll>& psumEnd, ll x) {
    // Find the first index where b[i] >= x.
    int idx = lower_bound(b.begin(), b.end(), x) - b.begin();
    // For indices i < idx, we add (x - b[i]). The sum is then:
    // idx * x - (b[0] + b[1] + ... + b[idx-1])
    return idx * x - psumEnd[idx];
}

ll cS(const vector<ll>& c, const vector<ll>& psumStart, ll x) {
    // Find the first index where c[i] > x.
    int idx = upper_bound(c.begin(), c.end(), x) - c.begin();
    int n = c.size();
    // Sum of elements from idx to n-1 is psumStart[n] - psumStart[idx]
    ll sumOverElements = psumStart[n] - psumStart[idx];
    // Each of these (n-idx) elements contributes a subtraction of x.
    return sumOverElements - (n - idx) * x;
}


void solve(int& tc) {
    int k,n;
    cin >> k >> n;
    vector<pi> a;

    ll ans = 0;
    vll b;
    vll c;
    for (int i = 0; i < n; ++i){
        char z1,z2;
        int p1,p2;
        cin >> z1 >> p1 >> z2 >> p2;
        if (z1 == z2){
            ans += abs(p2-p1);
        } else {
            a.emplace_back(min(p1,p2),max(p1,p2));
            b.emplace_back(min(p1,p2));
            c.emplace_back(max(p1,p2));
        }
    }

    n = a.size();
    ans += n;

    sort(b.begin(),b.end());
    sort(c.begin(),c.end());

    ll s = 0;
    for (int i = 0; i < n; ++i)
        s += a[i].second-a[i].first;


    vll psumStart;
    psumStart.emplace_back(0);

    vll psumEnd;
    psumEnd.emplace_back(0);
    for (int i = 0; i < n; ++i){
        psumStart.emplace_back(psumStart.back() + b[i]);
        psumEnd.emplace_back(psumEnd.back() + c[i]);
    }

    ll gans = INF/3;
    for (int i = 0; i < n; ++i){
        ll x = a[i].first;
        ll temp = 2ll*(bS(c,psumEnd,x) + cS(b,psumStart,x));
        gans = min(gans,temp);

        x = a[i].second;
        temp = 2ll*(bS(c,psumEnd,x) + cS(b,psumStart,x));
        gans = min(gans,temp);
    }

    print(ans + s + gans);





}


int main() {
    fast_io;
    int t;
    t = 1;
  //  cin >> t;
    time__("solve") {
        preload();
        int x = 0;
        while (t-- > 0) {
            x++;
            solve(x);
        }
    }

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:32:15: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'std::chrono::duration<long int, std::ratio<1, 1000> >::rep' {aka 'long int'} [-Wformat=]
   32 |         debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
      |               ^~~~~~~~~~~~~~~     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                                                                                                                                            |
      |                                                                                                                                            std::chrono::duration<long int, std::ratio<1, 1000> >::rep {aka long int}
bridge.cpp:27:36: note: in definition of macro 'debug'
   27 | #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
      |                                    ^~~~~~~~~~~
bridge.cpp:135:5: note: in expansion of macro 'time__'
  135 |     time__("solve") {
      |     ^~~~~~
bridge.cpp:32:23: note: format string is defined here
   32 |         debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
      |                    ~~~^
      |                       |
      |                       long long int
      |                    %ld

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37