QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22723 | #2365. Flight Collision | 1145141919810# | AC ✓ | 154ms | 31268kb | C++20 | 3.7kb | 2022-03-10 15:43:41 | 2022-04-30 01:34:53 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#include<set>
#include<cmath>
#include<ctime>
#include<random>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define bc(x) __builtin_popcount(x)
#define re register
#define il inline
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n';
// #pragma GCC optimize(3)
#define int long long
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace IO_BUFF{
mt19937 rnd(time(0)^(ll)(new char));
int rend(int x){
return rnd()%x+1;
}
void rendom_shuffle(int *a,int len){
shuffle(a+1,a+len+1,rnd);
}
const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
inline int gc(){
if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);
return (HD==TL)?EOF:*HD++;
}
inline int inn(){
int x,ch,s=1;while((ch=gc())<'0'||ch>'9')if(ch=='-')s=-1;x=ch^'0';
while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');return x*s;
}
char ssss[19999999],tttt[20];int ssl,ttl;
inline int print(int x)
{
if(x<0)ssss[++ssl]='-',x=(-x);
if(!x) ssss[++ssl]='0';for(ttl=0;x;x/=10) tttt[++ttl]=char(x%10+'0');
for(;ttl;ttl--) ssss[++ssl]=tttt[ttl];return ssss[++ssl]='\n';
}
inline int Flush(){return fwrite(ssss+1,sizeof(char),ssl,stdout),ssl=0,0;}
int read(){
char c=getchar();int x=1;int s=0;
while(c<'0' || c>'9'){if(c=='-')x=-1;c=getchar();}
while(c>='0' && c<='9'){
s=s*10+c-'0';c=getchar();
}
return s*x;
}
}using namespace IO_BUFF;
/*namespace CFConTest{
const int mod=998244353;
inline int add(const int &x,const int &y){
return (x+y>=mod?x+y-mod:x+y);
}
inline int del(const int &x,const int &y){
return (x-y<0?x-y+mod:x-y);
}
int ksm(int x,int k){
int base=1;
while(k){
if(k&1)base=1ll*base*x%mod;
k>>=1;
x=1ll*x*x%mod;
}
return base;
}
};
using namespace CFConTest;*/
const int N=5e5+5;
int n,x[N],d[N];
int st[N],top;
int pre[N],suf[N];
int vis[N];
struct node{
int u,v;
long double val;
friend bool operator < (node x,node y){
if(x.val!=y.val)return x.val<y.val;
else if(x.u!=y.u)return x.u<y.u;
else return x.v<y.v;
}
};
multiset<node>s;
set<int>nmb;
void del(int u){
int ss=suf[u];
int pp=pre[u];
pre[ss]=pp;
suf[pp]=ss;
vis[u]=1;
}
void add(int u,int v){
if(d[u]<=d[v])return ;
s.insert({u,v,(long double)1.0*(x[u]-x[v])/(d[v]-d[u])});
}
signed main(){
#ifdef newbiewzs
double startt=clock();
freopen("data.in","r",stdin);
#else
#endif
n=read();
for(int i=1;i<=n;i++){
x[i]=read();d[i]=read();
pre[i]=i-1;
if(i!=n)suf[i]=i+1;
nmb.insert(i);
}
for(int i=1;i<n;i++){
add(i,i+1);
}
while(s.size()){
node u=*(s.begin());
s.erase(u);
if(vis[u.u] || vis[u.v] || !u.u || !u.v)continue;
nmb.erase(u.u);
nmb.erase(u.v);
del(u.u);
del(u.v);
auto it=nmb.lower_bound(u.u);
if(it==nmb.end() || it==nmb.begin()) continue;
auto iv=it;iv--;
int pre=*(iv);
int nxt=*nmb.lower_bound(u.v);
add(pre,nxt);
}
for(int i=1;i<=n;i++){
if(!vis[i])st[++top]=i;
}
cout<<top<<'\n';
for(int i=1;i<=top;i++){
cout<<st[i]<<" ";
}
#ifdef newbiewzs
double endd=clock();
cerr<<'\n';
cerr<<"Time:"<<endd-startt<<" ms"<<'\n';
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 13820kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 15956kb
input:
5 1 1000000000 2 1000000000 3 -1000000000 4 -1000000000 5 -1000000000
output:
1 5
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 15960kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
1 3
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 15836kb
input:
2 5 4 10 5
output:
2 1 2
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 15956kb
input:
9 10 10 20 7 30 5 40 0 42 0 50 -1 60 -2 70 -10 80 -12
output:
1 1
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 15904kb
input:
5 10 0 20 0 30 1 40 0 50 0
output:
3 1 2 5
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 34ms
memory: 20500kb
input:
98765 0 -48539 1 -48539 2 -48539 3 -48539 4 -48539 5 -48539 6 -48539 7 -48539 8 -48539 9 -48539 10 -48539 11 -48539 12 -48539 13 -48539 14 -48539 15 -48539 16 -48539 17 -48539 18 -48539 19 -48539 20 -48539 21 -48539 22 -48539 23 -48539 24 -48539 25 -48539 26 -48539 27 -48539 28 -48539 29 -48539 30 -...
output:
98765 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 60ms
memory: 25272kb
input:
99999 -999999396 999999395 -999971669 999999396 -999971668 -999999396 -999961260 999999396 -999961259 -999999396 -999907239 999999396 -999907238 -999999396 -999754561 999999396 -999754560 -999999396 -999662011 999999396 -999662010 -999999396 -999651505 999999396 -999651504 -999999396 -999619141 9999...
output:
1 99999
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 59ms
memory: 29076kb
input:
99999 -999999244 999999243 -999956299 999999244 -999956298 -999999244 -999945616 999999244 -999945615 -999999244 -999944410 999999244 -999944409 -999999244 -999891030 999999244 -999891029 -999999244 -999862261 999999244 -999862260 -999999244 -999835376 999999244 -999835375 -999999244 -999705681 9999...
output:
1 1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 75ms
memory: 31008kb
input:
99999 -999999634 999999633 -999951510 999999634 -999951509 -999999634 -999895803 999999634 -999895802 -999999634 -999883648 999999634 -999883647 -999999634 -999880002 999999634 -999880001 -999999634 -999879250 999999634 -999879249 -999999634 -999758480 999999634 -999758479 -999999634 -999583344 9999...
output:
1 1
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 84ms
memory: 29860kb
input:
100000 0 0 1 -499999669 2 -999999337 1000 999998221 1001 499999611 1002 1000 2000 2000 2001 -499998575 2002 -999999149 3000 999999419 3001 500001210 3002 3000 4000 4000 4001 -499997324 4002 -999998647 5000 5000 6000 999998787 6001 500002394 6002 6000 7000 7000 8000 8000 9000 9000 9001 -249992975 900...
output:
5702 3 16 21 46 47 76 77 78 79 102 103 118 123 124 151 152 153 174 189 194 243 266 267 298 299 304 309 310 319 324 325 326 351 396 397 506 507 542 551 556 571 572 629 638 649 650 665 764 807 832 837 876 921 938 959 976 977 978 1167 1220 1221 1228 1237 1238 1273 1280 1285 1290 1291 1292 1293 1370 137...
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 34ms
memory: 27480kb
input:
99999 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1...
output:
1 1
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 37ms
memory: 23344kb
input:
100000 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 ...
output:
2 1 2
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 3ms
memory: 16020kb
input:
2 -1000000000 1000000000 1000000000 1000000000
output:
2 1 2
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 15836kb
input:
2 -1000000000 999999999 1000000000 1000000000
output:
2 1 2
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 6ms
memory: 15948kb
input:
2 -1000000000 1000000000 1000000000 999999999
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 3ms
memory: 15892kb
input:
2 -1000000000 999999999 1000000000 999999999
output:
2 1 2
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 3ms
memory: 15760kb
input:
10 -8 1 -4 1 -3 3 -2 -9 2 -3 4 1 5 1 6 4 8 4 10 3
output:
4 1 6 7 8
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 154ms
memory: 27244kb
input:
100000 -999990163 -377895309 -999984163 8973261 -999979867 834504530 -999953994 761228981 -999936881 -463878169 -999916723 -15264200 -999907073 -174466667 -999877240 -726147638 -999876260 947109625 -999846455 -153928844 -999842048 -820363438 -999816282 549455586 -999814709 990129 -999808106 -5103181...
output:
8 1 2448 60523 62076 62079 74424 99893 99998
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 136ms
memory: 27372kb
input:
100000 -999999527 -897350344 -999982057 -849659915 -999973845 -76432407 -999947168 295353679 -999944429 -291836812 -999943207 -113638209 -999929091 277369081 -999923482 -341494644 -999901773 -413159641 -999886430 386321890 -999873068 -832012113 -999863798 296432997 -999856998 -228698165 -999794684 -...
output:
6 1 2 62119 89002 99727 99998
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 143ms
memory: 29084kb
input:
100000 -999970270 -507664063 -999953025 -779973700 -999951134 768353813 -999942782 256251065 -999923116 -331605753 -999915433 -78154988 -999907734 631563655 -999907262 -335053550 -999901832 -846942814 -999899573 -790177737 -999889186 838524268 -999873298 -730637168 -999870040 677208179 -999858626 95...
output:
6 72943 83560 99261 99330 99951 99952
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 150ms
memory: 27372kb
input:
100000 -999999663 606420568 -999977713 -465238391 -999972974 -470545763 -999922236 587581803 -999917815 -352443486 -999910614 -151519504 -999903937 230521617 -999880664 473948012 -999879036 533852278 -999846934 -277893200 -999844515 -825287819 -999838091 -647654324 -999824249 545274926 -999805576 -7...
output:
4 3 120 1729 12556
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 3ms
memory: 15960kb
input:
2 3 -8 4 10
output:
2 1 2
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 2ms
memory: 15868kb
input:
2 -57 23 91 11
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 3ms
memory: 15876kb
input:
10 -926 345 -872 -566 -680 465 -348 -50 -71 -500 16 939 402 -386 592 -709 617 -515 713 -824
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 0ms
memory: 15956kb
input:
23 -9789 6740 -9087 7154 -8243 3939 -6908 9254 -6829 -426 -6367 1462 -3319 -2522 -2438 4232 -1161 -2195 -305 3393 2357 -9935 2571 -2348 3537 6328 4256 6094 7195 -2556 7315 6805 7359 -355 8361 9027 8532 -4742 8792 7705 9083 2738 9142 -9725 9242 6364
output:
3 7 12 13
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 0ms
memory: 15964kb
input:
223 -210 92 -208 -103 -205 153 -204 110 -203 165 -197 -147 -196 -70 -195 -93 -194 61 -193 -158 -192 54 -188 -108 -187 -14 -186 -128 -185 -86 -183 -157 -182 146 -178 183 -177 62 -170 135 -166 56 -162 63 -161 180 -160 -37 -159 210 -158 -140 -157 166 -156 12 -155 204 -152 30 -148 -147 -146 113 -141 6 -...
output:
3 189 194 197
result:
ok 2 lines
Test #28:
score: 0
Accepted
time: 3ms
memory: 15964kb
input:
1002 -100179 -21171 -99945 41039 -99874 55638 -99733 71524 -99523 67610 -99143 -35927 -98730 27793 -98540 85922 -98521 35885 -98492 44007 -98361 49124 -97803 -94904 -97591 -83195 -97569 11766 -97151 -13511 -97073 -89473 -96949 -24584 -96945 88291 -96487 11795 -96406 14793 -96393 -74765 -96348 -65018...
output:
2 157 164
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 7ms
memory: 15900kb
input:
102 -51 28 -50 -43 -49 10 -48 1 -47 35 -46 48 -45 -13 -44 -31 -43 47 -42 -33 -41 -4 -40 2 -39 -19 -38 30 -37 9 -36 7 -35 6 -34 0 -32 -10 -31 -20 -30 -49 -29 25 -28 -20 -27 -44 -26 39 -25 0 -24 47 -23 21 -22 44 -21 29 -20 10 -19 12 -18 -18 -17 -15 -16 22 -15 48 -14 16 -13 9 -12 -5 -11 -9 -10 -39 -9 1...
output:
2 11 16
result:
ok 2 lines
Test #30:
score: 0
Accepted
time: 7ms
memory: 16772kb
input:
10023 -43847833 25247568 -43845663 8733039 -43838636 5179259 -43836292 1793827 -43822381 40024163 -43820210 -39007118 -43817905 -2879971 -43815454 -30954405 -43815166 -5172304 -43812716 -33955692 -43802254 39807831 -43786912 37254277 -43781753 -23294796 -43781248 -43787269 -43777151 -7784632 -437602...
output:
3 31 292 293
result:
ok 2 lines
Test #31:
score: 0
Accepted
time: 150ms
memory: 29232kb
input:
100000 -50000 24770 -49999 20894 -49998 13386 -49997 18436 -49996 5532 -49995 46989 -49994 -47019 -49993 5933 -49992 25157 -49991 38760 -49990 -18838 -49989 -26564 -49988 13720 -49987 -20401 -49986 -25596 -49985 -17766 -49984 -40566 -49983 -4333 -49982 -8765 -49981 -4272 -49980 -33122 -49979 -49859 ...
output:
6 7379 7380 7381 7396 96725 99984
result:
ok 2 lines
Test #32:
score: 0
Accepted
time: 135ms
memory: 31268kb
input:
100000 -50010 38174 -50009 6226 -50008 -45668 -50007 -28702 -50006 -43951 -50005 38612 -50004 -10089 -50003 36228 -50002 3152 -50001 -31933 -50000 -11085 -49999 -16941 -49998 37111 -49997 -26162 -49996 -43943 -49995 39192 -49994 10898 -49993 -44560 -49992 5905 -49991 34476 -49990 -24532 -49989 28474...
output:
4 5 37240 37957 99998
result:
ok 2 lines
Test #33:
score: 0
Accepted
time: 2ms
memory: 15964kb
input:
100 -51 -12 -50 -40 -48 -44 -47 39 -46 -24 -45 -45 -44 28 -43 -50 -42 13 -41 23 -40 -25 -39 42 -38 19 -37 26 -36 -17 -35 46 -34 -24 -33 35 -32 47 -31 27 -30 -10 -29 -17 -28 -46 -27 31 -26 -31 -25 -48 -24 20 -23 31 -22 -16 -21 -21 -20 -23 -19 -29 -18 11 -17 51 -16 9 -15 -43 -14 -44 -12 -41 -11 10 -10...
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 102ms
memory: 25824kb
input:
83382 -133993820 76865248 -133990261 7033984 -133985576 131479163 -133983908 77729895 -133982156 -106523218 -133976468 12730762 -133975243 132782745 -133972485 -35728865 -133971240 42445369 -133968182 18266933 -133958226 -12176455 -133954836 -88478665 -133952445 10482634 -133951610 1798923 -13395084...
output:
8 21 268 2027 2114 73043 81406 83355 83358
result:
ok 2 lines