oj.uz

Submission #465869

# Submission time Handle Problem Language Result Execution time Memory
465869 2021-08-17T03:46:12 Z bonopo Sails (IOI07_sails) C++14
0 / 100
 116 ms 4224 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;
int N, bit[MM]; pair<int,int> m[MM];

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

int qry(int idx) {
    int 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, r, 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(r+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;
      |                 ~~^~~
sails.cpp:66:18: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |             upd(l+r-h+k, -1);
      |                 ~^~
sails.cpp:66:18: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1476 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 2224 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 3800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 4048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 4224 KB Output isn't correct
2 Halted 0 ms 0 KB -