답안 #882936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882936	2023-12-04T08:01:02 Z	NotLinux	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	109 ms	5604 KB

bridge

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// PUT IT BEFORE THE INCLUDE
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 7;
template<class T, class Container = vector<T>, class Compare = less<T>>
struct PriorityQueue {
  int sz = 0;
  priority_queue<T, Container, Compare> pq, del;
 
  void emplace(const T &val) { pq.emplace(val); ++sz; }
  void erase(const T &val) { del.emplace(val); --sz; }
  void pop() { erase(top()); }
  T top() {
    while (!del.empty() && !pq.empty() && del.top() == pq.top()) del.pop(), pq.pop();
    return pq.top();
  }
  int size() const {return sz;}
};
 
template<class T>
struct MedianHeap {
	long long sumlo = 0 , sumhi = 0;
  PriorityQueue<T> lo;
  PriorityQueue<T, vector<T>, greater<T>> hi; 
 
  void Fix() {
    while (hi.size() > lo.size()){
    	sumlo += hi.top();
    	sumhi -= hi.top();
    	lo.emplace(hi.top());
    	hi.pop();
    }
    while (lo.size() > hi.size() + 1){
    	sumhi += lo.top();
    	sumlo -= lo.top();
    	hi.emplace(lo.top());
    	lo.pop();
    }
  }
  
  void emplace(const T &val) {
    if (lo.size() == 0 || val <= lo.top()){
    	sumlo += val;
    	lo.emplace(val);
    }
    else {
    	sumhi += val;
    	hi.emplace(val);
    }
    Fix();
  }
 
  void erase(const T &val) {
    if (lo.size() && val <= lo.top()){
    	sumlo -= val;
    	lo.erase(val);
    }
    else {
    	sumhi -= val;
    	hi.erase(val);
    }
    Fix();
  }
  long long get_ans(){
  	return (1ll * lo.top() * lo.size() - sumlo) + (sumhi - 1ll * lo.top() * hi.size());
  }
  T top() { return lo.top(); }
};
bool cmp(array < int , 3 > const& a , array < int , 3 > const& b){
	return a[0] < b[0];
}
void solve(){
	int k,n;
	long long 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);
	MedianHeap<int> med1 , med2;
	for(auto itr : v2){
		med2.emplace(itr[1]);
		med2.emplace(itr[2]);
	}
	long long ans1 = inf;
	if(v2.size()){
		if(k == 1){
			ans1 = med2.get_ans();
		}
		else{
			for(auto itr : v2){
				med2.erase(itr[1]);
				med2.erase(itr[2]);
				med1.emplace(itr[1]);
				med1.emplace(itr[2]);
				ans1 = min(ans1 , med1.get_ans() + med2.get_ans());
			}
		}
	}
	else ans1 = 0;
	cout << ans0 + ans1 + v2.size() << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	0 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	600 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	460 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	20 ms	3292 KB	Output is correct
13	Correct	40 ms	4492 KB	Output is correct
14	Correct	31 ms	3524 KB	Output is correct
15	Correct	23 ms	3016 KB	Output is correct
16	Correct	23 ms	4040 KB	Output is correct
17	Correct	31 ms	4536 KB	Output is correct
18	Correct	32 ms	4032 KB	Output is correct
19	Correct	36 ms	4560 KB	Output is correct
20	Correct	27 ms	4300 KB	Output is correct
21	Correct	36 ms	4392 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	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	0 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	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	0 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 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	1 ms	344 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	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	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	600 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	1 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	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	47 ms	4804 KB	Output is correct
26	Correct	86 ms	5508 KB	Output is correct
27	Correct	106 ms	5312 KB	Output is correct
28	Correct	109 ms	5312 KB	Output is correct
29	Correct	109 ms	5320 KB	Output is correct
30	Correct	59 ms	3016 KB	Output is correct
31	Correct	40 ms	4176 KB	Output is correct
32	Correct	74 ms	5572 KB	Output is correct
33	Correct	80 ms	4548 KB	Output is correct
34	Correct	80 ms	5604 KB	Output is correct
35	Correct	54 ms	5084 KB	Output is correct
36	Correct	79 ms	5524 KB	Output is correct
37	Correct	28 ms	4148 KB	Output is correct

답안 #882936

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0