oj.uz

Submission #43648

# Submission time Handle Problem Language Result Execution time Memory
43648 2018-03-19T04:17:13 Z comtalyst Palembang Bridges (APIO15_bridge) C++14
100 / 100
 1617 ms 50628 KB 
/*
 *	Task: apio15_bridges
 *	Lang: C/C++11
 *	Site: oj.uz
 *	Last Update: 19/3/2018
 */

#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;

/* Note
----------------------------
Learned : 
Bugs found & solved :
Optimizations :
----------------------------
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(),x.end()
#define long long long
#define MOD 1000000007
#define MAX (int)(1e9+5)
#define MIN (int)(-1e9-5)
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIO_ freopen("__in.txt","r",stdin),freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)
#define FILEIO(text) freopen(text".in","r",stdin),freopen(text".out","w",stdout)

template<typename T>using oset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
char c1[5],c2[5];
pair<long,long> a[100005];
vector<long> pos(1,0);
long sml[600005],smll[600005],smls[600005],smr[600005],smrl[600005],smrs[600005],best[100005];
umap<long,long> wh;
void sm_upl(long tidx,long l,long r,long x,long y,long w,long s){
	long mid = (l+r)/2;
	if(x > r || y < l){
		return;
	}
	if(x <= l && y >= r){
		smll[tidx] += w;
		smls[tidx] += (pos[y]-pos[r])*2*w + s;
		sml[tidx] += (pos[y]-pos[r])*2*w + s + ((pos[r]-pos[l])*(pos[r]-pos[l]+1))*w;
		return;
	}
	if(smll[tidx] || smls[tidx]){
		sm_upl(tidx*2,l,mid,l,r,smll[tidx],smls[tidx]);
		sm_upl(tidx*2+1,mid+1,r,l,r,smll[tidx],smls[tidx]);
		smll[tidx] = smls[tidx] = 0;
	}
	sm_upl(tidx*2,l,mid,x,y,w,s);
	sm_upl(tidx*2+1,mid+1,r,x,y,w,s);
	sml[tidx] = sml[tidx*2] + sml[tidx*2+1];
}
void sm_upr(long tidx,long l,long r,long x,long y,long w,long s){
	long mid = (l+r)/2;
	if(x > r || y < l){
		return;
	}
	if(x <= l && y >= r){
		smrl[tidx] += w;
		smrs[tidx] += (pos[l]-pos[x])*2*w + s;
		smr[tidx] += (pos[l]-pos[x])*2*w + s + ((pos[r]-pos[l])*(pos[r]-pos[l]+1))*w;
		return;
	}
	if(smrl[tidx] || smrs[tidx]){
		sm_upr(tidx*2,l,mid,l,r,smrl[tidx],smrs[tidx]);
		sm_upr(tidx*2+1,mid+1,r,l,r,smrl[tidx],smrs[tidx]);
		smrl[tidx] = smrs[tidx] = 0;
	}
	sm_upr(tidx*2,l,mid,x,y,w,s);
	sm_upr(tidx*2+1,mid+1,r,x,y,w,s);
	smr[tidx] = smr[tidx*2] + smr[tidx*2+1];
}
long sm_get(long tidx,long l,long r,long x){
	long mid = (l+r)/2;
	if(x > r || x < l){
		return 0;
	}
	if(x <= l && x >= r){
		return sml[tidx] + smr[tidx];
	}
	if(smll[tidx] || smls[tidx]){
		sm_upl(tidx*2,l,mid,l,r,smll[tidx],smls[tidx]);
		sm_upl(tidx*2+1,mid+1,r,l,r,smll[tidx],smls[tidx]);
		smll[tidx] = smls[tidx] = 0;
	}
	if(smrl[tidx] || smrs[tidx]){
		sm_upr(tidx*2,l,mid,l,r,smrl[tidx],smrs[tidx]);
		sm_upr(tidx*2+1,mid+1,r,l,r,smrl[tidx],smrs[tidx]);
		smrl[tidx] = smrs[tidx] = 0;
	}
	return sm_get(tidx*2,l,mid,x) + sm_get(tidx*2+1,mid+1,r,x);
}
bool rs(pair<int,int> x,pair<int,int> y){
	return ((double)(x.x+x.y))/2 < ((double)(y.x+y.y))/2;
}
 
main(){
	long t,i,j,k,n,m,x,y,res=0,mn=MAX,v;
	oset<int> apos;
	
	scanf("%lld %lld",&k,&n);
	for(i = 1; i <= n; i++){
		scanf("%s %lld %s %lld",c1,&x,c2,&y);
		x++;
		y++;
		if(x > y) swap(x,y);
		res += abs(y-x);
		if(c1[0] == c2[0]){
			n--;
			i--;
			continue;
		}
		a[i] = {x,y};
		res++;
		pos.emplace_back(x);
		pos.emplace_back(y);
	}
	if(!n){
		printf("%d\n",res);
		return 0;
	}
	sort(all(pos));
	pos.resize(unique(all(pos))-pos.begin());
	m = pos.size()-1;
	sort(a+1,a+1+n,rs);								// sort be mean of x and y then do brute force division
	for(i = 0; i < pos.size(); i++){
		wh[pos[i]] = i;
	}
	for(i = 1; i <= n; i++){
		x = a[i].x;
		y = a[i].y;
		apos.insert(x);
		apos.insert(y);
		sm_upl(1,1,m,1,wh[x],1,0);
		sm_upr(1,1,m,wh[y],m,1,0);
		best[i] = sm_get(1,1,m,wh[*apos.find_by_order(apos.size()/2)]);		// greedy : best is the middle positions
		if(apos.size()/2+1 < apos.size()) best[i] = min(best[i],sm_get(1,1,m,wh[*apos.find_by_order(apos.size()/2+1)]));
		if(apos.size()/2-1 > 0) best[i] = min(best[i],sm_get(1,1,m,wh[*apos.find_by_order(apos.size()/2-1)]));
	}
	if(k == 1){
		printf("%lld\n",res+best[n]);
		return 0;
	}
	memset(sml,0,sizeof sml);
	memset(smll,0,sizeof smll);
	memset(smls,0,sizeof smls);
	memset(smr,0,sizeof smr);
	memset(smrl,0,sizeof smrl);
	memset(smrs,0,sizeof smrs);
	apos.clear();
	mn = best[n];
	for(i = n; i >= 1; i--){
		x = a[i].x;
		y = a[i].y;
		apos.insert(x);
		apos.insert(y);
		sm_upl(1,1,m,1,wh[x],1,0);
		sm_upr(1,1,m,wh[y],m,1,0);
		mn = min(mn,sm_get(1,1,m,wh[*apos.find_by_order(apos.size()/2)]) + best[i-1]);
		if(apos.size()/2+1 < apos.size()) mn = min(mn,sm_get(1,1,m,wh[*apos.find_by_order(apos.size()/2+1)]) + best[i-1]);
		if(apos.size()/2-1 > 0) mn = min(mn,sm_get(1,1,m,wh[*apos.find_by_order(apos.size()/2-1)]) + best[i-1]);
	}
	printf("%lld\n",mn+res);
 
	return 0;	
}

Compilation message

bridge.cpp:111:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
bridge.cpp: In function 'int main()':
bridge.cpp:133:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("%d\n",res);
                    ^
bridge.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < pos.size(); i++){
               ^
bridge.cpp:112:7: warning: unused variable 't' [-Wunused-variable]
  long t,i,j,k,n,m,x,y,res=0,mn=MAX,v;
       ^
bridge.cpp:112:11: warning: unused variable 'j' [-Wunused-variable]
  long t,i,j,k,n,m,x,y,res=0,mn=MAX,v;
           ^
bridge.cpp:112:36: warning: unused variable 'v' [-Wunused-variable]
  long t,i,j,k,n,m,x,y,res=0,mn=MAX,v;
                                    ^
bridge.cpp:115:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&k,&n);
                          ^
bridge.cpp:117:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %s %lld",c1,&x,c2,&y);
                                       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 5 ms 824 KB Output is correct
5 Correct 5 ms 1080 KB Output is correct
6 Correct 4 ms 1080 KB Output is correct
7 Correct 4 ms 1080 KB Output is correct
8 Correct 4 ms 1080 KB Output is correct
9 Correct 5 ms 1080 KB Output is correct
10 Correct 4 ms 1080 KB Output is correct
11 Correct 5 ms 1080 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1080 KB Output is correct
2 Correct 2 ms 1080 KB Output is correct
3 Correct 3 ms 1080 KB Output is correct
4 Correct 5 ms 1080 KB Output is correct
5 Correct 5 ms 1080 KB Output is correct
6 Correct 3 ms 1080 KB Output is correct
7 Correct 6 ms 1080 KB Output is correct
8 Correct 4 ms 1080 KB Output is correct
9 Correct 5 ms 1080 KB Output is correct
10 Correct 3 ms 1080 KB Output is correct
11 Correct 6 ms 1080 KB Output is correct
12 Correct 267 ms 13932 KB Output is correct
13 Correct 861 ms 46780 KB Output is correct
14 Correct 397 ms 46780 KB Output is correct
15 Correct 474 ms 46780 KB Output is correct
16 Correct 251 ms 46780 KB Output is correct
17 Correct 589 ms 47008 KB Output is correct
18 Correct 364 ms 47008 KB Output is correct
19 Correct 612 ms 47008 KB Output is correct
20 Correct 255 ms 47008 KB Output is correct
21 Correct 526 ms 47008 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 47008 KB Output is correct
2 Correct 1 ms 47008 KB Output is correct
3 Correct 22 ms 47008 KB Output is correct
4 Correct 23 ms 47008 KB Output is correct
5 Correct 27 ms 47008 KB Output is correct
6 Correct 23 ms 47008 KB Output is correct
7 Correct 22 ms 47008 KB Output is correct
8 Correct 22 ms 47008 KB Output is correct
9 Correct 22 ms 47008 KB Output is correct
10 Correct 22 ms 47008 KB Output is correct
11 Correct 23 ms 47008 KB Output is correct
12 Correct 22 ms 47008 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 47008 KB Output is correct
2 Correct 1 ms 47008 KB Output is correct
3 Correct 22 ms 47008 KB Output is correct
4 Correct 22 ms 47008 KB Output is correct
5 Correct 23 ms 47008 KB Output is correct
6 Correct 22 ms 47008 KB Output is correct
7 Correct 24 ms 47008 KB Output is correct
8 Correct 23 ms 47008 KB Output is correct
9 Correct 23 ms 47008 KB Output is correct
10 Correct 22 ms 47008 KB Output is correct
11 Correct 25 ms 47008 KB Output is correct
12 Correct 22 ms 47008 KB Output is correct
13 Correct 23 ms 47008 KB Output is correct
14 Correct 28 ms 47008 KB Output is correct
15 Correct 28 ms 47008 KB Output is correct
16 Correct 23 ms 47008 KB Output is correct
17 Correct 23 ms 47008 KB Output is correct
18 Correct 23 ms 47008 KB Output is correct
19 Correct 23 ms 47008 KB Output is correct
20 Correct 26 ms 47008 KB Output is correct
21 Correct 25 ms 47008 KB Output is correct
22 Correct 26 ms 47008 KB Output is correct
23 Correct 23 ms 47008 KB Output is correct
24 Correct 26 ms 47008 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 47008 KB Output is correct
2 Correct 1 ms 47008 KB Output is correct
3 Correct 21 ms 47008 KB Output is correct
4 Correct 23 ms 47008 KB Output is correct
5 Correct 22 ms 47008 KB Output is correct
6 Correct 25 ms 47008 KB Output is correct
7 Correct 21 ms 47008 KB Output is correct
8 Correct 25 ms 47008 KB Output is correct
9 Correct 22 ms 47008 KB Output is correct
10 Correct 22 ms 47008 KB Output is correct
11 Correct 22 ms 47008 KB Output is correct
12 Correct 22 ms 47008 KB Output is correct
13 Correct 23 ms 47008 KB Output is correct
14 Correct 25 ms 47008 KB Output is correct
15 Correct 27 ms 47008 KB Output is correct
16 Correct 22 ms 47008 KB Output is correct
17 Correct 23 ms 47008 KB Output is correct
18 Correct 23 ms 47008 KB Output is correct
19 Correct 23 ms 47008 KB Output is correct
20 Correct 28 ms 47008 KB Output is correct
21 Correct 24 ms 47008 KB Output is correct
22 Correct 26 ms 47008 KB Output is correct
23 Correct 24 ms 47008 KB Output is correct
24 Correct 26 ms 47008 KB Output is correct
25 Correct 390 ms 47008 KB Output is correct
26 Correct 550 ms 47008 KB Output is correct
27 Correct 1509 ms 49796 KB Output is correct
28 Correct 1617 ms 50520 KB Output is correct
29 Correct 1567 ms 50520 KB Output is correct
30 Correct 709 ms 50520 KB Output is correct
31 Correct 391 ms 50520 KB Output is correct
32 Correct 1033 ms 50520 KB Output is correct
33 Correct 565 ms 50520 KB Output is correct
34 Correct 1040 ms 50520 KB Output is correct
35 Correct 439 ms 50520 KB Output is correct
36 Correct 890 ms 50628 KB Output is correct
37 Correct 422 ms 50628 KB Output is correct