QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104328 | #6334. Passport | oscaryang | 0 | 6ms | 15624kb | C++20 | 2.2kb | 2023-05-10 10:15:28 | 2023-05-10 10:15:32 |
Judging History
answer
#include<bits/stdc++.h>
#define vc vector
#define pb push_back
#define pf push_front
#define pof pop_front
#define mkp make_pair
using namespace std;
const int N=1e6+5,inf=1e7;
inline int read() {
int x=0,w=0; char ch=getchar();
while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
return w?-x:x;
}
inline void write(int x) {
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10); putchar(x%10+'0');
}
inline void writee(int x) { write(x); putchar(10); }
int n,q,idx;
int id[N],dist[N],d[N];
int hd[N],to[N<<1],ne[N<<1],e[N<<1],tc=1;
bool vis[N];
inline void add(int x,int y,int z) {
to[++tc]=x; ne[tc]=hd[y]; hd[y]=tc; e[tc]=z;
}
inline void bfs(int s,int *d) {
for(int i=1;i<=idx;i++) d[i]=inf, vis[i]=0;
d[s]=0; deque<int> Q; Q.pb(s); int x;
while(Q.size()) {
x=Q.front(); Q.pof();
if(vis[x]) continue; vis[x]=1;
for(int i=hd[x],y;i;i=ne[i])
if(!vis[y=to[i]] && d[x]+e[i]<d[y]) {
d[y]=d[x]+e[i];
if(e[i]) Q.pb(y);
else Q.pf(y);
}
}
}
inline void dijkstra() {
priority_queue<pair<int,int> > Q;
for(int i=1;i<=idx;i++) Q.push(mkp(-dist[i],i)), vis[i]=0;
int x;
while(Q.size()) {
x=Q.top().second; Q.pop();
if(vis[x]) continue; vis[x]=1;
for(int i=hd[x],y;i;i=ne[i])
if(!vis[y=to[i]] && dist[x]+e[i]<dist[y])
dist[y]=dist[x]+e[i], Q.push(mkp(-dist[y],y));
}
}
#define mid (l+r>>1)
#define ls (k<<1)
#define rs (k<<1|1)
inline void build(int k,int l,int r) {
if(l==r) return idx=max(idx,id[l]=k), void();
add(k,ls,0); add(k,rs,0);
build(ls,l,mid); build(rs,mid+1,r);
}
inline void ins(int k,int l,int r,int L,int R,int x) {
if(L>R || L>r || R<l) return ;
if(L<=l && R>=r) return add(x,k,1);
ins(ls,l,mid,L,R,x); ins(rs,mid+1,r,L,R,x);
}
int main() {
//freopen("ex_4.in","r",stdin);
n=read(); build(1,1,n);
for(int i=1,L,R;i<=n;i++) L=read(), R=read(), ins(1,1,n,L,R,id[i]);
bfs(id[1],d); for(int i=1;i<=idx;i++) dist[i]+=d[i];
bfs(id[n],d); for(int i=1;i<=idx;i++) dist[i]+=d[i];
dijkstra();
q=read(); int x;
while(q--) {
x=read();
if(dist[id[x]]>n) puts("-1");
else writee(dist[id[x]]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 6
Accepted
time: 4ms
memory: 15624kb
input:
2 1 1 1 2 1 1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 0
Accepted
time: 3ms
memory: 9492kb
input:
2 1 2 2 2 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -6
Time Limit Exceeded
input:
196001 1 408 2 37822 1 1221 1 160899 4 62751 3 21706 2 4118 8 70696 8 4916 3 24286 9 443 8 171744 11 170980 7 3541 12 16428 8 71164 1 186827 11 234 2 23141 4 17143 21 9522 10 24 19 15936 3 15884 17 426 14 3188 17 168317 4 1560 25 35 16 39439 21 122 4 17507 8 97645 11 824 25 59856 30 9265 7 151420 37...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 16
Accepted
time: 1ms
memory: 13636kb
input:
2 1 1 1 2 1 2
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 2ms
memory: 13544kb
input:
2 1 2 2 2 1 2
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 2ms
memory: 13572kb
input:
6 1 1 2 2 1 3 3 5 5 6 1 6 1 4
output:
3
result:
ok single line: '3'
Test #11:
score: -16
Wrong Answer
time: 4ms
memory: 11596kb
input:
9 1 1 2 2 3 3 1 4 2 8 5 7 4 9 8 8 9 9 1 6
output:
4
result:
wrong answer 1st lines differ - expected: '3', found: '4'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 24
Accepted
time: 1ms
memory: 11888kb
input:
2337 1 3 2 77 1 1397 2 222 3 62 6 1896 7 10 6 950 9 9 10 16 11 455 9 588 13 16 7 1245 9 1342 8 1727 7 122 11 653 9 1094 2 57 11 81 19 1290 6 1584 16 79 14 215 21 61 27 27 16 1458 16 198 26 180 31 31 11 240 33 36 11 121 34 1542 9 1752 14 456 36 43 36 2244 40 40 4 517 42 662 31 1350 33 162 30 843 28 1...
output:
4
result:
ok single line: '4'
Test #20:
score: -24
Wrong Answer
time: 2ms
memory: 13780kb
input:
2486 1 12 2 8 1 7 3 12 2 11 3 15 1 8 4 11 9 15 3 21 11 13 4 15 9 21 9 19 5 15 8 20 8 25 16 24 11 29 11 23 18 23 14 32 17 24 13 27 15 30 21 34 16 29 20 35 19 32 29 34 20 39 21 43 29 40 28 43 26 44 31 45 28 43 35 38 30 40 37 46 40 43 42 42 42 45 43 54 39 51 40 51 45 54 46 57 39 53 47 53 47 54 41 59 49...
output:
315
result:
wrong answer 1st lines differ - expected: '314', found: '315'
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 8
Accepted
time: 3ms
memory: 11908kb
input:
2419 1 883 1 29 3 41 4 2201 1 808 6 45 7 1456 6 134 6 1372 1 1776 4 441 7 208 5 28 4 604 7 56 9 617 8 2115 15 60 13 456 10 2071 18 23 18 39 5 39 21 35 4 75 25 44 24 640 21 30 4 860 30 31 18 78 32 779 1 927 33 34 19 59 34 181 21 502 23 155 39 39 2 254 30 641 42 50 10 2000 41 2220 18 632 35 48 27 905 ...
output:
3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 4 4 3 4 4 3 4 3 4 4 4 3 5 4 4 3 4 4 4 4 4 -1 3 4 4 3 3 4 4 4 3 3 4 4 3 -1 3 4 4 4 3 -1 4 4 4 3 4 4 4 4 4 4 3 3 4 5 4 3 3 4 4 3 4 4 3 4 3 4 4 -1 -1 3 4 4 3 4 4 3 4 3 4 5 4 4 4 4 3 4 4 4 3 4 5 4 4 4 4 4 3 4 4 4 4 4 4 4 3 4 4 4 -1 4 3 3 3 4 4 4 5 4 4 3 4 4 5 -1 4 4 4 4...
result:
ok 2419 lines
Test #29:
score: -8
Wrong Answer
time: 6ms
memory: 11748kb
input:
2500 1 7 1 6 1 8 1 15 5 14 2 17 5 18 8 17 2 13 3 12 3 14 12 22 4 15 6 18 14 16 8 20 6 22 10 22 12 28 11 28 20 24 12 33 16 29 23 28 20 28 19 35 18 30 24 39 20 33 19 33 30 40 23 32 26 37 28 36 30 45 35 40 36 41 34 44 34 46 29 44 37 50 33 44 39 49 35 54 40 54 39 46 36 50 47 54 44 49 46 61 42 58 41 58 4...
output:
314 314 314 314 315 315 315 315 315 315 315 315 315 315 315 314 314 314 314 314 315 314 315 315 315 314 314 315 314 314 315 315 315 315 314 315 315 315 315 314 314 315 315 314 314 315 314 315 315 314 314 314 314 314 314 314 315 314 314 314 314 314 315 315 315 315 314 315 314 314 314 314 314 314 314 ...
result:
wrong answer 4th lines differ - expected: '313', found: '314'
Subtask #5:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
input:
196830 1 67357 2 183304 3 23390 4 54 1 145887 3 27807 3 12376 1 1013 3 113274 3 191874 6 23342 9 2113 13 94245 3 141449 10 1727 3 51 17 99028 6 193803 8 7452 6 121537 9 23658 18 611 6 4756 4 5141 8 8547 8 66922 13 7021 9 72 3 53043 16 167381 2 15530 5 192 33 33 9 92655 10 36182 20 19992 36 24454 1 6...