제출 #1314951

#제출 시각아이디문제언어결과실행 시간메모리
1314951exoworldgdSails (IOI07_sails)C++20
100 / 100
54 ms2572 KiB
#pragma GCC optimize("O5,unroll-loops,inline,fast-math") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> #define int long long #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) using namespace std; const int N=1e5+5; int t[N],n,ans=0; pair<int,int> a[N]; void up(int i, int v) {for (; i < N; i += i&-i) t[i] += v;} int q(int i) { int sum=0; for (; i > 0; i -= i&-i) sum += t[i]; return sum; } int get(int x) { int l=0,r=N-1,m; while (l < r) m=(l+r+1)>>1, q(m)>=x ? l=m : r=m-1; return l; } signed main(void) { exoworldgd; cin >> n; for (int i=0 ;i< n; i++) cin >> a[i].first >> a[i].second; sort(a,a+n); for (int i=0,l,r,v;i < n;i ++) v=q(a[i].first-a[i].second+1),l=get(v+1),r=min(get(v),a[i].first), up(r+1,1), up(a[i].first+1,-1), up(l+1,1), up(l+r+a[i].second-a[i].first+1,-1); for (int i=1,v; i < N; i++) v=q(i), ans+=v*(v-1)/2; cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...