Submission #753892

#	Time	Username	Problem	Language	Result	Execution time	Memory
753892		bgnbvnbv	Sails (IOI07_sails)	C++14	100 / 100	208 ms	11804 KiB

sails

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10