Submission #49762

#	Time	Username	Problem	Language	Result	Execution time	Memory
49762		hamzqq9	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	371 ms	14048 KiB

bridge

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 998244353
#define inf 1000000000000000000
#define M 10000002
#define N 100005
#define LOG 40
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;

int sz,n,k,x1,x2;
ll ans=inf,pre[N],suf[N],Sum[N*8],add;
int Ok[N*8],tut[N*2];
vector<ii> seg;
char c1,c2;

void clear() {

	memset(Sum,0,sizeof(Sum));
	memset(Ok,0,sizeof(Ok));

}

ll getsum(int node,int bas,int son,int x,int y) {

	if(bas>y || son<x) return 0;

	if(bas>=x && son<=y) return Sum[node];

	return getsum(node*2,bas,orta,x,y)+getsum(node*2+1,orta+1,son,x,y);

}

int getkth(int node,int bas,int son,int k) {

	if(bas==son) return bas;

	if(Ok[node*2]>=k) return getkth(node*2,bas,orta,k);

	return getkth(node*2+1,orta+1,son,k-Ok[node*2]);

}

void up(int node,int bas,int son,int x) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		Sum[node]=tut[bas];
		Ok[node]=1;

		return ;

	} 

	up(node*2,bas,orta,x);
	up(node*2+1,orta+1,son,x);

	Sum[node]=Sum[node*2]+Sum[node*2+1];
	Ok[node]=Ok[node*2]+Ok[node*2+1];

}

void compress() {

	vector<iii> v;

	for(int i=0;i<sz;i++) {

		v.pb({seg[i].st,{i,0}});
		v.pb({seg[i].nd,{i,1}});

	}

	sort(all(v));

	for(int i=0;i<2*sz;i++) {

		tut[i+1]=v[i].st;

		if(v[i].nd.nd) {

			seg[v[i].nd.st].nd=i+1;

		}
		else {

			seg[v[i].nd.st].st=i+1;

		}

	}

}

int main() {
 
 	#if 0
	freopen("input.txt","r",stdin);
 	#endif

	scanf("%d %d",&k,&n);

	for(int i=1;i<=n;i++) {

		scanf(" %c %d %c %d",&c1,&x1,&c2,&x2);

		if(c1==c2) add+=abs(x1-x2);
		else {

			if(x1>x2) swap(x1,x2);

			seg.pb({x1,x2});

		}

	}

	sort(all(seg),[](ii x,ii y) {

		return x.st+x.nd<y.st+y.nd;

	});

	sz=sz(seg);

	compress();

	for(int i=0;i<sz;i++) {

		up(1,1,2*sz,seg[i].st);
		up(1,1,2*sz,seg[i].nd);

		int plc=getkth(1,1,2*sz,i+1);

		ll dec=getsum(1,1,2*sz,1,plc);
		ll add=getsum(1,1,2*sz,plc+1,2*sz);

		pre[i+1]=add-dec;

	}

	clear();

	reverse(all(seg));

	for(int i=0;i<sz;i++) {

		up(1,1,2*sz,seg[i].st);
		up(1,1,2*sz,seg[i].nd);

		int plc=getkth(1,1,2*sz,i+1);

		ll dec=getsum(1,1,2*sz,1,plc);
		ll add=getsum(1,1,2*sz,plc+1,2*sz);

		suf[i+1]=add-dec;

	}

	if(k==2) {

		for(int i=1;i<=sz;i++) {

			umin(ans,pre[i]+suf[sz-i]);

		}
	
	}
	else {

		ans=pre[sz];

	}

	printf("%lld",add+ans+sz);

}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&k,&n);
  ~~~~~^~~~~~~~~~~~~~~
bridge.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d",&c1,&x1,&c2,&x2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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