oj.uz

답안 #855223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855223 2023-09-30T21:12:29 Z AndiR Sails (IOI07_sails) C++11
60 / 100
 1000 ms 2688 KB 
#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(ll l, ll r, ll val){
    while (l<=n){
        aib[l]+=val;
        l+=l&-l;
    }
    r++;
    while (r<=n){
        aib[r]-=val;
        r+=r&-r;
    }
}
ll aib_val(ll pos){
    ll s=0;
    while (pos>0){
        s+=aib[pos];
        pos-=pos&-pos;
    }
    return s;
}
ll aib_bs2(ll val, ll h){
    ll 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;
}
ll aib_bs1(ll val, ll h){
    ll 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{
    ll 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 (ll i=0; i<n; i++)
        cin>>v[i].h>>v[i].k;
    sort(v, v+n, cmp);
    for (ll i=0; i<n; i++){
        ll val=aib_val(v[i].h-v[i].k+1);
        ll l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
        ll 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 (ll i=1; i<=n; i++)
        sol+=aib_val(i)*(aib_val(i)-1)/2;
    cout<<sol;
    return 0;
}

Compilation message

sails.cpp: In function 'll aib_bs2(ll, ll)':
sails.cpp:58:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     return sol;
      |            ^~~
sails.cpp: In function 'll aib_bs1(ll, ll)':
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:96:21: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |         aib_add(l, l+st-1, 1);
      |                    ~^~~
sails.cpp:93:59: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         ll l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
      |                                                           ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1030 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2648 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2648 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1043 ms 2648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 2680 KB Output is correct
2 Correct 39 ms 2652 KB Output is correct