110342024-06-28 11:02:27BaranJModern Artcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms356 KiB
2Elfogadva2ms356 KiB
subtask25/5
3Elfogadva6ms760 KiB
4Elfogadva8ms748 KiB
5Elfogadva8ms672 KiB
6Elfogadva9ms740 KiB
7Elfogadva10ms740 KiB
8Elfogadva8ms612 KiB
9Elfogadva8ms612 KiB
10Elfogadva3ms632 KiB
subtask315/15
11Elfogadva3ms356 KiB
12Elfogadva3ms256 KiB
13Elfogadva3ms416 KiB
14Elfogadva3ms424 KiB
15Elfogadva3ms376 KiB
16Elfogadva3ms340 KiB
17Elfogadva2ms256 KiB
18Elfogadva2ms256 KiB
19Elfogadva3ms504 KiB
subtask430/30
20Elfogadva3ms504 KiB
21Elfogadva3ms356 KiB
22Elfogadva3ms384 KiB
23Elfogadva4ms500 KiB
24Elfogadva3ms504 KiB
25Elfogadva3ms500 KiB
26Elfogadva3ms356 KiB
27Elfogadva3ms356 KiB
28Elfogadva3ms376 KiB
subtask550/50
29Elfogadva3ms376 KiB
30Elfogadva4ms356 KiB
31Elfogadva4ms520 KiB
32Elfogadva12ms948 KiB
33Elfogadva10ms740 KiB
34Elfogadva7ms632 KiB
35Elfogadva12ms760 KiB
36Elfogadva4ms376 KiB
37Elfogadva14ms740 KiB
38Elfogadva13ms612 KiB
39Elfogadva3ms372 KiB
40Elfogadva13ms1132 KiB
41Elfogadva14ms996 KiB
42Elfogadva14ms1260 KiB
43Elfogadva14ms1124 KiB
44Elfogadva17ms1068 KiB
45Elfogadva16ms1256 KiB