제출 #280958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
280958		ChrisT	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	697 ms	20044 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename t>
using pbds = tree<t,null_type,less<t>,rb_tree_tag,tree_order_statistics_node_update>;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 2e5 + 5;
vector<int> xs;
int getx (int x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
long long bit[MN];
void update (int i, int v) {
	for (;i<MN;i+=i&-i)
		bit[i]+=v;
}
long long query (int i) {
	long long ret = 0;
	for (;i;i^=i&-i)
		ret += bit[i];
	return ret;
}
int main () {
	int k,n; long long add = 0, ans = 8e18;
	scanf ("%d %d",&k,&n); vector<pair<int,int>> v = {{-1,-1}};
	for (int i = 1; i <= n; i++) {
		char c1, c2; int a,b;
		scanf (" %c %d %c %d",&c1,&a,&c2,&b);
		if (a > b) swap(a,b);
		if (c1 == c2) add += b - a;
		else {
			v.emplace_back(a,b);
			xs.push_back(a); xs.push_back(b); 
		}
	}
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	n = (int)v.size() - 1;
	sort(v.begin()+1,v.end(),[](const auto &a, const auto &b){return a.first + a.second < b.first + b.second;});
	//solve K = 1 for each prefix and suffix, merge
	//slope starts at -N, each A/B adds 1, we want to find where it is 0 (because of convexity)
	pbds<pair<int,int>> st; vector<long long> pre(n+1), suf(n+2); long long sum = 0;
	for (int i = 1; i <= n; i++) {
		st.insert({v[i].first,2*i}); st.insert({v[i].second,2*i+1});
		update(getx(v[i].first),v[i].first); update(getx(v[i].second),v[i].second); sum += v[i].first + v[i].second;
		int want = st.find_by_order(i)->first, cnt = st.order_of_key({want,-1});
		long long lowSum = query(getx(want) - 1) + (long long)(i - cnt) * want;
		long long highSum = sum - lowSum;
		pre[i] = highSum - lowSum;
	}
	if (k == 1) return !printf ("%lld\n",pre[n]+add+n);
	st.clear(); memset(bit,0,sizeof bit);sum = 0;
	for (int i = n; i >= 1; i--) {
		st.insert({v[i].first,2*i}); st.insert({v[i].second,2*i+1});
		update(getx(v[i].first),v[i].first); update(getx(v[i].second),v[i].second); sum += v[i].first + v[i].second;
		int want = st.find_by_order(n-i+1)->first, cnt = st.order_of_key({want,-1});
		long long lowSum = query(getx(want) - 1) + (long long)(n - i + 1 - cnt) * want;
		long long highSum = sum - lowSum;
		suf[i] = highSum - lowSum;
	}
	for (int takePre = 0; takePre <= n; takePre++) {
		ans = min(ans,add + pre[takePre] + suf[takePre+1] + n);
	}
	printf ("%lld\n",ans);
	return 0;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  scanf ("%d %d",&k,&n); vector<pair<int,int>> v = {{-1,-1}};
      |  ~~~~~~^~~~~~~~~~~~~~~
bridge.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf (" %c %d %c %d",&c1,&a,&c2,&b);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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