Submission #352452

#	Time	Username	Problem	Language	Result	Execution time	Memory
352452		CaroLinda	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	269 ms	32468 KiB

bridge

#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
 
const ll inf = 1e18 ;
const int MAXN = 1e5+10 ;
 
using namespace std ;
 
int N , K ;
long long ans ;
vector< vector<int> > sweep ;
vector< vector<int> > sweepIni ;
vector<ll> p , pref, suf, qtdPref, qtdSuf ;
multiset<tuple<ll,ll,ll> > s[2] ;
multiset<ll> ss[2] ;
ll fat ;
ll toSum[2] , toSubtract[2] , qtdSum[2] , qtdSubtract[2] , val[2] ; 
 
void add(int i, int j, int idx )
{
	for(auto e : sweep[j] )
	{
		if(e <= i ) continue ;
 
		toSubtract[idx] += p[j-1] ;
		qtdSubtract[idx]++ ;
 
		s[idx].insert( make_tuple( p[j-1] + p[e-1] - p[i-1] + fat , p[e-1] , p[j-1] ) ) ;
	}
}
 
void print(int idx )
{
	printf("Printing index %d\n", idx ) ;
	for(auto e : s[idx] ) printf("%lld %lld %lld\n", get<0>(e), get<1>(e) , get<2>(e) ) ;
	printf("toSum %lld, qtdSum %lld\ntoSubtract %lld, qtdSubtract %lld\n\n", toSum[idx], qtdSum[idx], toSubtract[idx], qtdSubtract[idx] ) ;
}
 
void compress(int i , int j,int idx )
{
	while( !s[idx].empty() && p[j-1] >= get<0>(*s[idx].begin() )-fat ) 
	{
		auto t = *s[idx].begin() ;
		s[idx].erase(s[idx].begin() ) ;
 
		toSubtract[idx] -= get<2>(t) ;
		qtdSubtract[idx]-- ;
 
		if( get<1>(t) <= p[i-1] ) continue ;
 
		toSum[idx] += get<1>(t) ;
		qtdSum[idx]++ ;
 
		ss[idx].insert( get<1>(t) ) ;
	}
	while( !ss[idx].empty() && p[i-1] >= *ss[idx].begin() ) 
	{
		toSum[idx] -= *ss[idx].begin() ;
		qtdSum[idx]-- ;
		ss[idx].erase(ss[idx].begin() ) ;
	}
}
 
ll getAns(int i, int j , int idx) { return qtdPref[i] * p[i-1] - pref[i] + suf[j] - qtdSuf[j] * p[j-1] + toSum[idx] - qtdSum[idx]*p[i-1] + qtdSubtract[idx]*p[j-1] - toSubtract[idx] ; }
 
int main()
{
	scanf("%d %d", &K , &N ) ;
 
	vector<pair<int,int> > intervals ;
 
	for(int i= 1; i <= N ; i++ )
	{
		char z1, z2 ;
		int x, y ;
		scanf(" %c %d %c %d", &z1, &x, &z2, &y ) ;
		
		if( x > y ) swap(x,y) ;
 
		ans += (ll)(y-x) ;
 
		if( z1 == z2 ) continue ;
 
		ans++ ;
 
		intervals.push_back(make_pair(x,y) ) ;
 
		p.push_back(x) ;
		p.push_back(y) ;	
 
	}
 
	sort(all(p) ) ;
	p.erase(unique(all(p) ), p.end() ) ;
 
	pref.resize( sz(p)+5 , 0 ) ; suf.resize(sz(p)+5, 0 ) ;
	qtdPref.resize(sz(p) + 5 , 0 ) ; qtdSuf.resize(sz(p)+5, 0 ) ;
 
	for(auto &e : intervals )
	{
		e.first = lower_bound(all(p), e.first ) - p.begin() + 1 ;
		e.second = lower_bound(all(p), e.second ) - p.begin() + 1 ;
 
		pref[e.second+1] += (ll)p[e.second-1] ;
		qtdPref[e.second+1]++ ;
		suf[e.first-1] += (ll)(p[e.first-1]) ;
		qtdSuf[e.first-1]++ ;
 
	}
 
	for(int i= 1 ; i <= sz(p) ; i++ ) pref[i] += pref[i-1] , qtdPref[i] += qtdPref[i-1] ;
	for(int i = sz(p) ; i >= 0 ; i-- ) suf[i] += suf[i+1] , qtdSuf[i] += qtdSuf[i+1] ;
 
	long long mn = (sz(intervals) == 0 ) ? 0 : inf ;
 
	for(int i = 1 ; i <= sz(p) ; i++ ) mn = min( mn, (qtdPref[i]-qtdSuf[i] )*p[i-1] -pref[i] + suf[i] ) ;
 
   if( sz(p) == 2 && K == 2 ) mn = 0 ;
 
	if( K == 1 || sz(p) <= 2 ) 
	{
		printf("%lld\n", ans + 2LL * mn ) ;
		return 0  ;
	}
 
	// -------------- tricky part begins here --------------
 
	sweep.resize( sz(p)+5 , vector<int>() ) ;
	sweepIni.resize( sz(p)+5 , vector<int>() ) ;
	for(auto e : intervals ) 
	{
		sweep[e.second].push_back( e.first ) ;
		sweepIni[e.first].push_back( e.second ) ;
	}
    
	add(1,1,0) ; add(1,2,0) ; 
	add(1,1,1) ; add(1,2,1) ; add(1,3,1) ;
 
	for(int opt = 2 , i = 1 ; i < sz(p) ; i++ )
   {
		
		compress(i,opt,0) ;
		if( opt+1 <= sz(p) ) compress(i,opt+1, 1) ;		
		 
	   val[0] = getAns(i,opt,0) ;
	   val[1] = (opt+1 <= sz(p) ) ?getAns(i,opt+1,1) : inf ;
 
 
		while( opt < i || (opt < sz(p) && val[1] <= val[0])  )
		{
			add(i,++opt,0) ; compress(i,opt,0) ;
			if( opt+1 <= sz(p) ) 
			{
				add(i, opt+1, 1) ;
				compress(i,opt+1, 1 ) ;
			}
 
			val[0] = getAns(i,opt,0) ;
		   val[1] = (opt+1 <= sz(p) ) ? getAns(i,opt+1,1) : inf ;
 
		 //  cout << i << " " << opt << " " << val[0] << endl ;
		}
 
 
		if( val[0] < mn ) mn = val[0] ;
 
		fat += p[i] - p[i-1] ;
 
   }
	 
	printf("%lld\n", ans + 2LL*mn ) ;
 
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d %d", &K , &N ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf(" %c %d %c %d", &z1, &x, &z2, &y ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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