oj.uz

Submission #465872

# Submission time Handle Problem Language Result Execution time Memory
465872 2021-08-17T03:49:57 Z bonopo Sails (IOI07_sails) C++14
100 / 100
 95 ms 2508 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 612 KB Output is correct
2 Correct 21 ms 844 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 776 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1080 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1624 KB Output is correct
2 Correct 69 ms 2508 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1740 KB Output is correct
2 Correct 57 ms 2412 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1836 KB Output is correct
2 Correct 71 ms 2372 KB Output is correct