Submission #143365

#	Time	Username	Problem	Language	Result	Execution time	Memory
143365		nicolaalexandra	Plahte (COCI17_plahte)	C++14	64 / 160	914 ms	460436 KiB

plahte

//#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#define DIM 80010
#define INF 2000000000
using namespace std;

//ifstream cin ("date.in");
//ofstream cout ("date.out");
struct point{
    int x,y,c;
};
point points[DIM];
struct dreptunghi{
    int x1,y1,x2,y2;
};
dreptunghi v[DIM];
struct event{
    int tip; /// 1-inceput de dreptunghi, 2-bila, 3-se termina dreptunghi
    int x; /// dreapta de baleiere
    int idx; /// indexul dreptunghiului
};
vector <event> events;
vector <int> L[DIM];
deque <int> aint[4*DIM];
set <int> colors[DIM];
int t[DIM],sol[DIM],s[4*DIM],viz[DIM];
int n,m,i,j,X1,Y1,X2,Y2,x,y,c,maxim,sol_poz,maxi,el,k;
inline int cmp (event a, event b){
    if (a.x == b.x)
        return a.tip < b.tip; /// bila trebuie sa o pun pe contur
    return a.x < b.x;
}
void update (int nod, int st, int dr, int x, int y, int val, int tip){
    if (x <= st && dr <= y){
        if (tip == 0) /// intra dreptunghi
            aint[nod].push_back(val);
        else aint[nod].pop_back();
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val,tip);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val,tip);
}
void query (int nod, int st, int dr, int poz){
    if (aint[nod].size()){
        if (t[aint[nod].back()] > maxim){
            maxim = t[aint[nod].back()];
            sol_poz = aint[nod].back();
        }}
    if (st >= dr)
        return;
    int mid = (st+dr)>>1;
    if (poz <= mid)
        query (nod<<1,st,mid,poz);
    else query ((nod<<1)|1,mid+1,dr,poz);
}
void dfs (int nod){
    int aux = nod;
    viz[nod] = 1;
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (!viz[vecin]){
            dfs (vecin);
            /// acum trebuie sa dau merge la seturile culorilor
            if (colors[aux].size() < colors[vecin].size())
                swap (aux,vecin);
            for (set<int>:: iterator it=colors[vecin].begin();it!=colors[vecin].end();it++)
                colors[aux].insert(*it);
        }}
    sol[nod] = colors[aux].size();
    swap (colors[aux],colors[nod]);
}
int cautare_binara (int v[], int n, int val){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] == val)
            return mid;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
    return -1;
}
int main (){

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>X1>>Y1>>X2>>Y2;
        events.push_back({1,X1,i});
        events.push_back({3,X2,i});
        v[i] = {X1,Y1,X2,Y2};
        s[++el] = Y1, s[++el] = Y2;
    }
    /// adaug dreptunghiul mare care le cuprinde pe toate
    v[0] = {-INF,-INF,INF,INF};
    events.push_back({1,-INF,0});
    events.push_back({3,INF,0});
    s[++el]  = -INF, s[++el] = INF;

    for (i=1;i<=m;i++){
        cin>>x>>y>>c;
        events.push_back({2,x,i});
        points[i] = {x,y,c};
        s[++el] = y;
    }

    sort (events.begin(),events.end(),cmp);
    /// elimin dublurile
    sort (s+1,s+el+1);
    k = 1;
    for (i=2;i<=el;i++)
        if (s[i] != s[i-1])
            s[++k] = s[i];

    maxi = k;
    for (i=0;i<events.size();i++){
        if (events[i].tip == 1){ /// inceput de dreptunghi
            if (events[i].x != -INF){
                /// trebuie sa aflu cel mai mic dreptunghi in care e inclus
                /// ca sa construiesc graful
                int poz = cautare_binara(s,k,v[events[i].idx].y1);
                maxim = -1;
                query (1,1,maxi,poz);
                L[sol_poz].push_back(events[i].idx);
            }
            t[events[i].idx] = i+1; /// tin minte din ce dreapa de baleiere l am obtinut
            /// acum il introduc in aint
            int poz1 = cautare_binara(s,k,v[events[i].idx].y1);
            int poz2 = cautare_binara(s,k,v[events[i].idx].y2);
            update (1,1,maxi,poz1,poz2,events[i].idx,0);
            continue;
        }
        if (events[i].tip == 3){
            /// se termina dreptunghi, deci trebuie sa dau pop_back la stiva
            int poz1 = cautare_binara(s,k,v[events[i].idx].y1);
            int poz2 = cautare_binara(s,k,v[events[i].idx].y2);
            update (1,1,maxi,poz1,poz2,events[i].idx,1);
            continue;
        }
        /// bila
        int poz = cautare_binara(s,k,points[events[i].idx].y);
        maxim = -1;
        query (1,1,maxi,poz);
        /// trebuie sa inserez culoarea in setul dreptunghiului
        colors[sol_poz].insert(points[events[i].idx].c);
    }

    dfs (0);
    for (i=1;i<=n;i++)
        cout<<sol[i]<<"\n";

    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++){
                  ~^~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<events.size();i++){
              ~^~~~~~~~~~~~~~

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