11034 | 2024-06-28 11:02:27 | BaranJ | Modern Art | cpp17 | Accepted 100/100 | 17ms | 1260 KiB |
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
vector<pair<long long, int>> t(2*n);
vector<int> x(n);
for(int i=0; i<n; i++){
cin>>x[i];
}
for(int i=0; i<n; i++){
int r; cin>>r;
t[2*i]={x[i]-r, 2*r};
t[2*i+1]={x[i]+r, -2*r};
}
sort(t.begin(), t.end());
long long unio=0, most=0, previ=0;
map<int, int> m;
m[0]=1;
for(int i=0; i<2*n; i++){
unio+=most*(t[i].first-previ);
//cout<<most<<" "<<t[i].first<<" "<<previ<<" "<<most*(t[i].first-previ)<<endl;
previ=t[i].first;
while(true){
if(t[i].second > 0){m[-t[i].second]++;}
else{
m[t[i].second]--;
if(m[t[i].second]==0){
m.erase(t[i].second);
}
}
if(i >=2*n-1 || t[i].first!=t[i+1].first){break;}
i++;
}
/*for (auto itr = m.begin(); itr != m.end(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}*/
most=-m.begin()->first;
//cout<<most<<" ";
}
cout<<unio;
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 356 KiB | ||||
2 | Accepted | 2ms | 356 KiB | ||||
subtask2 | 5/5 | ||||||
3 | Accepted | 6ms | 760 KiB | ||||
4 | Accepted | 8ms | 748 KiB | ||||
5 | Accepted | 8ms | 672 KiB | ||||
6 | Accepted | 9ms | 740 KiB | ||||
7 | Accepted | 10ms | 740 KiB | ||||
8 | Accepted | 8ms | 612 KiB | ||||
9 | Accepted | 8ms | 612 KiB | ||||
10 | Accepted | 3ms | 632 KiB | ||||
subtask3 | 15/15 | ||||||
11 | Accepted | 3ms | 356 KiB | ||||
12 | Accepted | 3ms | 256 KiB | ||||
13 | Accepted | 3ms | 416 KiB | ||||
14 | Accepted | 3ms | 424 KiB | ||||
15 | Accepted | 3ms | 376 KiB | ||||
16 | Accepted | 3ms | 340 KiB | ||||
17 | Accepted | 2ms | 256 KiB | ||||
18 | Accepted | 2ms | 256 KiB | ||||
19 | Accepted | 3ms | 504 KiB | ||||
subtask4 | 30/30 | ||||||
20 | Accepted | 3ms | 504 KiB | ||||
21 | Accepted | 3ms | 356 KiB | ||||
22 | Accepted | 3ms | 384 KiB | ||||
23 | Accepted | 4ms | 500 KiB | ||||
24 | Accepted | 3ms | 504 KiB | ||||
25 | Accepted | 3ms | 500 KiB | ||||
26 | Accepted | 3ms | 356 KiB | ||||
27 | Accepted | 3ms | 356 KiB | ||||
28 | Accepted | 3ms | 376 KiB | ||||
subtask5 | 50/50 | ||||||
29 | Accepted | 3ms | 376 KiB | ||||
30 | Accepted | 4ms | 356 KiB | ||||
31 | Accepted | 4ms | 520 KiB | ||||
32 | Accepted | 12ms | 948 KiB | ||||
33 | Accepted | 10ms | 740 KiB | ||||
34 | Accepted | 7ms | 632 KiB | ||||
35 | Accepted | 12ms | 760 KiB | ||||
36 | Accepted | 4ms | 376 KiB | ||||
37 | Accepted | 14ms | 740 KiB | ||||
38 | Accepted | 13ms | 612 KiB | ||||
39 | Accepted | 3ms | 372 KiB | ||||
40 | Accepted | 13ms | 1132 KiB | ||||
41 | Accepted | 14ms | 996 KiB | ||||
42 | Accepted | 14ms | 1260 KiB | ||||
43 | Accepted | 14ms | 1124 KiB | ||||
44 | Accepted | 17ms | 1068 KiB | ||||
45 | Accepted | 16ms | 1256 KiB |