QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#349597 | #4236. Triangular Logs | LaStataleBlue | RE | 1ms | 3904kb | C++23 | 4.0kb | 2024-03-10 03:10:39 | 2024-03-10 03:10:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200'005, NUM = 45, LOGN = 20, inf = 1e9+7;
array<int,NUM> inf2;
array<int,NUM> merge(array<int,NUM> a,array<int,NUM> b){
array<int,NUM> res;
int inda=0,indb=0;
for(int i=0;i<NUM;i++){
if(inda==NUM)res[i]=b[indb++];
else if(indb==NUM)res[i]=a[inda++];
else if(a[inda]<b[indb]){
res[i]=a[inda++];
}else{
res[i]=b[indb++];
}
}
return res;
}
#define _mid (_l+_r)/2
struct SegmentTree2{
array<int,NUM> maxi;
SegmentTree2 *left,*right;
static SegmentTree2* newSeg();
void checknode(){
if(left==nullptr)left=newSeg();
if(right==nullptr)right=newSeg();
}
void update(int pos,int val,int _l,int _r){
if(pos<_l || pos>_r)return;
for(int i=0;i<NUM;i++){
if(maxi[i]>val){
for(int j=i+1;j<NUM;j++){
maxi[j]=maxi[j-1];
}
maxi[i]=val;
break;
}
}
if(_l!=_r){
checknode();
left->update(pos,val,_l,_mid);
right->update(pos,val,_mid+1,_r);
}
}
array<int,NUM> query(int l,int r,int _l,int _r){
if(r<_l || l>_r || l>r)return inf2;
if(_l>=l && _r<=r)return maxi;
return merge(left->query(l,r,_l,_mid),right->query(l,r,_mid+1,_r));
}
};
SegmentTree2 vett2[1'000'000];
int cc2=0;
SegmentTree2* SegmentTree2::newSeg(){
int ind = cc2++;
vett2[ind].maxi=inf2;
return &vett2[ind];
}
struct SegmentTree{
SegmentTree2 *ds;
SegmentTree *left,*right;
static SegmentTree* newSeg(int _l,int _r);
void update(int x,int y,int val,int _l,int _r){
if(_r<x || _l>x)return;
ds->update(y,val,0,MAXN);
if(_l!=_r){
left->update(x,y,val,_l,_mid);
right->update(x,y,val,_mid+1,_r);
}
}
array<int,NUM> query(int x1,int x2,int y1,int y2,int _l,int _r){
if(x1>_r || x2<_l || x1>x2)return inf2;
if(_l>=x1 && _r<=x2)return ds->query(y1,y2,0,MAXN);
return merge(left->query(x1,x2,y1,y2,_l,_mid),right->query(x1,x2,y1,y2,_mid+1,_r));
}
};
SegmentTree vett[MAXN*2+10];
int cc=0;
SegmentTree* SegmentTree::newSeg(int _l,int _r){
int ind = cc++;
vett[ind].ds = SegmentTree2::newSeg();
if(_l!=_r){
vett[ind].left=newSeg(_l,_mid);
vett[ind].right=newSeg(_mid+1,_r);
}
return &vett[ind];
}
void solve([[maybe_unused]] int t){
int n,q;
cin>>n>>q;
vector<int> x(n),y(n),h(n);
map<int,int> tmp;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i]>>h[i];
tmp[x[i]]=0;
tmp[y[i]]=0;
}
tmp[inf]=0;
int cont=0;
for(auto &[i,j] : tmp){
j=cont++;
}
SegmentTree *ds = SegmentTree::newSeg(0,cont);
for(int i=0;i<n;i++){
ds->update(tmp[x[i]],tmp[y[i]],h[i],0,cont);
}
for(int i=0;i<q;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
x1 = tmp.lower_bound(x1)->second;
y1 = tmp.lower_bound(y1)->second;
x2 = tmp.lower_bound(x2)->second;
y2 = tmp.lower_bound(y2)->second;
array<int,NUM> ans = ds->query(x1,x2,y1,y2,0,cont);
//for(int i=0;i<10;i++){
// cout<<ans[i]<<" ";
//}
//cout<<"ecco\n";
bool ok = false;
for(int j=2;j<NUM;j++){
if(ans[j]==inf)continue;
if(ans[j]<ans[j-1]+ans[j-2])ok=true;
}
cout<<ok<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=0;i<NUM;i++)inf2[i]=inf;
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3904kb
input:
9 5 1 3 3 2 3 1 3 3 4 1 2 1 2 2 5 3 2 9 1 1 2 2 1 6 3 1 5 1 1 1 2 1 1 2 2 1 1 1 3 1 2 3 2 1 1 3 3
output:
0 1 0 0 1
result:
ok 5 lines
Test #2:
score: -100
Runtime Error
input:
481 1 8 6788 8975 24 6552 2668 26 7948 4730 40 531 9805 110 1914 1916 164 7073 3371 165 6293 7756 170 9946 2003 179 9654 1700 215 6447 2229 221 3149 3030 242 1999 6843 242 5764 3163 249 3716 8634 250 6801 9317 260 2741 4273 282 5436 4836 284 3951 6483 288 4812 76 375 9004 5492 380 5627 5929 391 6385...