제출 #1282099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282099		swishy123	Palembang Bridges (APIO15_bridge)	C++20	49 / 100	2101 ms	172424 KiB

bridge

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iomanip>
#include <queue>
#include <cassert>
#include <complex>
#include <cstring>
#include <memory>
#include <bitset>
#include <sstream>
#include <cmath>
#include <numeric>
#include <numbers>
#include <fstream>

using namespace std;

// #include <genlib.h>
// using namespace genlib;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #include <tr2/dynamic_bitset>   
// using namespace tr2;

#ifndef template
#ifndef define

#pragma GCC target("popcnt")
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pi pair<int, int>
#define nl cout << '\n';
#define x first
#define y second 
#define cbit(x) __builtin_popcountll(x)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng) 
#define siz(x) (int)x.size()
#define all(x) (x).begin(), (x).end() 
 
#endif
 
#ifndef print
void print(size_t x) {cout << x << ' ';}
void print(int x) {cout << x << ' ';}
void print(long long x) {cout << x << ' ';}
void print(float x) {cout << x << ' ';}
void print(long double x) {cout << x << ' ';}
void print(char x) {cout << x << ' ';}
void print(const char* x) {cout << x << ' ';}
void print(bool x) {cout << x << ' ';}
void print(string &x) {cout << x << ' ';}
 
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.x); print(p.y);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
    for (int i = 0; i < v.size(); i++){
        for (int j = 0; j < v[i].size(); j++)
            print(v[i][j]);
        nl;
    }
}
template <typename T, typename... V>
void print(T t, V&&... v) {print(t); print(v...);}
 
#endif
 
#ifndef read
void read(int &x) {cin >> x;}
void read(long long &x) {cin >> x;}
void read(unsigned &x) {cin >> x;}
void read(unsigned long long &x) {cin >> x;}
void read(float &x) {cin >> x;}
void read(long double &x) {cin >> x;}
void read(char &x) {cin >> x;}
void read(string &x) {cin >> x;}
void read(bool &x) {cin >> x;}
 
template<typename T> 
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++)
        read(v[i]);
}
template <typename T, typename... V>
void read(T &t, V&... v) {read(t); read(v...);}
#endif
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template<class... Args>
auto vec(size_t n, Args&&... args) {
    if constexpr(sizeof...(args) == 1)
        return vector(n, args...);
    else
        return vector(n, vec(args...));
}
 
#endif

const ll inf = 1e18;
const ll def = 5e6+1;
const ll mod = 1e9+7;

struct Segment{
    int l, r;
    float mid;
    Segment(int l, int r) : l(l), r(r){
        mid = (float)(l + r) / (float)2;
    }
};

struct Node{
    ll sum, lazy, tl, tr;
    int l, r;

    Node(){}
    Node(int l, int r) : tl(l), tr(r), lazy(0), sum(0), l(-1), r(-1){} 
};

Node st[def];
int siz = 0;

void extend(int u){
    int tl = st[u].tl, tr = st[u].tr;
    int l = st[u].l, r = st[u].r;
    
    if (tl == tr) return;
    int mid = (tl + tr) / 2;

    if (l == -1){
        st[u].l = siz;
        st[siz++] = Node(tl, mid);
    }
    if (r == -1){
        st[u].r = siz;
        st[siz++] = Node(mid + 1, tr);
    }
}       
void push(int u){
    ll lazy = st[u].lazy;
    int l = st[u].l, r = st[u].r;

    if (l != -1){
        st[l].sum += (st[l].tr - st[l].tl + 1) * lazy;
        st[l].lazy += lazy;
    }
    if (r != -1){
        st[r].sum += (st[r].tr - st[r].tl + 1) * lazy;
        st[r].lazy += lazy;
    }
    st[u].lazy = 0;
}   

void update(int ql, int qr, int crr, int x){
    if (ql > st[crr].tr || qr < st[crr].tl)
        return;
    if (st[crr].tl >= ql && st[crr].tr <= qr){
        st[crr].sum += (st[crr].tr - st[crr].tl + 1) * x;
        st[crr].lazy += x;
        return;
    }
    extend(crr);
    push(crr);

    update(ql, qr, st[crr].l, x);
    update(ql, qr, st[crr].r, x);

    st[crr].sum = st[st[crr].l].sum + st[st[crr].r].sum;
}

ll get(int ql, int qr, int crr){
    if (ql > st[crr].tr || qr < st[crr].tl)
        return 0;
    if (st[crr].tl >= ql && st[crr].tr <= qr)
        return st[crr].sum;
    extend(crr);
    push(crr);

    return get(ql, qr, st[crr].l) + get(ql, qr, st[crr].r);
}

void solve(){
    int k, n;
    cin >> k >> n;

    ll add = 0;
    vector<Segment> sm;

    vector<int> v;
    for (int i = 0; i < n; i++){
        char p, q;
        ll s, t;

        read(p, s, q, t);

        if (p == q)
            add += abs(s - t);
        else{
            add++;
            if (s > t)
                swap(s, t);
            v.push_back(s);
            v.push_back(t);
            sm.push_back(Segment(s, t));
        }
    }

    sort(v.begin(), v.end());
    v.erase(unique(all(v)), v.end());

    n = sm.size();
    sort(sm.begin(), sm.end(), [](Segment a, Segment b){
        return a.mid < b.mid;
    });

    int bound = 1e9;

    vector<ll> pref(n + 1, inf);
    vector<ll> suff(n + 1, inf);
    
    pref[0] = 0;
    suff[0] = 0;
    
    for (int o = 0; o < 2; o++){
        siz = 1;
        st[0] = Node(0, bound);

        for (int i = 1; i <= n; i++){
            int l = sm[i - 1].l, r = sm[i - 1].r;   
            update(0, 0, 0, (r - l) + l * 2 + 2);
            update(0, l, 0, -2);
            update(r + 1, bound, 0, 2);

            l = 0, r = v.size() - 1;
            while (r - l > 3){
                int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
                ll val1 = get(0, v[mid1], 0), val2 = get(0, v[mid2], 0);
    
                if (val1 <= val2)
                    r = mid2;
                else
                    l = mid1;
            }
            for (int j = l; j <= r; j++)
                pref[i] = min(pref[i], get(0, v[j], 0));
        }
        reverse(sm.begin(), sm.end());
        swap(pref, suff);
    }
    reverse(suff.begin(), suff.end());

    if (k == 1)
        cout << pref[n] + add;
    else{
        ll res = inf;
        for (int i = 0; i <= n; i++)
            res = min(res, pref[i] + suff[i]);
        cout << res + add;
    }
}                 

/* 
*/  

main(){ 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (ifstream("input.txt").good()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    }

    int t;
    t = 1;
    
    while (t--){
        solve();
        nl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp:285:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  285 | main(){
      | ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:290:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  290 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:291:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  291 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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