이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
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;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |