QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#887552 | #10051. Mi Teleférico | modwwe | 7 | 208ms | 43188kb | C++23 | 5.0kb | 2025-02-07 18:02:29 | 2025-02-07 18:02:32 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf = 1e16;
const ll mod2 = 1e9+7;
const int mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
if(x+y>=mod2) x-=mod2;
if(x+y<0)x+=mod2;
return x+y;
}
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int el = 19;
main()
{
if(fopen(task2".inp","r"))
{
fin(task2);
fou(task2);
}
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
NHP
/// cin>>s1;
//modwwe
phongbeo();
// checktime
}
vector<int> v;
ib a[300001];
id b[300001];
int ans[300001];
int last[300001];
int c[300001];
int net[300001];
bool cmp(ib a,ib b)
{
return a.b<b.b;
}
bool cmp2(id a,id b)
{
return a.a<b.a;
}
struct seg
{
int tlow[1200001];
int thigh[1200001];
void reset(int x)
{
for(int i=1; i<=4*x; i++)
tlow[i]=thigh[i]=inf;
}
void upd(int node,int l,int r,int l1,int x,int y)
{
if(l==r)
{
tlow[node]=min(tlow[node],x);
thigh[node]=min(thigh[node],y);
return;
}
int mid=l+r>>1;
if(l1<=mid)
upd(node<<1,l,mid,l1,x,y);
else upd(node<<1|1,mid+1,r,l1,x,y);
tlow[node]=min(tlow[node<<1],tlow[node<<1|1]);
thigh[node]=min(thigh[node<<1],thigh[node<<1|1]);
}
int getlow(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1||tlow[node]==inf) return inf;
if(l>=l1&&r<=r1) return tlow[node];
int mid=l+r>>1;
return min(getlow(node<<1,l,mid,l1,r1),getlow(node<<1|1,mid+1,r,l1,r1));
}
int gethigh(int node,int l,int r,int l1,int r1)
{
if(l>r1||r<l1||thigh[node]==inf) return inf;
if(l>=l1&&r<=r1) return thigh[node];
int mid=l+r>>1;
return min(gethigh(node<<1,l,mid,l1,r1),gethigh(node<<1|1,mid+1,r,l1,r1));
}
} st;
void phongbeo()
{
cin>>n>>m>>k;
for(int i=1; i<=m; i++)
cin>>a[i].a>>a[i].a>>a[i].b,v.pb(a[i].b),net[i]=1e15;
sort(a+1,a+1+m,cmp);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1; i<=m; i++)
{
net[last[a[i].a]]=i;
if(last[a[i].a]==0)s3=i;
last[a[i].a]=i;
}
for(int i=2; i<=n; i++)
if(last[i]==0)
{
cin>>m;
while(m--)
{
cout<<"No\n";
}
exit(0);
}
s9=a[s3].b;
for(int i=1; i<=m; i++)
{
c[i]=s3;
s3=max(s3,net[i]);
}
st.reset(v.size());
cin>>n;
for(int i=1; i<=n; i++)
cin>>b[i].a>>b[i].b>>b[i].c,b[i].d=i;
sort(b+1,b+1+n,cmp2);
l=1;
for(i=1; i<=n; i++)
{
while(l<=m&&a[l].b<=b[i].a)
{
if(c[l]==1e15)
{
l++;
continue;
}
s3=a[c[l]].b;
s5=lower_bound(v.begin(),v.end(),s3)-v.begin()+1;
st.upd(1,1,v.size(),s5,-a[l].b,s3-a[l].b);
l++;
}
s4=0;
if(l==1)
{
s4=s9-b[i].b;
}
else
{
s5=lower_bound(v.begin(),v.end(),b[i].b)-v.begin()+1;
s4=min(st.gethigh(1,1,v.size(),s5,v.size())+b[i].a-b[i].b,
st.getlow(1,1,v.size(),1,s5-1)+b[i].a);
}
if(l<=m&&c[l]!=1e15)s4=min(s4,a[c[l]].b-b[i].b);
if(s4<=b[i].c)ans[b[i].d]=1;
}
for(int i=1; i<=n; i++)
if(ans[i])cout<<"Yes\n";
else cout<<"No\n";
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 16108kb
input:
10 50 1000000000 1 2 500000000 1 2 500000000 3 8 973873925 3 7 226575828 2 5 256751110 3 9 545005567 2 5 981976767 6 10 125267845 3 8 973873925 3 4 545005567 1 3 545005567 1 8 973873925 3 9 545005567 1 2 500000000 1 5 125267845 4 10 125267845 1 2 500000000 3 8 681014347 2 5 256751110 3 8 973873925 5...
output:
No Yes No No No No Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes No Yes Yes Yes No No No No Yes No No No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes
result:
ok 50 lines
Test #2:
score: 7
Accepted
time: 0ms
memory: 15984kb
input:
17 50 1000000000 14 16 478286115 5 10 96493653 5 7 252785080 1 4 478286115 12 15 690190561 3 7 478286115 1 15 478286115 3 6 455071193 3 10 939277955 9 15 68268425 14 16 478286115 7 17 478286115 10 14 124831832 8 14 478286115 4 10 478286115 6 12 618245135 6 12 618245135 2 10 96493653 7 12 618245135 7...
output:
Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No No No No Yes No No Yes No No No Yes Yes Yes Yes Yes Yes No No Yes No No No No Yes No No No Yes Yes Yes No Yes
result:
ok 50 lines
Test #3:
score: 7
Accepted
time: 1ms
memory: 16104kb
input:
10 34 1000000000 1 9 671346137 7 9 315594823 2 4 891638791 1 5 882501266 1 7 859963142 1 7 669179854 2 4 323169905 4 8 163702438 8 10 331215915 3 4 130285193 1 10 142640042 3 5 675511278 2 3 668843790 1 2 999892708 2 3 1605113 3 4 677256724 1 2 148344385 5 6 998380123 4 9 879352989 5 8 823774249 4 6...
output:
No Yes No Yes No Yes Yes No No Yes Yes Yes No No Yes No Yes No No Yes Yes Yes Yes Yes No Yes Yes Yes No Yes No Yes Yes Yes No Yes Yes Yes Yes Yes No No Yes No Yes Yes Yes Yes Yes Yes
result:
ok 50 lines
Test #4:
score: 7
Accepted
time: 0ms
memory: 16104kb
input:
26 49 1000000000 12 13 611977488 4 16 272949408 2 7 20520813 4 21 524479777 1 14 2390085 11 19 522877672 6 10 505877270 5 10 7126003 5 12 328214743 2 4 26399349 1 12 979252737 5 23 613045504 6 8 499716348 4 5 994871405 2 3 655026912 3 4 588965854 14 22 348737376 5 6 477716057 4 13 32067215 14 17 659...
output:
Yes No Yes Yes Yes Yes Yes Yes Yes Yes No No No Yes No Yes No Yes Yes No Yes No Yes No No No Yes Yes No Yes Yes Yes No No Yes No No No No Yes No No No No No No Yes Yes No No
result:
ok 50 lines
Test #5:
score: 7
Accepted
time: 0ms
memory: 16108kb
input:
10 34 1000000000 5 8 239531297 4 5 584683265 2 3 870040936 7 10 994154255 1 4 785090306 1 3 619543381 1 2 763150606 7 9 817524870 1 2 422771238 1 5 13314391 4 9 19850108 6 9 254794959 2 7 221675669 7 10 127816592 4 7 571872106 4 6 992549438 4 6 297222565 2 10 746750282 3 8 572131190 1 5 249844389 6 ...
output:
No Yes Yes No Yes Yes No No No Yes No No No No Yes No No No Yes No No No Yes Yes Yes No No No Yes Yes Yes No No Yes Yes No Yes No Yes No Yes No No No Yes Yes No No No No
result:
ok 50 lines
Test #6:
score: 7
Accepted
time: 1ms
memory: 16108kb
input:
10 30 1000000000 5 6 851640558 5 8 603410611 4 5 296977015 1 2 420504212 3 7 728427798 6 9 378529260 1 2 926259966 1 4 527897244 3 4 771901862 8 9 855888110 1 3 510298000 7 10 503223315 1 2 609996425 2 3 943605177 5 8 348557013 2 4 996460998 5 6 375443979 4 5 535698016 2 6 607197713 1 10 27471518 5 ...
output:
Yes No Yes No Yes Yes Yes Yes Yes Yes Yes No Yes No Yes No No Yes Yes No Yes Yes Yes No No No Yes Yes Yes Yes Yes Yes No Yes Yes No No Yes Yes No Yes No Yes Yes No No No No Yes Yes
result:
ok 50 lines
Test #7:
score: 7
Accepted
time: 0ms
memory: 16104kb
input:
10 50 1000000000 6 7 179180554 1 5 46594370 6 8 503907400 1 4 703396085 3 4 123570873 1 3 145069235 3 7 956778166 1 8 678109461 8 9 104149168 3 9 468080481 1 2 628112967 3 4 551935548 1 2 827465078 5 7 432464323 1 3 777674996 6 9 220463165 1 3 296236227 5 9 647095589 1 3 54727350 2 4 891427928 7 9 8...
output:
No No No No No Yes Yes Yes Yes Yes No Yes Yes No No Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes No Yes No No Yes Yes Yes Yes Yes Yes Yes No Yes No Yes Yes No Yes No Yes Yes No Yes
result:
ok 50 lines
Test #8:
score: 7
Accepted
time: 1ms
memory: 16104kb
input:
20 50 1000000000 2 7 923019986 5 8 888550152 6 20 983952104 1 19 319407158 1 4 725034276 2 20 204391774 12 13 718010617 3 5 844603010 6 10 19359868 1 2 47810856 2 7 172925971 10 17 794403495 3 15 662261652 10 15 941165566 17 20 700944519 3 8 77339287 2 6 438004684 1 5 445171052 5 11 913778836 10 18 ...
output:
Yes Yes No Yes Yes No No No No No Yes No Yes No Yes No No Yes Yes Yes No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes No Yes Yes No No Yes No No No No Yes Yes Yes No No No No Yes
result:
ok 50 lines
Test #9:
score: 7
Accepted
time: 0ms
memory: 15980kb
input:
30 50 1000000000 2 8 274520841 8 9 822994262 4 18 543151019 11 13 832898984 6 10 361362137 2 4 874253291 23 28 715158332 5 8 798217990 7 24 583132960 3 20 371392965 13 16 343193764 7 11 513510613 21 23 711976125 14 17 115399995 6 15 712839555 12 27 364119438 5 19 185901326 10 25 592414172 6 21 71973...
output:
Yes Yes Yes No Yes Yes No No Yes Yes Yes Yes Yes No No Yes No Yes Yes Yes Yes No Yes Yes Yes No Yes No No No Yes No Yes Yes Yes Yes No No Yes No No No No Yes Yes No Yes No No No
result:
ok 50 lines
Test #10:
score: 7
Accepted
time: 0ms
memory: 15984kb
input:
50 50 1000000000 7 19 617794106 16 25 31582954 28 37 198265350 1 49 761637804 39 40 206412850 25 50 960890099 13 20 269547355 23 46 499718739 9 26 449421318 7 45 549218740 9 13 166331115 32 47 313439513 17 39 815951500 18 38 819225126 24 27 219046275 18 33 228333146 1 3 104278715 17 29 616123961 13 ...
output:
No Yes Yes No Yes Yes Yes No No Yes No Yes No No No Yes No No No No No No No Yes No Yes No Yes No No No No Yes No Yes No Yes Yes No Yes Yes Yes No No No Yes No Yes No Yes
result:
ok 50 lines
Test #11:
score: 7
Accepted
time: 0ms
memory: 7864kb
input:
10 10 1000000000 7 10 856828932 2 4 639288931 5 8 494909659 3 9 401299698 2 5 370163039 3 5 473094287 5 6 277516174 2 3 639523857 1 2 592000034 2 6 975384050 50 154326718 364688986 0 346970214 980918322 0 240629620 435988162 0 47981254 259011299 0 6970193 328908352 0 89370313 471270838 0 122758251 6...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No
result:
ok 50 lines
Test #12:
score: 7
Accepted
time: 0ms
memory: 7704kb
input:
30 50 1000000000 19 22 563696686 16 28 532689170 4 19 805192571 9 23 448517978 1 2 862554533 1 30 135546112 10 18 863190787 1 9 736211294 19 20 824168659 13 25 621103189 12 13 663236301 1 9 109974547 18 26 742986313 5 11 683906404 5 14 108561744 12 29 847040928 9 12 938409396 4 5 669146187 16 21 522...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No
result:
ok 50 lines
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 104ms
memory: 31648kb
input:
3000 300000 10 964 1548 5 401 655 7 158 1943 2 491 1319 5 1312 1783 3 72 203 2 1052 1849 4 310 2050 4 2186 2906 4 197 2168 10 1 141 10 1956 2810 3 1790 2985 6 2288 2814 4 202 301 8 11 486 4 22 159 1 962 1747 2 1906 1943 7 818 2635 1 229 532 10 1869 1983 4 248 1253 9 109 171 10 226 2020 8 476 1664 4 ...
output:
No No No No Yes Yes Yes Yes Yes Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Ye...
result:
wrong answer 441st lines differ - expected: 'No', found: 'Yes'
Subtask #3:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 111ms
memory: 31852kb
input:
3000 300000 100 1789 1993 97 41 2942 23 413 822 93 135 812 64 989 1490 83 120 2338 44 40 159 6 256 499 32 113 573 29 702 2562 51 333 353 6 58 79 14 631 2835 86 233 302 21 142 283 22 28 451 95 6 9 12 152 1061 50 229 1538 73 1717 2993 24 130 1989 91 1794 2838 89 616 844 4 462 2767 23 248 397 25 815 22...
output:
Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes...
result:
wrong answer 27th lines differ - expected: 'No', found: 'Yes'
Subtask #4:
score: 0
Wrong Answer
Test #48:
score: 0
Wrong Answer
time: 155ms
memory: 38120kb
input:
3000 300000 300000 1437 1448 41921 6 1490 100458 1102 1833 169594 147 1625 35757 22 90 249205 202 224 238633 174 678 96122 204 233 64048 573 1943 282174 7 384 222187 1250 1815 200905 483 2076 146227 973 1442 296192 400 2320 85525 90 1457 52616 1621 2227 152457 1563 1757 14155 397 1428 124886 2001 25...
output:
Yes No Yes Yes Yes Yes Yes Yes No Yes No Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes...
result:
wrong answer 11th lines differ - expected: 'Yes', found: 'No'
Subtask #5:
score: 0
Wrong Answer
Test #65:
score: 0
Wrong Answer
time: 161ms
memory: 40972kb
input:
3000 300000 300000 923 1232 226115 2404 2688 7731 881 915 112305 382 460 245741 2789 2880 247366 378 627 48776 564 1634 183198 262 1076 72590 1117 1947 105415 67 92 119328 1120 1656 77077 62 73 137310 333 336 244627 484 613 245727 195 1193 150354 2377 2653 120515 853 2237 133636 246 702 237472 2890 ...
output:
Yes No No Yes Yes Yes Yes No No No No Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes No Yes Yes Yes No Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes No ...
result:
wrong answer 1st lines differ - expected: 'No', found: 'Yes'
Subtask #6:
score: 0
Wrong Answer
Test #82:
score: 0
Wrong Answer
time: 121ms
memory: 29108kb
input:
300 8000 1000000000 40 209 882793335 136 161 415218683 85 237 681095399 89 221 21080810 94 98 189576197 40 41 277445174 122 286 266699843 34 50 166404174 158 258 270791285 64 112 605818708 9 250 237222744 221 274 211785329 84 233 740491264 66 260 863820010 90 134 180174669 5 8 718323541 193 258 7374...
output:
Yes Yes No Yes Yes No No No No No No Yes No Yes Yes No No No No No Yes Yes No No No No Yes Yes Yes Yes No No No Yes No No No No Yes Yes Yes Yes No Yes No No No Yes Yes No Yes Yes No No No Yes No No Yes No Yes No No Yes Yes No No No Yes Yes Yes No No Yes Yes Yes No Yes Yes No No No No No No No No No ...
result:
wrong answer 3rd lines differ - expected: 'Yes', found: 'No'
Subtask #7:
score: 0
Wrong Answer
Test #117:
score: 0
Wrong Answer
time: 208ms
memory: 43188kb
input:
3000 300000 1000000000 546 2448 697609657 1391 1486 569292288 875 2215 150348507 84 103 419587353 618 2459 633971761 588 920 31424403 120 1113 707624354 247 1761 695858303 524 1368 245595669 821 1718 314921143 260 1200 240918273 357 1213 706310950 1489 2280 11838279 807 1518 852953024 1253 2525 1543...
output:
Yes No No Yes No Yes No No No Yes No No No Yes No Yes No No No No No No No No No No No Yes No No Yes Yes No No Yes No No No No No No Yes Yes No No No Yes No No No Yes No No No No Yes No Yes Yes Yes Yes No No Yes No No No No No No Yes Yes No No No No No No Yes No No Yes Yes Yes No Yes Yes No Yes Yes ...
result:
wrong answer 2nd lines differ - expected: 'Yes', found: 'No'