oj.uz

Submission #971205

# Submission time Handle Problem Language Result Execution time Memory
971205 2024-04-28T06:38:06 Z 12345678 Sails (IOI07_sails) C++17
100 / 100
 511 ms 7320 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5984 KB Output is correct
2 Correct 23 ms 5972 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6128 KB Output is correct
2 Correct 16 ms 5980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5980 KB Output is correct
2 Correct 16 ms 5976 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5980 KB Output is correct
2 Correct 19 ms 6072 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5904 KB Output is correct
2 Correct 27 ms 6160 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5972 KB Output is correct
2 Correct 121 ms 6324 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 6432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 6484 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 6992 KB Output is correct
2 Correct 365 ms 6840 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 6996 KB Output is correct
2 Correct 204 ms 6684 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 7320 KB Output is correct
2 Correct 334 ms 7156 KB Output is correct