Submission #971205

#	Time	Username	Problem	Language	Result	Execution time	Memory
971205		12345678	Sails (IOI07_sails)	C++17	100 / 100	511 ms	7320 KiB

sails

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll res, n;
vector<pair<ll, ll>> h(nx);

struct segtree
{
    ll d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        int md=(l+r)/2;
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
    }
    ll query(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (l==r) return d[i];
        int md=(l+r)/2;
        if (idx<=md) return query(l, md, 2*i, idx);
        return query(md+1, r, 2*i+1, idx);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>h[i].first>>h[i].second;
    sort(h.begin()+1, h.begin()+n+1);
    for (int i=1; i<=n; i++)
    {
        int st=h[i].first-h[i].second+1;
        s.update(1, nx-1, 1, st, h[i].first, 1);
        if (st==1||s.query(1, nx-1, 1, st)<=s.query(1, nx-1, 1, st-1)) continue;
        int l=st, r=h[i].first;
        while (l<r)
        {
            int md=(l+r+1)/2;
            if (s.query(1, nx-1, 1, md)==s.query(1, nx-1, 1, st)) l=md;
            else r=md-1;
        }
        s.update(1, nx-1, 1, st, l, -1);
        int sz=l-st+1;
        l=1, r=st-1;
        while (l<r)
        {
            int md=(l+r)/2;
            if (s.query(1, nx-1, 1, md)==s.query(1, nx-1, 1, st-1)) r=md;
            else l=md+1;
        }
        s.update(1, nx-1, 1, l, l+sz-1, 1);
    }
    for (int i=1; i<nx; i++) res+=(s.query(1, nx-1, 1, i)*(s.query(1, nx-1, 1, i)-1))/2;
    cout<<res;
}

Compilation message (stderr)

sails.cpp: In member function 'void segtree::pushlz(int, int, int)':
sails.cpp:18:13: warning: unused variable 'md' [-Wunused-variable]
   18 |         int md=(l+r)/2;
      |             ^~

• 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