oj.uz

Submission #1105093

# Submission time Handle Problem Language Result Execution time Memory
1105093 2024-10-25T10:40:21 Z Faggi Sails (IOI07_sails) C++11
0 / 100
 67 ms 6728 KB 
#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;    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]});        }    }    while(sum.size()&&res.size())    {        pos=sum.front().first;        sob+=sum.front().second;        sum.pop();        while(res.size()&&res.front().first>pos)            res.pop();        while(res.size()&&sob>0)        {            sob-=res.front().second;            posR=res.front().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){    ll ma, sob, i, res=0ll;    for(i=tam; i>0ll; i--)    {        ma=min(x,tamDP[i]);        sob=0ll;        if(dp[i]>ma)        {            sob=dp[i]-ma;            dp[i]=ma;            dp[i-1ll]+=sob;        }    }    for(i=tam; i>0ll; i--)    {        res+=calcs[dp[i]];    }    return res;}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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 3556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 6080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 6576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 6728 KB Output isn't correct
2 Halted 0 ms 0 KB -