제출 #114947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114947		Mercenary	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	106 ms	4100 KiB

bridge

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;

int k , n;
vector<ii> a;

namespace Median_heap{
    ll lsum , hsum;
    priority_queue<int,vector<int>,greater<int>> h;
    priority_queue<int> l;
    void add(int a , int b){
        if(a > b)swap(a,b);
        l.push(a);h.push(b);
        lsum += a , hsum += b;
        while(l.top() > h.top()){
            int u = l.top();int v = h.top();
            lsum += v - u;
            hsum += u - v;
            l.pop();h.pop();
            l.push(v);
            h.push(u);
        }
    }
    ll Now(){
        assert(l.size() == h.size());
//        cout << hsum << " " << lsum << endl;
        return hsum - lsum;
    }
    void clear(){
        lsum = hsum = 0;
        while(!l.empty()){
            cerr << l.top() << endl;
            l.pop();
        }
        while(!h.empty()){
            cerr << h.top() << endl;
            h.pop();
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> k >> n;
    ll res = 0;
    ll res1 = (ll)1e18;
    for(int i = 1 ; i <= n ; ++i){
        char side , side1;
        int x, y;
        cin >> side >> x >> side1 >> y;
        if(x > y)swap(x,y);
        if(side == side1){
            res += y - x;
        }else{
            res++;
            a.pb(mp(x,y));
        }
    }
    if(a.size() == 0)return cout << res , 0;
    sort(a.begin(),a.end(),[](const ii x , const ii y){
            return x.first + x.second < y.first + y.second;
         });
    vector<ll> pre(a.size() + 2 , 0) , suf(a.size() + 2 , 0);
    Median_heap::clear();
    for(int i = 0 ; i < a.size() ; ++i){
        Median_heap::add(a[i].first,a[i].second);
        pre[i] = Median_heap::Now();
    }
    Median_heap::clear();
    for(int i = a.size() - 1 ; i >= 0 ; --i){
        Median_heap::add(a[i].first,a[i].second);
        suf[i] = Median_heap::Now();
    }
    if(k == 2){
        for(int i = 0 ; i < a.size() ; ++i){
            res1 = min(res1 , pre[i] + suf[i + 1]);
        }
    }else res1 = pre[a.size() - 1];
    assert(suf[0] == pre[a.size() -1]);
    res += res1;
    cout << res;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < a.size() ; ++i){
                     ~~^~~~~~~~~~
bridge.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < a.size() ; ++i){
                         ~~^~~~~~~~~~
bridge.cpp:59:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:60:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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