Submission #1127086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127086		kingmessi	Potatoes and fertilizers (LMIO19_bulves)	C++20	100 / 100	200 ms	33952 KiB

bulves

// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x) 
#define btz(x) __builtin_ctz(x)
using namespace std;

using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
  
int power( int N, int M){
    int power = N, sum = 1;
    if(N == 0) sum = 0;
    while(M > 0){if((M & 1) == 1){sum *= power;}
    power = power * power;M = M >> 1;}
    return sum;
}

const int MAXN = 100005;
int Z = 1;
int ls, rs, lv, zp;
map<int, int> MP;

void fix_left(ll s) {
    if (ls >= s) return;
    auto it = MP.begin();
    while (ls + it->second <= s) {
        ls += it->second;
        lv += ls * (next(it)->first - it->first);
        MP.erase(it++);
    }
    it->second -= s - ls;
    ls = s;
}

void fix_right(ll s) {
    if (rs <= s) return;
    auto it = --MP.end();
    while (rs - it->second >= s) {
        rs -= it->second;
        MP.erase(it--);
    }
    it->second += s - rs;
    rs = s;
}

void advance() {
    ll lo = MP.begin()->first;
    if (zp < lo) lv += ls * (zp - lo);
    else lv += Z * (zp - lo);
    ls -= Z, rs += Z;
    MP[zp] += 2 * Z;
}
 
void solve()
{
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    vi d(n);
    int off = 0;
    repin{
        cin >> a[i] >> b[i];
        d[i] = a[i]-b[i];
        if(i)d[i] += d[i-1];
    }
    repin{
        if(d[i] < 0)off -= d[i],d[i] = 0;
    }
    ls = -1;
    rs = 1;
    MP[d[0]] = 2;
    rep(i,1,n){
        zp = d[i];
        fix_left(-i);
        fix_right(0);
        advance();
    }
    int fin = lv, s = ls;
    for (auto it = MP.begin(); it->first < zp; it++) {
        s += it->second;
        fin += s * (min(next(it)->first,d.back()) - it->first);
    }
    cout << fin+off << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
        solve();
    return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36