#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Lin{
int s, e;
bool operator<(const Lin &oth) const {
return s + e < oth.s + oth.e;
}
};
const ll inf = 1e18;
int k, n;
vector<int> v;
vector<ll> w;
vector<Lin> u;
ll ans, cans, lans, bs;
void t1(){
scanf("%d", &n);
for(int i = 1, x, y; i <= n; i++){
char a[3], b[3];
scanf("%s%d%s%d", a, &x, b, &y);
if(a[0] == b[0]) ans += abs(x - y);
else{
v.push_back(x);
v.push_back(y);
ans++;
}
}
sort(v.begin(), v.end());
for(auto &i : v) ans += abs(i - v[v.size() / 2]);
printf("%lld\n", ans);
}
const int sz = 200010;
struct BIT{
ll dat[sz + 1];
void upd(int x, ll v){ for(x++; x <= sz; x += x & -x) dat[x] += v; }
ll get(int x){ ll ret = 0; for(x++; x; x -= x & -x) ret += dat[x]; return ret; }
ll get(int s, int e){ return get(e) - get(s - 1); }
} B[2][3];
void upd(int i, int j, int x){
B[j][0].upd(i, x);
B[j][1].upd(i, -x * v[i]);
B[j][2].upd(i, x * v[i]);
}
ll cal(int i, int j){
return B[0][1].get(0, i) + B[0][0].get(0, i) * v[i] +
B[0][2].get(i + 1, sz - 1) - B[0][0].get(i + 1, sz - 1) * v[i] +
B[1][1].get(0, j) + B[1][0].get(0, j) * v[j] +
B[1][2].get(j + 1, sz - 1) - B[1][0].get(j + 1, sz - 1) * v[j];
}
void t2(){
scanf("%d", &n);
for(int i = 1, x, y; i <= n; i++){
char a[3], b[3];
scanf("%s%d%s%d", a, &x, b, &y);
if(a[0] == b[0]) bs += abs(x - y);
else{
v.push_back(x);
v.push_back(y);
u.push_back({x, y});
bs++;
}
}
sort(v.begin(), v.end());
sort(u.begin(), u.end());
for(auto &i : u){
i.s = (int)(lower_bound(v.begin(), v.end(), i.s) - v.begin());
i.e = (int)(lower_bound(v.begin(), v.end(), i.e) - v.begin());
//printf("%d - %d\n", i.s, i.e);
upd(i.s, 1, 1); upd(i.e, 1, 1);
}
//puts("---");
int i = 0, j = 0, k = 0;
ans = lans = inf; cans = cal(i, j);
for(; i + 1 < v.size(); i++){
j = max(i, j);
while(k < u.size() && v[u[k].s] + v[u[k].e] < v[i] + v[j]){
//printf("upd %d\n", k);
upd(u[k].s, 1, -1); upd(u[k].e, 1, -1);
upd(u[k].s, 0, 1); upd(u[k].e, 0, 1);
k++;
}
cans = cal(i, j);
//printf("/// %d - %d : %lld\n", i, j, cans);
ans = min(ans, cans);
do{
lans = cans;
j++;
if(j >= v.size()) break;
while(k < u.size() && v[u[k].s] + v[u[k].e] < v[i] + v[j]){
//printf("upd %d\n", k);
upd(u[k].s, 1, -1); upd(u[k].e, 1, -1);
upd(u[k].s, 0, 1); upd(u[k].e, 0, 1);
k++;
}
cans = cal(i, j);
ans = min(ans, cans);
//printf("/// %d - %d : %lld\n", i, j, cans);
}while(j + 1 < v.size() && lans >= cans);
j--;
}
printf("%lld\n", ans + bs);
}
int main(){
scanf("%d", &k);
if(k == 1) t1();
else t2();
}
Compilation message
bridge.cpp: In function 'void t2()':
bridge.cpp:81:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i + 1 < v.size(); i++){
^
bridge.cpp:83:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(k < u.size() && v[u[k].s] + v[u[k].e] < v[i] + v[j]){
^
bridge.cpp:95:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j >= v.size()) break;
^
bridge.cpp:96:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(k < u.size() && v[u[k].s] + v[u[k].e] < v[i] + v[j]){
^
bridge.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
}while(j + 1 < v.size() && lans >= cans);
^
bridge.cpp: In function 'void t1()':
bridge.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
bridge.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d%s%d", a, &x, b, &y);
^
bridge.cpp: In function 'void t2()':
bridge.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
bridge.cpp:61:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d%s%d", a, &x, b, &y);
^
bridge.cpp: In function 'int main()':
bridge.cpp:112:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 4 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 6 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 7 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 8 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 9 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 11 |
Correct |
0 ms |
11404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 4 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 6 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 7 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 8 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 9 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 11 |
Correct |
0 ms |
11404 KB |
Output is correct |
| 12 |
Correct |
23 ms |
13024 KB |
Output is correct |
| 13 |
Correct |
73 ms |
13024 KB |
Output is correct |
| 14 |
Correct |
43 ms |
13024 KB |
Output is correct |
| 15 |
Correct |
29 ms |
12256 KB |
Output is correct |
| 16 |
Correct |
43 ms |
13024 KB |
Output is correct |
| 17 |
Correct |
56 ms |
13024 KB |
Output is correct |
| 18 |
Correct |
59 ms |
13024 KB |
Output is correct |
| 19 |
Correct |
73 ms |
13024 KB |
Output is correct |
| 20 |
Correct |
43 ms |
13024 KB |
Output is correct |
| 21 |
Correct |
66 ms |
13024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
11404 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
11404 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
11404 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
