QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#411829#4393. Snatch Groceriesmobbb#AC ✓107ms5864kbC++201.4kb2024-05-15 20:18:222024-05-15 20:18:22

Judging History

你现在查看的是最新测评结果

  • [2024-05-15 20:18:22]
  • 评测
  • 测评结果:AC
  • 用时:107ms
  • 内存:5864kb
  • [2024-05-15 20:18:22]
  • 提交

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