Submission #140931

#	Time	Username	Problem	Language	Result	Execution time	Memory
140931		Ruxandra985	Plahte (COCI17_plahte)	C++14	160 / 160	432 ms	31632 KiB

plahte

#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define INF 2000000000
#define DIMN 80010

using namespace std;
int dist , idx , level_sol;
int norm[3*DIMN],tata_dsu[DIMN] , sol[DIMN],tata[DIMN];
vector <int> v[DIMN];
set <int> cul[DIMN];
struct eveniment{
    int y,tip,idx;
} e[3*DIMN];
struct sheet{
    int x1,x2,y1,y2;
} s[DIMN];
struct punct{
    int x,y,c;
}pct[DIMN];
struct segment_tree{
    int level , idx , apart;
}aint[DIMN * 12];
int cmp (eveniment a , eveniment b){
    if (a.y!=b.y)
        return a.y < b.y;
    else if (a.tip != b.tip)
        return a.tip < b.tip;
    return a.idx < b.idx;
}
int findd(int x){
    int st,dr,mid;
    st = 1;
    dr = dist;
    while (st<=dr){
        mid = (st + dr)/2;
        if (norm[mid] == x)
            return mid;
        else if (norm[mid] < x)
            st = mid + 1;
        else dr = mid - 1;
    }
    return -1;
}
void add (int nod,int st,int dr,int l,int r,int val){
    int mid;
    if (l<=st && dr<=r){
        //if (st == 5 && dr == 6)
          //  printf ("%d ",val);
        aint[nod].idx = val;
        aint[nod].level = 1 + level_sol;
        aint[nod].apart++;
        return;
    }
    mid = (st + dr)/2;
    if (l<=mid)
        add(2*nod,st,mid,l,r,val);
    if (mid+1<=r)
        add(2*nod+1,mid+1,dr,l,r,val);

}
void del (int nod,int st,int dr,int l,int r){
    int mid;
    //if ( l == 4 && r == 7)
      //  printf ("%d %d\n",st,dr);
    if (l<=st && dr<=r){
        if (aint[nod].apart > 1){
            aint[nod].idx = tata[aint[nod].idx];
            aint[nod].level--;
        }
        else {
            aint[nod].idx = aint[nod].level = 0;
        }
        aint[nod].apart--;
        return;
    }
    mid = (st + dr)/2;
    if (l<=mid)
        del(2*nod,st,mid,l,r);
    if (mid+1<=r)
        del(2*nod+1,mid+1,dr,l,r);

}
void qry (int nod,int st,int dr,int l,int r){
    int mid = (st + dr)/2;

    //if ( l == r && l == 5)
      //  printf ("%d %d %d %d %d\n",nod,st,dr,aint[nod].idx,aint[nod].level);

    if (aint[nod].level > level_sol){
        level_sol = aint[nod].level;
        idx = aint[nod].idx;
    }

    if (l<=st && dr<=r){
        return;
    }


    if (l<=mid)
        qry(2*nod,st,mid,l,r);
    if (mid+1<=r)
        qry(2*nod+1,mid+1,dr,l,r);
}


void dfs (int nod){
    int i,vecin,sz_max = 0 , heavy;

    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        dfs(vecin);
        if (cul[tata_dsu[vecin]].size() > sz_max){
            sz_max = cul[tata_dsu[vecin]].size();
            heavy = vecin;
        }
    }
    if (!sz_max){ /// nu ai fii de la care sa iei informatii
        sol[nod] = cul[tata_dsu[nod]].size();
        return;
    }

    if (cul[nod].size() > sz_max){
        sz_max = cul[nod].size();
        heavy = nod;
    }

    tata_dsu[nod] = tata_dsu[heavy]; /// il alipesti la padurea aia

    /// merge si erase

    if (heavy!=nod){
        cul[tata_dsu[nod]].insert(cul[nod].begin() , cul[nod].end());
        cul[nod].clear();
    }


    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i];
        if (vecin!=heavy){
            cul[tata_dsu[nod]].insert(cul[tata_dsu[vecin]].begin() , cul[tata_dsu[vecin]].end());
            cul[tata_dsu[vecin]].clear();
        }
    }

    sol[nod] = cul[tata_dsu[nod]].size();

}

int main()
{
    //FILE *fin = fopen ("a.in","r");
    //FILE *fout = fopen ("a.out" , "w");
    int n,m,elem,ev=0,i,x1,y1,x2,y2,x,y,c;
    scanf ("%d%d",&n,&m);
    elem = 0;
    s[0].x1 = -INF;
    s[0].x2 = INF;
    s[0].y1 = -INF;
    s[0].y2 = INF;

    norm[++elem] = -INF;
    norm[++elem] = INF;

    ev++;
    e[ev].y = -INF;
    e[ev].tip = 0; /// incepe dreptunghi
    e[ev].idx = 0;

    ev++;
    e[ev].y = INF;
    e[ev].tip = 2; /// se termina dreptunghi
    e[ev].idx = 0;

    for (i=1;i<=n;i++){
        scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);

        tata_dsu[i] = i; /// initializare pentru dsu

        s[i].x1 = x1;
        s[i].x2 = x2;
        s[i].y1 = y1;
        s[i].y2 = y2;

        norm[++elem] = y1;
        norm[++elem] = y2;

        ev++;
        e[ev].y = x1;
        e[ev].tip = 0; /// incepe dreptunghi
        e[ev].idx = i;

        ev++;
        e[ev].y = x2;
        e[ev].tip = 2; /// se termina dreptunghi
        e[ev].idx = i;
    }
    for (i=1;i<=m;i++){
        scanf ("%d%d%d",&x,&y,&c);

        norm[++elem] = y;

        pct[i].x = x;
        pct[i].y = y;
        pct[i].c = c;
        ev++;
        e[ev].y = x;
        e[ev].tip = 1; /// punct
        e[ev].idx = i;
    }
    /// normalizare y

    sort (norm + 1 , norm + elem + 1);
    dist = 0;
    for (i=1;i<=elem;i++){
        if (dist == 0 || norm[i]!=norm[i-1])
            norm[++dist] = norm[i];
    }

    /// dist = cati y distincti sunt , cb pe norm pt a afla echivalentul normalizat

    sort (e + 1 , e + ev + 1 , cmp);
    for (i=1 ; i<=ev ; i++){

        if (e[i].tip!=1){
            y1 = findd(s[e[i].idx].y1);
            y2 = findd(s[e[i].idx].y2);
        }
        else y = findd(pct[e[i].idx].y);
        if (e[i].tip == 0){ /// incepe dreptunghi
            level_sol = 0;
            if (e[i].idx){ /// nu e dreptunghiul fictiv
                qry (1,1,dist,y1,y2);
                v[idx].push_back(e[i].idx);
                tata[e[i].idx] = idx;
            }
            add(1,1,dist,y1,y2,e[i].idx);
        }
        else if (e[i].tip == 1){ /// punct
            //if (e[i].idx == 8)
              //  printf ("a");
            level_sol = 0;
            qry(1,1,dist,y,y);
            cul[idx].insert(pct[e[i].idx].c);
            //if (idx == 5)
            //printf ("%d %d %d %d\n",pct[e[i].idx].x,pct[e[i].idx].y,pct[e[i].idx].c,e[i].idx);
        }
        else { /// se termina dreptunghi
            //if (e[i].idx == 5)
              //  printf ("%d %d\n",y1,y2);
            del(1,1,dist,y1,y2);
        }
        //if (aint[10].idx == 5)
        //printf ("%d ",aint[10].idx);
    }
    dfs(0); /// dsu
    for (i=1;i<=n;i++)
        printf ("%d\n",sol[i]);
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:111:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
plahte.cpp:114:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (cul[tata_dsu[vecin]].size() > sz_max){
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
plahte.cpp:124:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cul[nod].size() > sz_max){
         ~~~~~~~~~~~~~~~~^~~~~~~~
plahte.cpp:139:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:156:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d%d",&n,&m);
     ~~~~~~^~~~~~~~~~~~~~
plahte.cpp:177:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:200:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d%d",&x,&y,&c);
         ~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32