Hướng dẫn giải của CP GBUP
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include<bits/stdc++.h> #define int long long using namespace std; struct Sus { priority_queue<pair<int, int>> left_part, delete_left_part; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> right_part, delete_right_part; int sum_left = 0, sum_right = 0; void init() { sum_left = sum_right = 0; while(left_part.size() > 0) left_part.pop(); while(right_part.size() > 0) right_part.pop(); while(delete_left_part.size() > 0) delete_left_part.pop(); while(delete_right_part.size() > 0) delete_right_part.pop(); } void add(pair<int, int> v){ if(right_part.size() == 0 || v < right_part.top()){ left_part.push(v); sum_left += v.second; } else{ right_part.push(v); sum_right += v.second; } } void del(pair<int, int> v){ if(right_part.size() == 0 || v < right_part.top()){ sum_left -= v.second; if(left_part.size() > 0 && left_part.top() == v) left_part.pop(); else delete_left_part.push(v); } else{ sum_right -= v.second; if(right_part.size() > 0 && right_part.top() == v) right_part.pop(); else delete_right_part.push(v); } } void clean_left(){ while(delete_left_part.size() > 0 && left_part.top() == delete_left_part.top()){ left_part.pop(); delete_left_part.pop(); } } void clean_right(){ while(delete_right_part.size() > 0 && right_part.top() == delete_right_part.top()){ right_part.pop(); delete_right_part.pop(); } } void balance(){ while(sum_left < sum_right){ clean_right(); pair<int, int> v = right_part.top(); right_part.pop(); sum_left += v.second; sum_right -= v.second; left_part.push(v); } while(sum_left > sum_right){ clean_left(); pair<int, int> v = left_part.top(); left_part.pop(); sum_right += v.second; sum_left -= v.second; right_part.push(v); } } int maxval(){ balance(); int ans = sum_left * sum_right; clean_right(); pair<int, int> v = right_part.top(); //This should always exist ans = max(ans, (sum_left + v.second) * (sum_right - v.second)); return ans; } inline int sz(){return left_part.size() + right_part.size();} vector<pair<int, int>> all_element(){ vector<pair<int, int>> ans; while(left_part.size() > 0){ clean_left(); if(left_part.size() == 0) break; ans.push_back(left_part.top()); left_part.pop(); } while(right_part.size() > 0){ clean_right(); if(right_part.size() == 0) break; ans.push_back(right_part.top()); right_part.pop(); } init(); return ans; } }; const int maxlen = 12; signed main() { int n, q; cin>>n>>q; auto encode = [&](string s) -> pair<int, int>{ int num = 0, sum = 0; for(int i = 0; i < s.size(); i++) sum += s[i] - 'a' + 1001; while(s.size() < maxlen) s.push_back('a' - 1); for(int i : s) num = num * 27 + i; //This is smaller than 2e17 return make_pair(num, sum); }; vector<Sus> st(n+5); for(int i = 1; i <= n; i++){ int m; cin>>m; for(int j = 1; j <= m; j++){ string s; cin>>s; st[i].add(encode(s)); } } for(int test = 0; test < q; test++){ int type; cin>>type; if(type == 1){ int p; string s; cin>>p>>s; st[p].add(encode(s)); } else if(type == 2){ int p; string s; cin>>p>>s; st[p].del(encode(s)); } else if(type == 3){ int u, v; cin>>u>>v; if(st[u].sz() > st[v].sz()){ swap(st[u].sum_left, st[v].sum_left); swap(st[u].sum_right, st[v].sum_right); st[u].left_part.swap(st[v].left_part); st[u].right_part.swap(st[v].right_part); st[u].delete_left_part.swap(st[v].delete_left_part); st[u].delete_right_part.swap(st[v].delete_right_part); } vector<pair<int, int>> val = st[u].all_element(); for(pair<int, int> i : val) st[v].add(i); } else{ int p; cin>>p; cout<<st[p].maxval()<<'\n'; } } }
Đang tải...