比赛 26暑假集训模拟赛1 评测结果 AAAWWWEEEE
题目名称 光线追踪 最终得分 30
用户昵称 exil 运行时间 2.398 s
代码语言 C++ 内存使用 13.44 MiB
提交时间 2026-06-29 12:00:37
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int sum;
    int l;
    int r;
    int lan;
};
node tree[405][1205];
void jianshu(int shu,int k,int l,int r){
    tree[shu][k]={0,l,r,0};
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    jianshu(shu,k<<1,l,mid);
    jianshu(shu,k<<1|1,mid+1,r);
}
void pushdown(int shu,int x){
    if(tree[shu][x].lan==0)return;
    tree[shu][x<<1].lan=tree[shu][x].lan;
    tree[shu][x<<1|1].lan=tree[shu][x].lan;
    tree[shu][x<<1].sum=(tree[shu][x<<1].r-tree[shu][x<<1].l+1)*tree[shu][x].lan;
    tree[shu][x<<1|1].sum=(tree[shu][x<<1|1].r-tree[shu][x<<1|1].l+1)*tree[shu][x].lan;
    tree[shu][x].lan=0;
}
void add(int shu,int k,int l,int r,int v){
    if(tree[shu][k].l>r || tree[shu][k].r<l)return;
    pushdown(shu,k);
    if(tree[shu][k].l>=l && tree[shu][k].r<=r){
        tree[shu][k].lan=v;
        tree[shu][k].sum=(tree[shu][k].r-tree[shu][k].l+1)*v;
        return;
    }
    add(shu,k<<1,l,r,v);
    add(shu,k<<1|1,l,r,v);
    tree[shu][k].sum=tree[shu][k<<1].sum+tree[shu][k<<1|1].sum;
}
int cha(int shu,int k,int wei){
    if(tree[shu][k].l>wei || tree[shu][k].r<wei)return 0;
    pushdown(shu,k);
    if(tree[shu][k].l==wei && tree[shu][k].r==wei){
        return tree[shu][k].sum;
    }
    return cha(shu,k<<1,wei) + cha(shu,k<<1|1,wei);
}
signed main(){
    freopen("raytracing.in","r",stdin);
    freopen("raytracing.out","w",stdout);
    int q;
    cin>>q;
    if(q<=1000){
        vector<double> v[5];
        for(int i = 1;i<=q;i++){
            int s;
            cin>>s;
            if(s==1){
                double x1,y1,x2,y2;
                cin>>x1>>y1>>x2>>y2;
                v[1].push_back(x1),v[2].push_back(y1),v[3].push_back(x2),v[4].push_back(y2);
                v[0].push_back(i);
            }
            else if(s==2){
                double x,y;
                cin>>x>>y;
                int len=v[1].size();
                double minn=INT_MAX,r=0;
                for(int j = len-1;j>=0;j--){
                    //下边 
                    
                    
                    double xx=v[2][j]/y*x;
                    if(v[1][j]<=xx && v[3][j]>=xx){
                        if(xx<minn){
                            minn=xx;
                            r=v[0][j];
                        }
                        continue;
                    }
                    //左边
                    
                    double yy=v[1][j]/x*y;
                    if(v[2][j]<=yy && v[4][j]>=yy){
                        if(v[1][j]<minn){
                            minn=v[1][j];
                            r=v[0][j];
                        }
                        continue;
                    } 
                
 
                }
                cout<<r<<endl;
            }
        }
        return 0;
    }
    for(int i = 1;i<=402;i++){
        jianshu(i,1,0,200);
    }
    for(int i = 1;i<=q;i++){
        int s;
        cin>>s;
        if(s==1){
            double x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            add(y1,1,x1,x2,i);
            add(x1+201,1,y1,y2,i);
        }
        else if(s==2){
            double x,y;
            cin>>x>>y;
            double minn=INT_MAX;
            int r=0;
            for(int j = 1;j<=200;j++){
                double xx=j/y*x;
                int xx1=xx;
                if(xx1==xx){
                    int e=cha(j,1,xx1);
                    if(e!=0){
                        if(xx<minn){
                            r=e;
                           
                            minn=min(minn,xx);
                        }
                        else if(xx==minn)r=max(r,e);
                        break;
                        
                    }
                    
                }
                else{
                    int e1=cha(j,1,xx1),e2=cha(j,1,xx1+1);
                    if(e1!=0 && e2!=0){
                        if(xx<minn){
                            r=min(e1,e2);
                            //cout<<e1<<" "<<e2<<endl;
                            minn=min(minn,xx);
                        }
                        else if(xx==minn)r=max(r,min(e1,e2));
                        break;
                        
                    }
                    
                }
            }
            
            for(int j = 201;j<=400;j++){
                double yy=(j-200)/x*y;
                int yy1=yy;
                double tt=j-200;
                if(yy1==yy){
                    int e=cha(j,1,yy1);
                    if(e!=0){
                        if(tt<minn){
                            r=e;
                            
                            minn=min(minn,tt);
                        }
                        else if(tt==minn)r=max(r,e);
                        break;
                        
                    }
                    
                }
                else{
                    int e1=cha(j,1,yy1),e2=cha(j,1,yy1+1);
                    if(e1!=0 && e2!=0){
                        if(tt<minn){
                            r=min(e1,e2);
                            //cout<<"ee"<<r<<endl;
                            
                            minn=min(minn,tt);
                        }
                        else if(tt==minn)r=max(r,min(e1,e2));
                        break;
                       
                    }
                    
                }
            }
            cout<<r<<endl;
        }
    }
    
    return 0;
}