oj.uz

Submission #882924

# Submission time Handle Problem Language Result Execution time Memory
882924 2023-12-04T07:25:21 Z NotLinux Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 12736 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18 + 7;
struct ONLINE_MEDIAN{
	int sum1 = 0 , sum2 = 0 , sz = 0;
	multiset < int > s1,s2;
	void insert(int x){
		sum2 += x;
		s2.insert(x);
		sz++;
		while(s1.size() < ((sz+1)/2)){
			sum1 += *s2.begin();
			s1.insert(*s2.begin());
			sum2 -= *s2.begin();
			s2.erase(s2.begin());
		}
		while(s2.size() and *(--s1.end()) > *(s2.begin())){
			sum2 += *(--s1.end());
			s2.insert(*(--s1.end()));
			sum1 -= *(--s1.end());
			s1.erase(--s1.end());
			sum1 += *s2.begin();
			s1.insert(*s2.begin()),
			sum2 -= *s2.begin();
			s2.erase(s2.begin());
		}
	}
	void erase(int x){
		if(s1.count(x)){
			sum1 -= x;
			s1.erase(s1.find(x));
		}
		else {
			sum2 -= x;
			s2.erase(s2.find(x));
		}
		sz--;
		while(s1.size() > ((sz+1)/2)){
			sum2 += *(--s1.end());
			s2.insert(*(--s1.end())),
			sum1 -= *(--s1.end());
			s1.erase(--s1.end());
		}
		while(s1.size() < ((sz+1)/2)){
			sum1 += *(s2.begin());
			s1.insert(*s2.begin());
			sum2 -= *(s2.begin());
			s2.erase(s2.begin());
		}
		while(s2.size() and *(--s1.end()) > *(s2.begin())){
			sum2 += *(--s1.end());
			s2.insert(*(--s1.end()));
			sum1 -= *(--s1.end());
			s1.erase(--s1.end());
			sum1 += *s2.begin();
			s1.insert(*s2.begin()),
			sum2 -= *s2.begin();
			s2.erase(s2.begin());
		}
	}
	int get_median(){
		if(s1.empty())return 0;
		return *(--s1.end());
	}
	int get_ans(){
		int medi = get_median();
		return (medi * s1.size() - sum1) + (sum2 - medi * s2.size());
	}
	void debug(){
		cout << "set : ";
		for(auto itr : s1)cout << itr << " ";
		cout << "|";
		for(auto itr : s2)cout << itr << " ";
	}
};
bool cmp(array < int , 3 > const& a , array < int , 3 > const& b){
	return a[0] < b[0];
}
void solve(){
	int k,n,ans0 = 0;
	cin >> k >> n;
	vector < array < int , 3 > > v2;
	for(int i = 0;i<n;i++){
		char c1,c2;
		int p1,p2;
		cin >> c1 >> p1 >> c2 >> p2;
		if(c1 == c2){
			ans0 += abs(p1 - p2);
		}
		else{
			v2.push_back({p1 + p2 , p1 , p2});
		}
	}
	sort(v2.begin() , v2.end() , cmp);
	ONLINE_MEDIAN med1 , med2;
	for(auto itr : v2){
		med2.insert(itr[1]);
		med2.insert(itr[2]);
	}
	int ans1 = inf;
	if(k == 1){
		ans1 = med2.get_ans();
	}
	else{
		for(auto itr : v2){
			med2.erase(itr[1]);
			med2.erase(itr[2]);
			med1.insert(itr[1]);
			med1.insert(itr[2]);
			ans1 = min(ans1 , med1.get_ans() + med2.get_ans());
		}
	}
	cout << ans0 + (ans1 == inf ? 0ll : ans1) + v2.size() << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Compilation message

bridge.cpp: In member function 'void ONLINE_MEDIAN::insert(long long int)':
bridge.cpp:12:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   12 |   while(s1.size() < ((sz+1)/2)){
      |         ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp: In member function 'void ONLINE_MEDIAN::erase(long long int)':
bridge.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   39 |   while(s1.size() > ((sz+1)/2)){
      |         ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp:45:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |   while(s1.size() < ((sz+1)/2)){
      |         ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 62 ms 12004 KB Output is correct
13 Correct 88 ms 12736 KB Output is correct
14 Correct 74 ms 11464 KB Output is correct
15 Correct 47 ms 7344 KB Output is correct
16 Correct 62 ms 12224 KB Output is correct
17 Correct 64 ms 12736 KB Output is correct
18 Correct 67 ms 11956 KB Output is correct
19 Correct 70 ms 12152 KB Output is correct
20 Correct 61 ms 11960 KB Output is correct
21 Correct 64 ms 12136 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 2 ms 360 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 3 ms 348 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Execution timed out 2033 ms 12732 KB Time limit exceeded
26 Halted 0 ms 0 KB -