제출 #1028720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028720		vjudge1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	81 ms	8388 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long ll;

vector<ll> a, b, pa, pb;

ll query(ll x, ll y)
{
  ll idx = upper_bound(b.begin(), b.end(), x) - b.begin();
  ll ans = idx * x - pb[idx];

  idx = upper_bound(a.begin(), a.end(), y) - a.begin();
  ans += pa.back() - pa[idx] - (a.size() - idx) * y;
  return ans;
}

signed main()
{
  int k, n;
  cin >> k >> n;
  ll ans = 0;
  vector<pair<int,int> > p;
  for(int i = 0; i < n; i ++)
    {
      char P, Q;
      int s, t;
      cin >> P >> s >> Q >> t;
      if(t < s) swap(s, t);
      if(P == Q)
	ans += t - s;
      else
	{
	  a.push_back(s);
	  b.push_back(t);
	  p.push_back({s, t});
	}
    }

  pa.resize(1 + a.size());
  pb.resize(1 + b.size());
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  
  pa[0] = pb[0] = 0;
  for(int i = 0; i < a.size(); i++)
    {
      pa[i + 1] = pa[i] + a[i];
      pb[i + 1] = pb[i] + b[i];
    }
  
  ans += p.size();
  
  if(k == 1)
    {
      vector<ll> v;
      for(auto [x, y] : p)
	{
	  v.push_back(x);
	  v.push_back(y);
	}
      
      sort(v.begin(), v.end());
      ll testans = 1e18 * (!v.empty()), suf = 0, sz = v.size();
      for(ll i : v) suf += i;
      ll prf = 0, cnt = 0;
      for(ll i : v)
	{
	  testans = min(testans, cnt * i - prf + suf - (sz - cnt) * i);
	  prf += i;
	  suf -= i;
	  cnt++;
	}
      
      ans += testans;
    }
  else
    {
      ll testans = 1e18 * (!p.empty());
      
      vector<ll> v;
      for(auto [x, y] : p)
	v.push_back(y), v.push_back(x), ans += y - x;

      sort(v.begin(), v.end());
      v.resize(unique(v.begin(), v.end()) - v.begin());

      int cnt = 0;
      map<int, vector<pair<int, int> > > mp;
      for(auto [x, y] : p)
	mp[y].push_back({x, cnt++});
      
      for(int i = 0; i < v.size(); i ++)
	{
	  set<pair<int, int> > st;
	  ll cost = 0, costp = 0;
	  for(int j = i; j < v.size(); j++)
	    {
	      ll temp = query(v[i], v[j]);

	      if(st.size())
		cost += 1ll * st.size() * (v[j] - v[j - 1]);
	      
	      while(st.size() && st.begin()->first <= v[j])
		{
		  int idx = st.begin()->second;
		  costp += p[i].first - v[i];
		  cost -= v[j] - p[i].second;
		  st.erase(st.begin());
		}
	      
	      if(j > 0 && !mp[v[j - 1]].empty())
		{
		  for(auto [s, idx] : mp[v[j - 1]])
		    if(v[i] < s)
		      {
			if(s - v[i] <= v[j] - v[j - 1])
			  costp += s - v[i];
			else
			  {
			    cost += v[j] - v[j - 1];
			    st.insert({v[j - 1] + s - v[i], idx});
			  }
		      }
		}
	      testans = min(testans, temp + cost + costp);
	    }
	}
      ans += testans;
    }
  cout << ans << endl;
  return 0;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:48:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
bridge.cpp:95:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |       for(int i = 0; i < v.size(); i ++)
      |                      ~~^~~~~~~~~~
bridge.cpp:99:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for(int j = i; j < v.size(); j++)
      |                   ~~^~~~~~~~~~
bridge.cpp:108:9: warning: unused variable 'idx' [-Wunused-variable]
  108 |     int idx = st.begin()->second;
      |         ^~~

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