Submission #855222

#	Time	Username	Problem	Language	Result	Execution time	Memory
855222		AndiR	Sails (IOI07_sails)	C++11	60 / 100	1054 ms	3048 KiB

sails

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("");
ofstream fout ("");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

ll n, aib[Nmax];

void aib_add(int l, int r, int val){
    while (l<=n){
        aib[l]+=val;
        l+=l&-l;
    }
    r++;
    while (r<=n){
        aib[r]-=val;
        r+=r&-r;
    }
}
ll aib_val(int pos){
    ll s=0;
    while (pos>0){
        s+=aib[pos];
        pos-=pos&-pos;
    }
    return s;
}
int aib_bs2(int val, int h){
    int l=1, r=h, mij, v, sol;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v>=val){
            sol=mij;
            l=mij+1;
        }
        else r=mij-1;
    }
    return sol;
}
int aib_bs1(int val, int h){
    int l=1, r=h, mij, v, sol;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v<=val){
            sol=mij;
            r=mij-1;
        }
        else l=mij+1;
    }
    return sol;
}

struct mat{
    int h, k;
}v[Nmax];

bool cmp(mat a, mat b){
    return a.h<b.h;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for (int i=0; i<n; i++)
        cin>>v[i].h>>v[i].k;
    sort(v, v+n, cmp);
    for (int i=0; i<n; i++){
        ll val=aib_val(v[i].h-v[i].k+1);
        int l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
        int st=v[i].k-(v[i].h-r+1);
        aib_add(r, v[i].h, 1);
        aib_add(l, l+st-1, 1);
    }
    ll sol=0;
    for (int i=1; i<=n; i++)
        sol+=aib_val(i)*(aib_val(i)-1)/2;
    cout<<sol;
    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int aib_bs2(int, int)':
sails.cpp:58:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     return sol;
      |            ^~~
sails.cpp: In function 'int aib_bs1(int, int)':
sails.cpp:71:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     return sol;
      |            ^~~
sails.cpp: In function 'int main()':
sails.cpp:29:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     while (l<=n){
      |            ^
sails.cpp:61:27: note: 'sol' was declared here
   61 |     int l=1, r=h, mij, v, sol;
      |                           ^~~
sails.cpp:93:60: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         int l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
      |                                                            ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 10 / 10