Submission #465872

#	Time	Username	Problem	Language	Result	Execution time	Memory
465872		bonopo	Sails (IOI07_sails)	C++14	100 / 100	95 ms	2508 KiB

sails

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
ll N, bit[MM]; pair<int,int> m[MM];

void upd(int idx, int v) {
    for(; idx<MM; idx+=idx&-idx) bit[idx]+=v;
}

ll qry(int idx) {
    ll ret=0;
    for(; idx>=1; idx-=idx&-idx) ret+=bit[idx];
    return ret;
}

ll sum(ll n) {
    return (n*(n+1))/2LL;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N;
    for(int i=1; i<=N; ++i) cin>>m[i].f>>m[i].s;
    sort(m+1, m+N+1);

    for(int i=1; i<=N; ++i) {
        int h=m[i].f, k=m[i].s, l=h-k+1, r=h-k+1, lo, hi, mid;
        int lvl=qry(h-k+1);

        lo=1; hi=h-k+1;
        while(lo<=hi) {
            mid=lo+hi>>1;
            if(qry(mid)==lvl) l=mid, hi=mid-1;
            else lo=mid+1;
        }

        lo=h-k+1, hi=h;
        while(lo<=hi) {
            mid=lo+hi>>1;
            if(qry(mid)==lvl) r=mid, lo=mid+1;
            else hi=mid-1;
        }

      //  cout<<l<<" "<<r<<" "<<lvl<<" "<<h<<" "<<k<<el;

        if(l==h-k+1) {
            upd(l, 1);
            upd(h+1, -1);
        } else {
            if(r<h) {
                upd(r+1, 1);
                upd(h+1, -1);
            }

            upd(l, 1);
            upd(l+r-h+k, -1);
        }
    }

    ll ans=0;
    for(int i=1; i<=m[N].f; ++i) {
        int x=qry(i);
       // cout<<x<<" sail "<<i<<el;
        ans+=sum(x-1);
    }

    cout<<ans<<el;
}

// MM

Compilation message (stderr)

sails.cpp: In function 'int32_t main()':
sails.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             mid=lo+hi>>1;
      |                 ~~^~~
sails.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             mid=lo+hi>>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