Cod sursa(job #3165231)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 5 noiembrie 2023 18:15:33
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.33 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

#define DIM 100000
using namespace std;

//ofstream g("debug.out");

int n,m,B,S,k1,k2;
float sol[2*DIM+5];
int a,b,c,t;

struct info{
    float val;
    //bool lazy = 0;
}aint[4*DIM+5];

struct info2{
    int st;
    int dr;
    int order;
    int type;
}qx[2*2*2*DIM+5],qy[2*2*2*DIM+5];

bool cmp(info2 a,info2 b){
    return a.order < b.order;
}

info makeInfo(info a,info b){

    info sol;

    if(a.val == 0 && b.val == 0){
        sol.val = 0;
    }else if(a.val >= 1 && b.val >= 1){
        sol.val = 1;
    }else{
        sol.val = 0.5;
    }

    return sol;

}

/*void propag(int nod,int st,int dr){
    if(aint[nod].lazy){
        if(st!=dr){
            aint[2*nod].val +=aint[nod].lazy;
            aint[2*nod].lazy +=aint[nod].lazy;

            aint[2*nod+1].val +=aint[nod].lazy;
            aint[2*nod+1].lazy +=aint[nod].lazy;
        }
        aint[nod].lazy = 0;
    }
}*/

void build(int nod,int st,int dr){
    if(st == dr){
        aint[nod].val = 0;
    }else{
        int mid = (st+dr)/2;

        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);

        aint[nod].val = 0;
    }

}

info query(int nod,int st,int dr,int a,int b){
    //propag(nod,st,dr);
    if(a<=st && dr<=b){
        return aint[nod];
    }else{
        int mid = (st+dr)/2;

        if(b<=mid){
            return query(2*nod,st,mid,a,b);
        }
        if(mid+1<=a){
            return query(2*nod+1,mid+1,dr,a,b);
        }

        return makeInfo(query(2*nod,st,mid,a,b),query(2*nod+1,mid+1,dr,a,b));
    }
}

void update(int nod,int st,int dr,int a,int b,int x){
    //propag(nod,st,dr);

    if(st == dr/*a<=st && dr<=b*/){
        aint[nod].val += x;
        //aint[nod].lazy += x;
    }else{
        int mid = (st+dr)/2;

        if(a<=mid){
            update(2*nod,st,mid,a,b,x);
        }
        if(mid+1<=b){
            update(2*nod+1,mid+1,dr,a,b,x);
        }

        aint[nod] = makeInfo(aint[2*nod],aint[2*nod+1]);
    }

}

int main()
{
    //ifstream cin("in.in");

    int x1,x2,y1,y2;

    cin>>n>>m;

    cin>>B;
    for(int i=1;i<=B;i++){
        cin>>y1>>x1>>y2>>x2;

        k1++;
        qx[k1].order = x1;
        qx[k1].st = y1;
        qx[k1].dr = y2;
        qx[k1].type = -1;

        k1++;
        qx[k1].order = x2+1;
        qx[k1].st = y1;
        qx[k1].dr = y2;
        qx[k1].type = -2;

        k2++;
        qy[k2].order = y1;
        qy[k2].st = x1;
        qy[k2].dr = x2;
        qy[k2].type = -1;

        k2++;
        qy[k2].order = y2+1;
        qy[k2].st = x1;
        qy[k2].dr = x2;
        qy[k2].type = -2;
    }

    cin>>S;

    for(int i=1;i<=S;i++){
        sol[i]=-1;
    }

    for(int i=1;i<=S;i++){
        cin>>t>>a>>b>>c;

        if(t==1){
            k2++;
            qy[k2].order = a;
            qy[k2].st = b;
            qy[k2].dr = c;
            qy[k2].type = i;
        }else{
            k1++;
            qx[k1].order = a;
            qx[k1].st = b;
            qx[k1].dr = c;
            qx[k1].type = i;
        }
    }

    sort(qx+1,qx+k1+1,cmp);
    sort(qy+1,qy+k2+1,cmp);

    int st,dr,type;
    build(1,1,n);
    for(int i=1;i<=k1;i++){
        st = qx[i].st;
        dr = qx[i].dr;
        type = qx[i].type;

        //g<<st<<" "<<dr<<" "<<type<<" "<<'\n';

        if(type == -1){
            update(1,1,n,st,dr,1);
        }else if(type == -2){
            update(1,1,n,st,dr,-1);
        }else{
            info val = query(1,1,n,st,dr);
            sol[type] = val.val;
        }
    }

    build(1,1,m);
    for(int i=1;i<=k2;i++){
        st = qy[i].st;
        dr = qy[i].dr;
        type = qy[i].type;

        //g<<st<<" "<<dr<<" "<<type<<" "<<'\n';

        if(type == -1){
            update(1,1,m,st,dr,1);
        }else if(type == -2){
            update(1,1,m,st,dr,-1);
        }else{
            info val = query(1,1,m,st,dr);
            sol[type] = val.val;
        }
    }

    for(int i=1;i<=S;i++){
        //g<<sol[i]<<'\n';
        if(sol[i] == 1){
            cout<<"SUNK\n";
        }else if(sol[i] == 0){
            cout<<"MISS\n";
        }else{
            cout<<"HIT\n";
        }
    }


    return 0;
}