QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#349618#4236. Triangular LogsLaStataleBlueCompile Error//C++234.1kb2024-03-10 03:18:362024-03-10 03:18:36

Judging History

你现在查看的是最新测评结果

  • [2024-03-10 03:18:36]
  • 评测
  • [2024-03-10 03:18:36]
  • 提交

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;
        
        if(left==nullptr && right==nullptr)return inf2;
        return merge(left->query(l,r,_l,_mid),right->query(l,r,_mid+1,_r));
    }
};
SegmentTree2 vett2[11'000'000];
int cc2=0;

SegmentTree2* SegmentTree2::newSeg(){
    if(cc2==11'000'000)exit(0);
    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){
    if(cc==MAXN*2+10)exit(0);
    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;
}

详细

/tmp/ccTf6Nf1.o: in function `SegmentTree2::newSeg()':
answer.code:(.text+0x59e): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5a6): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5b5): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5bd): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5cc): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5d4): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5e6): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5ee): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x5fa): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x602): relocation truncated to fit: R_X86_64_PC32 against symbol `inf2' defined in .bss section in /tmp/ccTf6Nf1.o
answer.code:(.text+0x60f): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status