QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624478#4419. Package Deliveryqq0121AC ✓197ms5476kbC++141.3kb2024-10-09 15:56:252024-10-09 15:56:25

Judging History

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

  • [2024-10-09 15:56:25]
  • 评测
  • 测评结果:AC
  • 用时:197ms
  • 内存:5476kb
  • [2024-10-09 15:56:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+10;
const int mod=998244353;
int n,m;
int k;
struct node
{
    int l;
    int r;
}p[N];
bool cmp(node A,node B)
{
    if(A.l==B.l)
    {
        return A.r<B.r;
    }
    return A.l<B.l;
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].l>>p[i].r;
    }
    sort(p+1,p+1+n,cmp);
// cout<<1<<'\n';
    int ans=0;
    priority_queue<int,vector<int>,greater<int> >q;
    int  x=1;
    while(x<=n)
    {
        while(!q.empty()&&q.top()<p[x].l)
        {
            ans++;
            for(int i=1;i<=k;i++)
            {
                if(q.empty())
                {
                    break;
                }q.pop();
            }
        }
        if(x<=n)
        {
            q.push(p[x].r);
            x++;
        }
    }
    while(!q.empty())
    {
        ans++;
        for(int i=1;i<=k;i++)
        {
            
            if(q.empty())
            {
                break;
            }
            q.pop();
        }        
    }
    cout<<ans<<"\n";

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 197ms
memory: 5476kb

input:

2024
100 1
442460151 948559787
257924752 333997853
135225571 423096735
145956270 581316137
150642648 957750064
96771425 543507149
148750856 983838996
440403577 961685342
156399906 910285983
243714738 956235493
326220800 458442515
529302759 988863811
27258022 939870551
104136802 968000285
915165476 9...

output:

100
50
34
25
20
17
15
13
12
11
10
9
10
8
7
7
7
7
6
9
6
7
8
5
7
6
7
5
8
10
9
7
6
8
6
6
8
8
6
11
7
10
7
9
7
9
8
8
9
6
8
6
7
9
8
7
7
10
8
11
6
11
8
8
7
9
8
8
9
7
9
10
7
9
9
8
6
8
8
10
9
7
8
7
9
7
11
7
10
6
9
8
7
8
7
9
8
5
9
9
100
50
34
28
27
24
24
22
26
21
29
27
24
26
25
25
23
22
22
29
24
24
23
26
24
2...

result:

ok 2024 lines