oj.uz

Submission #753892

# Submission time Handle Problem Language Result Execution time Memory
753892 2023-06-06T09:30:50 Z bgnbvnbv Sails (IOI07_sails) C++14
100 / 100
 208 ms 11804 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,c[maxN],st[4*maxN],mn[4*maxN];
ll seg[maxN*4];
ll lazy[4*maxN];
void down(ll id,ll l,ll r)
{
    ll &x=lazy[id];
    ll mid=l+r>>1;
    st[id*2]+=x;
    mn[id*2]+=x;
    lazy[id*2]+=x;
    st[id*2+1]+=x;
    mn[id*2+1]+=x;
    lazy[id*2+1]+=x;
    seg[id*2]+=x*(mid-l+1);
    seg[id*2+1]+=x*(r-mid);
    x=0;
}
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]+=val;
        mn[id]+=val;
        lazy[id]+=val;
        seg[id]+=val*(r-l+1);
        return;
    }
    down(id,l,r);
    ll mid=l+r>>1;
    update(i,j,val,id*2,l,mid);
    update(i,j,val,id*2+1,mid+1,r);
    st[id]=max(st[id*2],st[id*2+1]);
    mn[id]=min(mn[id*2],mn[id*2+1]);
    seg[id]=seg[id*2]+seg[id*2+1];
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return 0;
    if(i<=l&&r<=j) return seg[id];
    down(id,l,r);
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll bs1(ll x,ll val,ll id=1,ll l=1,ll r=n)
{
    if(r<x||st[id]<val) return r+1;
    if(l==r) return l;
    down(id,l,r);
    ll mid=l+r>>1;
    ll pos=bs1(x,val,id*2,l,mid);
    if(pos==mid+1) return bs1(x,val,id*2+1,mid+1,r);
    return pos;
}
ll bs2(ll val,ll id=1,ll l=1,ll r=n)
{
    if(mn[id]>val) return l-1;
    if(l==r) return l;
    down(id,l,r);
    ll mid=l+r>>1;
    ll pos=bs2(val,id*2+1,mid+1,r);
    if(pos==mid) return bs2(val,id*2,l,mid);
    return pos;
}
pli a[maxN];
ll ans=0;
void solve()
{
    cin >> n;
    ll mx=0;
    for(int i=1;i<=n;i++) cin >> a[i].fi >> a[i].se,mx=max(mx,a[i].fi);
    sort(a+1,a+n+1);
    ll cc=n;
    n=mx;
    fill(st,st+4*maxN,0);
    for(int i=1;i<=cc;i++)
    {
        ll x=get(n-(a[i].fi-a[i].se),n-(a[i].fi-a[i].se));
        ll f=bs1(n-a[i].fi+1,x);
        ll s=bs2(x);
        ans+=get(n-a[i].fi+1,n-a[i].fi+a[i].se);
        update(n-a[i].fi+1,f-1,1);
        ll num=a[i].se-((f-1)-(n-a[i].fi+1)+1);
        update(s-num+1,s,1);
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

sails.cpp: In function 'void down(ll, ll, ll)':
sails.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     ll mid=l+r>>1;
      |            ~^~
sails.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
sails.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     ll mid=l+r>>1;
      |            ~^~
sails.cpp: In function 'll get(ll, ll, ll, ll, ll)':
sails.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     ll mid=l+r>>1;
      |            ~^~
sails.cpp: In function 'll bs1(ll, ll, ll, ll, ll)':
sails.cpp:62:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     ll mid=l+r>>1;
      |            ~^~
sails.cpp: In function 'll bs2(ll, ll, ll, ll)':
sails.cpp:72:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3488 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3720 KB Output is correct
2 Correct 8 ms 9556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5156 KB Output is correct
2 Correct 41 ms 4368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5504 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7444 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 10924 KB Output is correct
2 Correct 145 ms 11804 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 11252 KB Output is correct
2 Correct 107 ms 11728 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 11324 KB Output is correct
2 Correct 141 ms 7608 KB Output is correct