이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define upp(a, b) upper_bound(b.begin(), b.end(), a) - b.begin()
typedef long long ll;
const int N = 2e5+4;
const ll inf = 4e18;
struct node{
ll a,b,c;
};
node operator+(node a,node b){
return {a.a + b.a, a.b + b.b, a.c + b.c};
}
struct St{
int n;
node t[N<<2];
void build(int _n){ n = _n;
for (int i=1; i<2*n; i++) t[i] = {0, 0, 0};
}
void up(int i,node val){ i+=n;
for (t[i] = t[i] + val; i>>=1; ) t[i] = t[i<<1] + t[i<<1|1];
}
node que(int l,int r){ node ans = {0, 0, 0};
for (l+=n, r+=n; l<r; l>>=1, r>>=1){
if (l&1) ans = ans + t[l++];
if (r&1) ans = ans + t[--r];
}
return ans;
}
} d3;
int k,n,n1,n2;
ll ans1,ans2;
pair<int,int> a1[N];
vector<int> d1,d2[N];
ll pr[N],Spr[N],su[N],Ssu[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> k >> n; ans2 = inf;
for (int l,r; n; n--){ char cl,cr; cin >> cl >> l >> cr >> r;
if (l > r) swap(l, r); ans1 += r-l;
if (cl != cr) a1[n1++] = {l, r};
}
ans1 += n1;
for (int i=0; i<n1; i++){ auto [l, r] = a1[i];
d1.push_back(l), d1.push_back(r);
}
sort(d1.begin(), d1.end());
d1.erase(unique(d1.begin(), d1.end()), d1.end());
n2 = d1.size();
for (int i=0; i<n1; i++){ auto [l, r] = a1[i];
d2[upp(r, d1)].push_back(upp(l, d1));
pr[upp(r, d1)]++, su[upp(l, d1)]++, Spr[upp(r, d1)] += r, Ssu[upp(l, d1)] += l;
}
for (int i=1; i<=n2; i++) pr[i] += pr[i-1], Spr[i] += Spr[i-1];
for (int i=n2; i>=1; i--) su[i] += su[i+1], Ssu[i] += Ssu[i+1];
// for (int i=1; i<=n2; i++) cout << d1[i-1] << " "; cout << "\n";
// for (int i=1; i<=n2; i++)
// cout << i << " -> " << pr[i] << " " << Spr[i] << " " << su[i] << " " << Ssu[i] << "\n";
if (k == 1) for (int i=1; i<=n2; i++)
ans2 = min(ans2, Ssu[i+1] - Spr[i-1] + d1[i-1]*(pr[i-1] - su[i+1]));
else for (int i=1; i+1<=n2; i++){ vector<int> d4;
for (int j=i+1; j<=n2; j++) for (int l : d2[j-1]) if (l > i)
d4.push_back(d1[l-1] + d1[j-2]);
sort(d4.begin(), d4.end());
d4.erase(unique(d4.begin(), d4.end()), d4.end());
d3.build(d4.size());
for (int j=i+1; j<=n2; j++){
for (int l : d2[j-1]) if (l > i)
d3.up(upp(d1[l-1] + d1[j-2], d4)-1, {1, d1[l-1], d1[j-2]});
node x = d3.que(0, upp(d1[i-1] + d1[j-1], d4));
node y = d3.que(upp(d1[i-1] + d1[j-1], d4), d3.n);
ans2 = min(ans2, x.b - d1[i-1]*x.a + d1[j-1]*y.a - y.c);
}
}
// cout << ans1 << " " << ans2 << "\n";
cout << ans1 + 2*ans2 << "\n";
return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
컴파일 시 표준 에러 (stderr) 메시지
bridge.cpp: In function 'int main()':
bridge.cpp:49:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
49 | if (l > r) swap(l, r); ans1 += r-l;
| ^~
bridge.cpp:49:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
49 | if (l > r) swap(l, r); ans1 += r-l;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |