oj.uz

Submission #236298

# Submission time Handle Problem Language Result Execution time Memory
236298 2020-06-01T04:32:34 Z mahmoudbadawy Palembang Bridges (APIO15_bridge) C++17
100 / 100
 477 ms 13036 KB 
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

struct median{
	multiset<int> l,r;
	long long lsum,rsum;
	int med;
	// l < med
	// r med  , > med
	median():lsum(0),rsum(0){}
	void fix()
	{
		// odd: l.size() = r.size()-1 , even: l.size() = r.size() (taking larger as median)
		if(l.size()>r.size())
		{
			med=(*l.rbegin());
			lsum-=med; rsum+=med;
			l.erase(l.find(*l.rbegin()));
			r.insert(med);
		}
		if(r.size() > l.size()+1)
		{
			l.insert(*r.begin());
			lsum+=*r.begin(); rsum-=*r.begin();
			r.erase(r.begin());
			med=*r.begin();
		}
		//cout << lsum << " " << rsum << endl;
	}
	void insert(int x)
	{
		//cout << "Inserting " << x << endl;
		med=r.size()?(*r.begin()):-1;
		if(x<med)
		{
			lsum+=x;
			l.insert(x);
		}
		else
		{
			rsum+=x;
			r.insert(x);
		}
		fix();
	}
	void erase(int x)
	{
		med=r.size()?(*r.begin()):-1;
		if(x<med)
		{
			lsum-=x;
			l.erase(l.find(x));
		}
		else
		{
			rsum-=x;
			r.erase(r.find(x));
		}
		fix();
	}
};

vector< pair<int,int> > v;
int n,k;

bool cmp(pair<int,int> a,pair<int,int> b)
{
	return a.F+a.S < b.F+b.S;
}

int main()
{
	scanf("%d %d",&k,&n);
	long long init=0,ans=(1LL<<60);
	for(int i=0;i<n;i++)
	{
		char s,t;
		int x,y;
		scanf(" %c %d %c %d",&s,&x,&t,&y);
		if(s==t) init+=abs(x-y);
		else v.push_back({x,y});
	}
	n=v.size();
	sort(v.begin(),v.end(),cmp);
	init+=n;
	median l,r;
	for(int i=0;i<n;i++)
	{
		r.insert(v[i].F);
		r.insert(v[i].S);
	}
	ans=r.rsum-r.lsum;
	//cout << r.med << endl;
	/*for(auto i:r.l)
		cout << i << " ";
	cout << endl;
	for(auto i:r.r)
		cout << i << " ";
	cout << endl;*/
	if(k==2)
	{
		for(int i=0;i<n;i++)
		{
			r.erase(v[i].F); l.insert(v[i].F);
			r.erase(v[i].S); l.insert(v[i].S);
			ans=min(ans,(r.rsum-r.lsum)+(l.rsum-l.lsum));
		}
	}
	cout << ans+init << endl;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:76: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:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d",&s,&x,&t,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 400 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 95 ms 11240 KB Output is correct
13 Correct 175 ms 12776 KB Output is correct
14 Correct 174 ms 10732 KB Output is correct
15 Correct 96 ms 7664 KB Output is correct
16 Correct 92 ms 12136 KB Output is correct
17 Correct 106 ms 12776 KB Output is correct
18 Correct 98 ms 12520 KB Output is correct
19 Correct 119 ms 12780 KB Output is correct
20 Correct 101 ms 12396 KB Output is correct
21 Correct 105 ms 12520 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 436 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 512 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 7 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 209 ms 11244 KB Output is correct
26 Correct 349 ms 11500 KB Output is correct
27 Correct 457 ms 12268 KB Output is correct
28 Correct 477 ms 13036 KB Output is correct
29 Correct 456 ms 12780 KB Output is correct
30 Correct 189 ms 6896 KB Output is correct
31 Correct 166 ms 12140 KB Output is correct
32 Correct 206 ms 12776 KB Output is correct
33 Correct 171 ms 12396 KB Output is correct
34 Correct 227 ms 12828 KB Output is correct
35 Correct 222 ms 12520 KB Output is correct
36 Correct 216 ms 12776 KB Output is correct
37 Correct 200 ms 11372 KB Output is correct