QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268837#7744. Elevator2986858916TL 1ms3432kbC++203.5kb2023-11-28 21:58:192023-11-28 21:58:20

Judging History

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

  • [2023-11-28 21:58:20]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3432kb
  • [2023-11-28 21:58:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ll long long
#define lowbit(x) x&-x
const int N=1e7+1,mod=1e9+19;
void solve(){
    int n,k;cin>>n>>k;
    vector<pair<int,int>>a,b;
    map<int,int>one,two;
    for(int i=0;i<n;i++){
        int c,w,f;cin>>c>>w>>f;
        if(w==1){
            one[f]+=c;
        }else two[f]+=c;
        // if(w==1)a.emplace_back(c,f);
        // else b.emplace_back(c,f);
    }
    for(auto &[f,c]:one)a.emplace_back(c,f);
    for(auto &[f,c]:two)b.emplace_back(c,f);
    function<bool(pair<int,int>,pair<int,int>)>cmp=[&](const auto x,const auto y){
        return x.second>y.second;
    };
    sort(a.begin(),a.end(),cmp);
    sort(b.begin(),b.end(),cmp);
    ll ans=0;
    int p=k,cnt=0,ex=0;
    int l=0,li=0;
    while(l<a.size()||li<b.size()){
        if(l<a.size()&&li<b.size()){
            if(a[l].second>b[li].second){
                if(a[l].first<=ex){
                    ex-=a[l].first,a[l].first=0;
                    continue;
                }else a[l].first-=ex,ex=0;
                if(p==k){
                    cnt=a[l].second;
                }
                if(a[l].first>=k){
                    ans+=1ll*a[l].first/k*a[l].second;
                    a[l].first=a[l].first%k;
                }
                if(p>=a[l].first)p-=a[l].first;
                else p=a[l].first-p,ans+=cnt,cnt=a[l].second;
                l++;
            }else {
                if(p==k){
                    cnt=b[li].second;
                }
                if(p==1){
                    ans+=cnt;
                    p=k;
                    ex++;
                    continue;
                }
                if(b[li].first>=k/2){
                    ans+=1l*b[li].first/(k/2)*b[li].second;
                    b[li].first=b[li].first%(k/2);
                }
                if(p>=b[li].first*2)p-=b[li].first*2;
                else{
                    if(p&1)ex++;
                    p=b[li].first*2-p,ans+=cnt;
                    if(p!=k)cnt=b[li].second;
                }li++;
            }
        }else if(l<a.size()){
                if(a[l].first<=ex){
                    ex-=a[l].first,a[l].first=0;
                    continue;
                }else a[l].first-=ex,ex=0;
                if(p==k){
                    cnt=a[l].second;
                }
                if(a[l].first>=k){
                    ans+=1ll*a[l].first/k*a[l].second;
                    a[l].first=a[l].first%k;
                }
                if(p>=a[l].first)p-=a[l].first;
                else p=a[l].first-p,ans+=cnt,cnt=a[l].second;
                l++;
        }else {
                if(p==k){
                    cnt=b[li].second;
                }
                if(p==1){
                    ans+=cnt;
                    p=k;
                    ex++;
                    continue;
                }
                if(b[li].first>=k/2){
                    ans+=1ll*b[li].first/(k/2)*b[li].second;
                    b[li].first=b[li].first%(k/2);
                }
                if(p>=b[li].first*2)p-=b[li].first*2;
                else {
                    if(p&1)ex++;
                    p=b[li].first*2-p,ans+=cnt,cnt=b[li].second;
                }
                li++;
        }
        if(p==0){
            p=k;ans+=cnt;
        }
    }
    if(p!=k)ans+=cnt;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3432kb

input:

2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345

output:

24
100000

result:

ok 2 lines

Test #2:

score: -100
Time Limit Exceeded

input:

5501
8 104
5 2 3
6 2 4
5 2 3
6 2 9
8 2 4
2 1 3
7 2 4
8 2 8
1 290
3 1 1
12 12
6 1 2
1 2 2
1 1 2
1 2 4
6 1 1
1 2 5
6 1 4
4 1 4
6 2 4
6 2 5
4 2 5
4 1 4
5 334
1 1 4
1 2 3
4 2 1
5 1 1
2 1 2
13 218
5 2 3
5 1 4
1 2 1
1 2 5
3 2 2
1 1 3
4 2 2
1 2 5
2 2 1
2 1 5
3 2 1
5 2 1
1 1 4
10 260
7 2 1
5 1 1
5 2 4
6 1 6...

output:


result: