제출 #43957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43957		Kerim	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	1227 ms	49972 KiB

bridge

#include "bits/stdc++.h"
#include<ext/pb_ds/assoc_container.hpp>
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
 
typedef pair<int,int> PII;
typedef tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> tes;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll pre[MAXN],suf[MAXN];
vector<PII>v;
vector<int>comp;
bool cmp(PII x,PII y){
	return (x.ff+x.ss<y.ff+y.ss);
}
tes s;
map<int,int>cnt;
pair<ll,int>F[MAXN],sum;
void update(int x,int y){
	sum=mp(sum.ff+y,sum.ss+1);
	for(;x<MAXN;x+=x&(-x))
		F[x]=mp(F[x].ff+y,F[x].ss+1);
}
void upd(int x){
	//~ cout<<"upd " <<x<<endl;
	cnt[x]++;
	s.insert(mp(x,cnt[x]));
	update(upper_bound(all(comp),x)-comp.begin(),x);
}
pair<ll,int>tap(int x){
	pair<ll,int>res=mp(0,0);
	for(;x;x-=x&(-x))
		res=mp(res.ff+F[x].ff,res.ss+F[x].ss);
	return res;	
}
ll solve(int x){
	//~ printf("median %d\n",x);
	pair<ll,int> res=tap(upper_bound(all(comp),x)-comp.begin());
	return (res.ss*1LL*x-res.ff)+((sum.ff-res.ff)-(sum.ss-res.ss)*1LL*x);
}
int main(){
    //~ freopen("file.in", "r", stdin);
    int k,n;
    scanf("%d%d",&k,&n);
	ll ans=0;
	for(int i=1;i<=n;i++){
		char a,c;
		int b,d;
		scanf(" %c%d %c%d",&a,&b,&c,&d);
		if(a!=c){
			v.pb(mp(b,d));
			comp.pb(b);comp.pb(d);
		}
		else
			ans+=abs(b-d);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)),comp.end());
	//~ tr(it,comp)
		//~ cout<<*it<<" ";
	//~ cout<<endl;	
	sort(all(v),cmp);
	for(int i=0;i<int(v.size());i++){
		upd(v[i].ff);upd(v[i].ss);
		pre[i]=solve((s.find_by_order(s.size()/2-1)->ff+s.find_by_order(s.size()/2)->ff)/2);
		//~ tr(it,s)
			//~ cout<<it->ff<<" ";
		//~ cout<<endl;	
		//~ cout<<pre[i]<<endl;
		//~ wr
	}
	s.clear();cnt.clear();
	sum=mp(0,0);
	memset(F,0,sizeof F);
	for(int i=int(v.size())-1;i>=0;i--){
		upd(v[i].ff);upd(v[i].ss);
		suf[i]=solve((s.find_by_order(s.size()/2-1)->ff+s.find_by_order(s.size()/2)->ff)/2);
	}
	ll res=0;
	if(v.size())
		res=pre[v.size()-1];
	if(k==1)
		printf("%lld\n",ans+res+v.size());
	else{
		for(int i=0;i<int(v.size())-1;i++)
			umin(res,pre[i]+suf[i+1]);
		printf("%lld\n",ans+res+v.size());	
	}	
	return 0;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&k,&n);
     ~~~~~^~~~~~~~~~~~~~
bridge.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d",&a,&b,&c,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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