QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #744043 | #9730. Elevator II | Microperson# | WA | 105ms | 7920kb | C++20 | 2.5kb | 2024-11-13 20:40:46 | 2024-11-13 20:40:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1000007;
struct p
{
ll l,r,i;
bool operator<(const p& a)const{
if(a.l==l)return a.r<r;
return a.l>l;
}
};
struct p0
{
ll x,i,f;
};
p0 arr0[N];
p arr[N];
ll flag0[N];
map<ll,ll> m0;
ll cmp0(p0 a,p0 b){
if(a.x==b.x)return a.f<b.f;
return a.x<b.x;
}
multiset<p> s;
multiset<p> ::iterator it;
multiset<p> ::reverse_iterator it2;
void solve( ){
s.clear();
m0.clear();
ll n,now;
cin >> n>> now;
for(ll i=0;i<=n*2;i++)flag0[i]=0;
ll ans=0;
ll len=0;
for(ll i=1;i<=n;i++){
cin >> arr[i].l>>arr[i].r;
arr[i].i=i;
arr0[len].x=arr[i].l,arr0[len].i=i,arr0[len].f=1;
len++;
arr0[len].x=arr[i].r,arr0[len].i=i,arr0[len].f=-1;
len++;
s.insert({arr[i].l,arr[i].r,arr[i].i});
}
ll c=0;
sort(arr0,arr0+len,cmp0);
for(ll i=0;i<len;i++){
c+=arr0[i].f;
m0[arr0[i].x]=c;
}
ll len0=0;
for(auto &it0:m0){
flag0[len0++]=it0.first;
// cout<<it0.first<<'!';
}
ll f=0;
if(m0.find(now)!=m0.end()){
}else{
ll t=upper_bound(flag0,flag0+len0,now)-flag0-1;
if(t==-1){
ans+=flag0[0]-now;
now=flag0[0];
}else if(t==len0-1){
f=1;
}else{
if(m0[now]==0){
ans+=flag0[t+1]-now;
now=flag0[t+1];
}
}
}
vector<ll> ans2;
// for(auto &it0:s){
// cout<<it0.l<<' '<<it0.r<<' '<<it0.i<<'\n';
// }
while(1){
if(f==1)break;
it=s.upper_bound({now,0,0});
// if(it==s.end())cout<<8;
// if(it==s.begin())cout<<7;
// cout<<(*it).l<<'!';
it--;
// cout<<(*it).l<<"?";
ans+=(*it).r-(*it).l;
now=(*it).r;
ans2.push_back((*it).i);
s.erase(it);
if(m0[now]==0){
it=s.upper_bound({now,0,0});
if(it==s.end())break;
ans+=(*it).l-now;
now=(*it).l;
}
}
for(it2=s.rbegin();it2!=s.rend();it2++){
// cout<<(*it2).l<<'!'<<(*it2).r<<'!'<<(*it2).i<<'\n';
ans+=(*it2).r-(*it2).l;
ans2.push_back((*it2).i);
}
cout<<ans<<'\n';
for(ll i=0;i<n;i++){
cout<<ans2[i]<<' ';
}
cout<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll T=1;
cin >> T;
while(T--){
solve();
}
}
/*
1
4 2
3 6
1 3
2 7
5 6
5
4 2
3 6
1 3
2 7
5 6
2 5
2 4
6 8
9 4
3 6
3 4
3 5
7 12
6 15
6 9
11 14
1 5
2 5
2 6
2 3
4 5
2 1
10 12
13 15
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7740kb
input:
2 4 2 3 6 1 3 2 7 5 6 2 5 2 4 6 8
output:
11 3 4 1 2 5 2 1
result:
ok ok 2 cases (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 105ms
memory: 7920kb
input:
6100 19 52 51 98 2 83 40 58 96 99 39 55 72 94 15 17 4 15 48 99 2 99 77 78 35 77 44 62 79 81 30 31 1 48 48 76 68 99 60 66 6 19 44 53 64 92 17 28 67 98 9 99 40 65 16 27 99 100 15 56 4 6 24 97 84 96 47 49 37 38 77 79 13 40 13 92 71 100 47 93 90 91 72 81 15 48 32 71 19 17 95 99 10 23 18 100 90 93 52 92 ...
output:
527 1 4 14 11 6 18 19 17 9 13 3 5 12 15 7 8 2 10 16 203 3 5 4 2 1 6 402 16 11 1 13 5 8 14 6 12 7 4 15 2 9 10 3 733 18 16 4 17 8 1 5 12 10 19 13 14 6 11 3 7 9 15 2 249 11 2 8 12 4 6 14 5 10 1 15 3 9 13 7 437 18 11 10 6 7 2 13 20 4 8 5 15 9 16 14 1 19 3 12 17 109 1 4 3 2 192 5 6 4 8 2 3 1 9 10 ...
result:
wrong answer Participant declares the cost to be 527, but the plan actually costs 524 (test case 1)