QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #178089 | #1179. Contamination | STUDENT0 | AC ✓ | 1665ms | 118696kb | C++14 | 1.4kb | 2023-09-13 17:55:17 | 2023-09-13 17:55:17 |
Judging History
answer
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct c{
int d,e,f,g,h;
}j[2000000];
int k[3000000],t[8388608],u;
string cc[1000000];
bool o(c p,c q)
{
return p.e<q.e||p.e==q.e&&p.g<q.g;
}
bool w(int x,int y,int z,int aa,int bb)
{
if (x>=z&&y<=aa) return t[bb]>=j[u].f;
if (z<=x+y>>1&&w(x,x+y>>1,z,aa,bb<<1)) return 1;
if (aa>x+y>>1&&w((x+y>>1)+1,y,z,aa,bb<<1^1)) return 1;
return 0;
}
int main()
{
int a,b,i,l,m,n,r,s,v,dd;
scanf("%d%d",&a,&b);
for (i=0;i<a;i++)
{
scanf("%d%d%d",&j[i].d,&j[i].e,&j[i].f);
j[i].e-=j[i].f;
j[i].f+=j[i].e+j[i].f;
j[i].g=-1;
k[i]=j[i].d;
}
for (l=0;l<b;l++)
{
scanf("%d%d%d%d%d%d",&j[a+l].d,&m,&j[a+l].h,&n,&j[a+l].e,&j[a+l].f);
// if (l==2299) cout<<j[a+l].d<<" "<<m<<" "<<j[a+l].h<<" "<<n<<" "<<j[a+l].e<<" "<<j[a+l].f<<endl;
j[a+l].g=l;
k[a+(l<<1)]=j[a+l].d;
k[a+(l<<1)+1]=j[a+l].h;
}
sort(j,j+a+b,o);
sort(k,k+a+(b<<1));
r=1<<int(ceil(log(a+(b<<1))/log(2)));
for (s=1;s<r<<1;s++) t[s]=-1000000001;
for (;u<a+b;u++) if (j[u].g==-1) for (v=r+lower_bound(k,k+a+(b<<1),j[u].d)-k;v;v>>=1) t[v]=max(t[v],j[u].f);
else if (w(0,r-1,lower_bound(k,k+a+(b<<1),min(j[u].d,j[u].h))-k,lower_bound(k,k+a+(b<<1),max(j[u].d,j[u].h))-k,1)) cc[j[u].g]="NO\n";
else cc[j[u].g]="YES\n";
for (dd=0;dd<b;dd++) cout<<cc[dd];
return 0;
}
/*
4 1
3 3 2
7 7 3
12 5 2
8 2 1
10 9 0 9 4 9
*/
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 40396kb
input:
3 3 3 3 2 7 7 3 12 5 2 1 4 14 4 2 6 1 4 14 4 4 7 1 4 14 4 3 9
output:
YES NO YES
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 36ms
memory: 46088kb
input:
4 85076 3 3 2 7 7 3 12 5 2 8 2 1 0 9 0 9 0 9 0 9 0 9 1 9 0 9 0 9 2 9 0 9 0 9 3 9 0 9 0 9 4 9 0 9 0 9 5 9 0 9 0 9 6 9 0 9 0 9 7 9 0 9 0 9 8 9 0 9 0 9 9 9 0 9 1 9 0 9 0 9 1 9 1 9 0 9 1 9 2 9 0 9 1 9 3 9 0 9 1 9 4 9 0 9 1 9 5 9 0 9 1 9 6 9 0 9 1 9 7 9 0 9 1 9 8 9 0 9 1 9 9 9 0 9 2 9 0 9 0 9 2 9 1 9 0 9...
output:
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 YES YES YES YES YES YES YES YES YES YES YES NO NO NO NO NO NO YES YES YES YES NO NO NO NO NO NO YES YES YES YES NO NO NO NO NO N...
result:
ok 85076 tokens
Test #3:
score: 0
Accepted
time: 682ms
memory: 84876kb
input:
60000 1000000 317019858 -453590068 1859484 88391669 912272848 1969071 -111486904 302322746 1924539 -136256363 -826084674 1914964 809111862 107646868 1927616 514237791 857438747 1979607 -436520809 616429677 1962669 754842512 -655550538 1871559 216022803 261869501 1908243 -269097217 378277677 1966064 ...
output:
YES YES YES NO NO NO YES NO NO NO YES YES YES YES NO YES NO NO NO YES NO YES NO YES NO YES NO YES NO NO YES YES YES YES YES NO YES YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES NO NO YES YES NO YES NO NO YES YES YES YES YES YES YES NO YES YES NO YES NO YES YES NO YES YES YES N...
result:
ok 1000000 tokens
Test #4:
score: 0
Accepted
time: 1665ms
memory: 118696kb
input:
1000000 999500 -786701000 11 751 -261287000 -109 371 644457000 -224 326 -112133000 173 393 -7669000 -311 337 314509000 110 387 -144839000 -251 302 921285000 -132 348 -852019000 -35 838 -184221000 124 343 282699000 353 452 -297163000 -264 317 -493643000 34 349 285117000 347 441 -38087000 -206 270 753...
output:
NO YES YES YES YES YES YES NO NO NO NO YES NO YES YES NO YES NO YES YES YES NO YES YES NO YES NO NO YES NO YES YES YES YES NO NO YES YES YES YES NO NO YES YES YES NO NO YES YES YES YES NO YES NO YES NO NO YES YES YES YES NO YES NO YES NO YES NO NO NO NO YES NO NO NO NO YES YES YES NO YES YES NO YES ...
result:
ok 999500 tokens