QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#411829 | #4393. Snatch Groceries | mobbb# | AC ✓ | 107ms | 5864kb | C++20 | 1.4kb | 2024-05-15 20:18:22 | 2024-05-15 20:18:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template<class T>
struct Fenwick{
vector<T> c;
int n;
Fenwick(int _n){
n = _n;
c.resize(n + 1);
}
T sum(int x){
T res = 0;
for (; x ; x -= x & (-x)){
res += c[x];
}
return res;
}
void add(int x,T d){
for (;x <= n;x += x & (-x)){
c[x] += d;
}
}
T rangesum(int l,int r){
return sum(r) - sum(l - 1);
}
};
void solve(){
int n;
cin >> n;
vector<pair<int,int>> seg(n);
vector<int> vx;
for (auto &[l,r] : seg){
cin >> l >> r;
vx.push_back(l);
vx.push_back(r);
}
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
int m = vx.size();
Fenwick<int> f(m + 3);
for (auto &[l,r] : seg){
l = lower_bound(vx.begin(),vx.end(),l) - vx.begin() + 1;
f.add(l,1);
r = lower_bound(vx.begin(),vx.end(),r) - vx.begin() + 1;
f.add(r,1);
}
int ans = 0;
sort(seg.begin(),seg.end());
for (auto [l,r] : seg){
if (f.rangesum(l,r) == r - l + 1) ans++;
else
break;
}
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 107ms
memory: 5864kb
input:
5 3 1 2 3 4 5 6 3 1 2 3 4 4 5 100000 263324740 263324748 920719069 920719077 82595123 82595132 765796214 765796222 621714954 621714959 77799324 77799332 278166427 278166428 375391536 375391545 856576804 856576812 512542774 512542781 829984452 829984457 302442403 302442404 779239984 779239986 1189173...
output:
3 1 275 5575 10000
result:
ok 5 lines