QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211764 | #6416. Classical Scheduling Problem | Liberty12619 | TL | 1ms | 9768kb | C++20 | 2.8kb | 2023-10-12 21:01:08 | 2023-10-12 21:01:09 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define PII pair<int,int>
using namespace std;
const int N = 2e5+10;
int A[N],root[N],num,pos;
struct node {
int a,b,id;
}f[N];
struct node1 {
int l,r,cnt,sum,val;
}t[N*20];
bool cmp(node a,node b) {
return a.b<b.b;
}
int n,tim,idx;
vector<int> v;
void build(int &now,int l,int r) {
now=++idx;
t[now].cnt=t[now].sum=t[now].val=0;
if(l==r) return ;
int mid=l+r>>1;
build(t[now].l,l,mid);
build(t[now].r,mid+1,r);
}
void modify(int &now,int pre,int l,int r,int p,int val) {
now=++idx;
t[now]=t[pre];
t[now].cnt++,t[now].sum+=val;
if(l==r) {
t[now].val=val;
return ;
}
int mid=l+r>>1;
if(p<=mid) modify(t[now].l,t[pre].l,l,mid,p,val);
else modify(t[now].r,t[pre].r,mid+1,r,p,val);
}
int query(int now,int pre,int l,int r,int k) {
if(l==r) return t[now].val*k;
int mid=l+r>>1;
int res=t[t[now].l].cnt-t[t[pre].l].cnt;
if(res>=k) return query(t[now].l,t[pre].l,l,mid,k);
else {
return query(t[now].r,t[pre].r,mid+1,r,k-res)+t[t[now].l].sum-t[t[pre].l].sum;
}
}
int getid(int x) {
return lower_bound(A+1,A+num+1,x)-A;
}
bool check(int x) {
int cost=1e18;
for(int i=x;i<=n;i++) {
int k=f[i].b;
if(k<=x) {
int c=query(root[i],root[0],1,num,x);
if(c<cost) {
cost=c;
pos=i;
}
continue;
}
int res1=query(root[i-1],root[0],1,num,x-1);
int res2=query(root[n],root[i],1,num,k-x);
if(res1+res2+f[i].a<cost) {
cost=res1+res2+f[i].a;
pos=i;
}
}
if(cost>tim) return false;
else return true;
}
void solve()
{
cin>>n>>tim;
for(int i=1;i<=n;i++) {
cin>>f[i].a>>f[i].b;
f[i].id=i;
}
sort(f+1,f+n+1,cmp);
for(int i=1;i<=n;i++) A[i]=f[i].a;
sort(A+1,A+n+1);
num=unique(A+1,A+n+1)-A-1;
build(root[0],1,num);
for(int i=1;i<=n;i++) {
int p=getid(f[i].a);
modify(root[i],root[i-1],1,num,p,f[i].a);
}
int ans=0;
int l=1,r=n;
while(l<=r) {
int mid=l+r>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
int pos1=pos;
if(!check(1)) {
cout<<0<<endl<<0<<endl;
return ;
}
pos=pos1;
priority_queue<PII> q;
for(int i=1;i<pos;i++) q.push({-f[i].a,f[i].id});
int cnt=0;
while(cnt<ans-1&&q.size()) {
auto p=q.top();
q.pop();
int x=p.y;
v.push_back(x);
cnt++;
}
v.push_back(f[pos].id);
if(f[pos].b>ans) {
while(q.size()) q.pop();
for(int i=pos+1;i<=n;i++) q.push({-f[i].a,f[i].id});
cnt=0;
while(cnt<f[pos].b-ans) {
auto p=q.top();
q.pop();
int x=p.y;
v.push_back(x);
cnt++;
}
}
cout<<ans<<endl;
cout<<v.size()<<endl;
for(int x:v) cout<<x<<" ";
cout<<endl;
}
signed main()
{
int T = 1;
cin.tie(0)->sync_with_stdio(false);
cin>>T;
while(T--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9768kb
input:
2 4 100 20 1 40 4 60 3 30 3 1 5 10 1
output:
2 3 1 4 2 0 0
result:
ok ok, 2 test cases (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
10000 21 1892 174 13 604 15 170 2 413 11 899 2 531 12 651 17 553 9 429 8 837 14 937 12 577 7 532 11 19 2 173 10 165 6 762 15 221 6 945 13 302 19 7 3 54 26066 812 31 432 24 240 37 171 39 204 47 174 30 569 1 467 5 624 42 734 35 907 3 568 23 802 40 991 32 119 13 187 27 739 42 891 14 550 44 374 16 483 1...
output:
7 8 21 14 16 3 18 12 9 15 53 61 21 14 16 3 18 12 9 15 22 25 37 41 15 27 4 6 48 16 54 29 5 31 3 38 42 43 44 51 35 20 2 8 30 21 52 19 34 12 7 26 9 53 33 36 46 47 10 49 24 17 40 45 39 13 1 32 23 18 50 11 28 12 73 21 14 16 3 18 12 9 15 22 25 37 41 15 27 4 6 48 16 54 29 5 31 3 38 42 43 44 51 35 20 2 8 ...