#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct SegTree{
struct Node{
int val;
int cnt;
Node* lnode;
Node* rnode;
Node():cnt(0),val(0),lnode(nullptr),rnode(nullptr){}
Node* crl(){
if (lnode==nullptr) lnode = new Node;
return lnode;
}
Node* crr(){
if (rnode==nullptr) rnode = new Node;
return rnode;
}
};
Node* root;
SegTree():root(new Node){}
void push(int x){
int l = 0, r = MOD;
Node* node = root;
while (l<r){
int mid = l+(r-l)/2;
node->val+=x;
node->cnt++;
if (l==r) break;
if (mid>=x){
r=mid;
node=node->crl();
}
else {
l=mid+1;
node=node->crr();
}
}
node->val+=x;
node->cnt++;
}
void erase(int x){
int l = 0, r = MOD;
Node* node = root;
while (l<r){
int mid = l+(r-l)/2;
node->val-=x;
node->cnt--;
if (l==r) break;
if (mid>=x){
r=mid;
node=node->crl();
}
else {
l=mid+1;
node=node->crr();
}
}
node->val-=x;
node->cnt--;
}
int median(){
int l = 0, r = MOD;
Node* node = root;
int k = node->cnt/2;
while (l<r){
int mid = l+(r-l)/2;
int left = 0;
if (node->lnode!=nullptr) left = node->lnode->cnt;
if (left>=k){
node=node->lnode;
r=mid;
}
else {
k-=left;
node=node->rnode;
l=mid+1;
}
}
return l;
}
pair<int,int> query(int tarl, int tarr, int l = 0, int r = -1, Node* node = nullptr){
if (r==-1){
r=MOD, node=root;
}
if (node==nullptr) return {0,0};
if (l>=tarl && r<=tarr) return {node->val,node->cnt};
if (l>tarr || r<tarl) return {0,0};
int mid = l+(r-l)/2;
pair<int,int> lnode = query(tarl, tarr, l, mid, node->lnode);
pair<int,int> rnode = query(tarl, tarr, mid+1, r, node->rnode);
return {lnode.first+rnode.first,lnode.second+rnode.second};
}
};
struct Solution{
SegTree segtree;
SegTree ls;
SegTree rs;
void push(int l, int r){
ls.push(l);
rs.push(r);
segtree.push(l);
segtree.push(r);
}
void erase(int l, int r){
ls.erase(l);
rs.erase(r);
segtree.erase(l);
segtree.erase(r);
}
int query(){
int x = segtree.median();
pair<int,int> left = rs.query(0,x);
pair<int,int> right = ls.query(x,MOD);
return (left.second*x-left.first+right.first-right.second*x)*2;
}
};
int32_t main(){
ios;
int t=1;
int tno = 0;
if (!t) cin>>t;
while (t-(tno++)){
deci(k);deci(n);
vector<pair<int,int>> segment;
int ans = 0;
for (int i = 0; i < n; i++){
char a,c;
int b,d;
cin>>a>>b>>c>>d;
ans+=abs(b-d);
if (a!=c){
ans++;
segment.push_back({min(b,d),max(b,d)});
}
}
n=segment.size();
vector<int> arr(n+1,0);
vector<int> barr(n+1,0);
Solution soln;
Solution soln2;
for (int i = 1; i <= n; i++){
soln.push(segment[i-1].first,segment[i-1].second);
arr[i]=soln.query();
}
for (int i = 1; i <= n; i++){
barr[n-i+1]=soln.query();
soln.erase(segment[i-1].first,segment[i-1].second);
}
if (k==1) ans+=arr[n];
else {
int crr = arr[0]+barr[n];
for (int i = 0; i <= n; i++){
crr=min(arr[i]+barr[n-i],crr);
}
ans+=crr;
}
cout<<ans<<endl;
}
}
Compilation message
bridge.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize("Bismillahirrahmanirrahim")
|
bridge.cpp: In constructor 'SegTree::Node::Node()':
bridge.cpp:39:7: warning: 'SegTree::Node::cnt' will be initialized after [-Wreorder]
39 | int cnt;
| ^~~
bridge.cpp:38:7: warning: 'long long int SegTree::Node::val' [-Wreorder]
38 | int val;
| ^~~
bridge.cpp:42:3: warning: when initialized here [-Wreorder]
42 | Node():cnt(0),val(0),lnode(nullptr),rnode(nullptr){}
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
2396 KB |
Output is correct |
5 |
Correct |
7 ms |
3932 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
5 ms |
3420 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
4 ms |
2396 KB |
Output is correct |
5 |
Correct |
7 ms |
3928 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
5 ms |
3416 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
97 ms |
3544 KB |
Output is correct |
13 |
Runtime error |
520 ms |
262144 KB |
Execution killed with signal 9 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
1 ms |
496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
500 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |