110342024-06-28 11:02:27BaranJModern Artcpp17Accepted 100/10017ms1260 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms356 KiB
2Accepted2ms356 KiB
subtask25/5
3Accepted6ms760 KiB
4Accepted8ms748 KiB
5Accepted8ms672 KiB
6Accepted9ms740 KiB
7Accepted10ms740 KiB
8Accepted8ms612 KiB
9Accepted8ms612 KiB
10Accepted3ms632 KiB
subtask315/15
11Accepted3ms356 KiB
12Accepted3ms256 KiB
13Accepted3ms416 KiB
14Accepted3ms424 KiB
15Accepted3ms376 KiB
16Accepted3ms340 KiB
17Accepted2ms256 KiB
18Accepted2ms256 KiB
19Accepted3ms504 KiB
subtask430/30
20Accepted3ms504 KiB
21Accepted3ms356 KiB
22Accepted3ms384 KiB
23Accepted4ms500 KiB
24Accepted3ms504 KiB
25Accepted3ms500 KiB
26Accepted3ms356 KiB
27Accepted3ms356 KiB
28Accepted3ms376 KiB
subtask550/50
29Accepted3ms376 KiB
30Accepted4ms356 KiB
31Accepted4ms520 KiB
32Accepted12ms948 KiB
33Accepted10ms740 KiB
34Accepted7ms632 KiB
35Accepted12ms760 KiB
36Accepted4ms376 KiB
37Accepted14ms740 KiB
38Accepted13ms612 KiB
39Accepted3ms372 KiB
40Accepted13ms1132 KiB
41Accepted14ms996 KiB
42Accepted14ms1260 KiB
43Accepted14ms1124 KiB
44Accepted17ms1068 KiB
45Accepted16ms1256 KiB