Submission #1105121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105121		Faggi	Sails (IOI07_sails)	C++11	25 / 100	225 ms	9516 KiB

sails

#include <bits/stdc++.h>
#define ll long long
using namespace std;vector<ll>tamDP;vector<ll>calcs;ll tam;bool can(vector<ll> dp,ll x){    ll ma, sob=0, i,pos,posR;    priority_queue<pair<ll,ll>>sum,res;    for(i=tam; i>0ll; i--)    {        ma=min(x,tamDP[i]);        if(dp[i]>ma)        {            sob=dp[i]-ma;            dp[i]=ma;            if(i>1ll)                sum.push({i,sob});            else                return 0;        }        else        {            res.push({i,ma-dp[i]});        }    }    sob=0;    while(sum.size()&&res.size())    {        pos=sum.top().first;        sob+=sum.top().second;        sum.pop();        while(res.size()&&res.top().first>pos)            res.pop();        while(res.size()&&sob>0)        {            sob-=res.top().second;            posR=res.top().first;            res.pop();        }        if(sob>0)            return 0;        else        {            res.push({posR,abs(sob)});            sob=0;        }    }    if(sum.size()||sob>0)        return 0;    return 1;}ll calc(vector<ll> dp, ll x){    priority_queue<pair<ll,ll>>pq;    ll rest, a, b, i;    for(i=tam; i>0; i--)    {        if(dp[i]<min(x,tamDP[i]))        {            pq.push({i,min(x,tamDP[i])-dp[i]});        }    }    for(i=tam; i>0; i--)    {        while(pq.size()&&pq.top().first>i)            pq.pop();        if(dp[i]>min(x,tamDP[i]))        {            while(dp[i]>min(x,tamDP[i]))            {                rest=min(dp[i]-min(x,tamDP[i]),pq.top().second);                dp[i]-=rest;                dp[pq.top().first]+=rest;                if(pq.top().second-rest>0)                {                    a=pq.top().first;                    b=pq.top().second-rest;                    pq.pop();                    pq.push({a,b});                }                else                {                    pq.pop();                }            }        }    }    ll ret=0;    for(i=tam; i>0; i--)    {        ret+=calcs[dp[i]];    }    return ret;}int main(){    ll n, i, mi=0ll, ma=0ll, piv,pos;    cin >> n;    calcs.resize(n+1ll);    calcs[0ll]=0ll;    calcs[1ll]=0ll;    for(i=2ll; i<=n; i++)    {        calcs[i]+=calcs[i-1ll]+(i-1ll);    }    vector<pair<ll,ll>>v(n);    for(i=0ll; i<n; i++)    {        cin >> v[i].first >> v[i].second;        tam=max(v[i].first,tam);    }    vector<ll> dp(tam+1,0ll);    tamDP.resize(tam+1,0ll);    for(i=0ll; i<n; i++)    {        dp[v[i].first]+=1ll;        dp[v[i].first-v[i].second]-=1ll;        tamDP[v[i].first]+=1ll;    }    ma=dp[tam];    for(i=tam-1ll; i>=0ll; i--)    {        dp[i]+=dp[i+1ll];        ma=max(ma,dp[i]);        tamDP[i]+=tamDP[i+1ll];    }    pos=ma;    while(mi<=ma)    {        piv=(mi+ma)/2ll;        if(can(dp,piv))        {            ma=piv-1ll;            pos=piv;        }        else        {            mi=piv+1ll;        }    }    cout << calc(dp,pos) << endl;    return 0;}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10