Submission #147469

#	Time	Username	Problem	Language	Result	Execution time	Memory
147469		alexandra_udristoiu	Plahte (COCI17_plahte)	C++14	160 / 160	1215 ms	499632 KiB

plahte

#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<vector>
#define DIM 80005
using namespace std;
int n, m, i, nr, x, y, x2, y2;
int w[3 * DIM], t[DIM], ff[DIM], sol[DIM];
stack<int> aint[700000];
set<int> s[DIM];
struct str{
    int t, x, y, y2, col, ind;
};
str v[3 * DIM];
vector<int> vec[DIM];
int cmp(str a, str b){
    if(a.x == b.x){
        return a.t < b.t;
    }
    return a.x < b.x;
}
int cautbin(int x){
    int st = 1, dr = nr, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(w[mid] == x){
            return mid;
        }
        if(w[mid] < x){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
}
void update(int nod, int st, int dr, int p, int u, int ind){
    if(p <= st && dr <= u){
        aint[nod].push(ind);
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p, u, ind);
        }
        if(u > mid){
            update(2 * nod + 1, mid + 1, dr, p, u, ind);
        }
    }
}
void update2(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        aint[nod].pop();
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update2(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            update2(2 * nod + 1, mid + 1, dr, p, u);
        }
    }
}
int query(int nod, int st, int dr, int p){
    int x = 0;
    if( !aint[nod].empty() ){
        x = aint[nod].top();
    }
    if(st != dr){
        int mid = (st + dr) / 2;
        if(p <= mid){
            x = max(x, query(2 * nod, st, mid, p) );
        }
        else{
            x = max(x, query(2 * nod + 1, mid + 1, dr, p) );
        }
    }
    return x;
}
void dfs(int nod){
    if(vec[nod].size() == 0){
        ff[nod] = nod;
        sol[nod] = s[nod].size();
        return;
    }
    for(int i = 0; i < vec[nod].size(); i++){
        dfs(vec[nod][i]);
    }
    ff[nod] = ff[ vec[nod][0] ];
    for(int i = 1; i < vec[nod].size(); i++){
        int vecin = vec[nod][i];
        if(s[ ff[nod] ].size() < s[ ff[vecin] ].size() ){
            ff[nod] = ff[vecin];
        }
    }
    set<int>::iterator it;
    for(int i = 0; i < vec[nod].size(); i++){
        int vecin = vec[nod][i];
        if(ff[vecin] == ff[nod]){
            continue;
        }
        for(it = s[ ff[vecin] ].begin(); it != s[ ff[vecin] ].end(); it++){
            s[ ff[nod] ].insert(*it);
        }
    }
    for(it = s[nod].begin(); it != s[nod].end(); it++){
        s[ ff[nod] ].insert(*it);
    }
    sol[nod] = s[ ff[nod] ].size();
}
int main(){
    cin>> n >> m;
    for(i = 1; i <= n; i++){
        cin>> x >> y >> x2 >> y2;
        v[2 * i - 1].ind = v[2 * i].ind = i;
        v[2 * i - 1].y = v[2 * i].y = y;
        v[2 * i - 1].y2 = v[2 * i].y2 = y2;
        v[2 * i - 1].x = x;
        v[2 * i].x = x2;
        v[2 * i - 1].t = 1;
        v[2 * i].t = 3;
        w[2 * i - 1] = y;
        w[2 * i] = y2;
    }
    for(i = 2 * n + 1; i <= 2 * n + m; i++){
        cin>> v[i].x >> v[i].y >> v[i].col;
        v[i].t = 2;
        w[i] = v[i].y;
    }
    m += 2 * n;
    sort(w + 1, w + m + 1);
    nr = 1;
    for(i = 2; i <= m; i++){
        if(w[i] != w[nr]){
            w[++nr] = w[i];
        }
    }
    for(i = 1; i <= m; i++){
        v[i].y = cautbin(v[i].y);
        if(v[i].y2 != 0){
            v[i].y2 = cautbin(v[i].y2);
        }
    }
    sort(v + 1, v + m + 1, cmp);
    for(i = 1; i <= m; i++){
        if(v[i].t == 1){
            x = query(1, 1, nr, v[i].y);
            t[ v[i].ind ] = v[x].ind;
            update(1, 1, nr, v[i].y, v[i].y2, i);
            continue;
        }
        if(v[i].t == 2){
            x = query(1, 1, nr, v[i].y);
            if(x != 0){
                s[ v[x].ind ].insert(v[i].col);
            }
            continue;
        }
        update2(1, 1, nr, v[i].y, v[i].y2);
    }
    for(i = 1; i <= n; i++){
        vec[ t[i] ].push_back(i);
    }
    for(i = 1; i <= n; i++){
        if(t[i] == 0){
            dfs(i);
        }
    }
    for(i = 1; i <= n; i++){
        cout<< sol[i] <<"\n";
    }
}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~
plahte.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < vec[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~
plahte.cpp:99:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int cautbin(int)':
plahte.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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