Submission #138344

#	Time	Username	Problem	Language	Result	Execution time	Memory
138344		Linca_Robert	Plahte (COCI17_plahte)	C++14	0 / 160	493 ms	37120 KiB

plahte

#include<bits/stdc++.h>
#define Nst (nod<<1)
#define Ndr ((nod<<1)|1)
using namespace std;

const int DIM = 8e4 + 5;

int N, M;

struct event{
    int tip, pos, x, y, ind;
};
vector<event> arr;
vector<int> Norm, edge[DIM];
set<int> col[DIM];
int t[DIM], wh_set[DIM], ans[DIM];

struct aint{
    bool lazy;
    int val;
} A[4 * DIM];

void build( int nod, int st, int dr ){
    A[nod].lazy = false;
    A[nod].val = 1;
    if( st != dr ){
        int mid = ( st + dr ) >> 1;
        build( Nst, st, mid + 0 );
        build( Ndr, mid + 1, dr );
    }
}

inline void update_lazy( int nod, int st, int dr ){
    if( A[nod].lazy == false )
        return;
    A[nod].lazy = false;
    if( st != dr ){
        A[Nst].lazy = A[Ndr].lazy = true;
        A[Nst].val = A[Ndr].val = A[nod].val;
    }
}

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

    if( a <= st && dr <= b ){
        A[nod].lazy = true;
        A[nod].val = x;
    }else{
        int mid = ( st + dr ) >> 1;
        if( a <= mid )
            update( Nst, st, mid + 0, a, b, x );
        if( b > mid )
            update( Ndr, mid + 1, dr, a, b, x );
    }
}

int query( int nod, int st, int dr, int p ){
    update_lazy( nod, st, dr );

    if( st == dr ){
        return A[nod].val;
    }else{
        int mid = ( st + dr ) >> 1;
        if( p <= mid )
            return query( Nst, st, mid + 0, p );
        else
            return query( Ndr, mid + 1, dr, p );
    }
}

inline bool cmp( event a, event b ){
    if( a.pos == b.pos )
        return a.tip < b.tip;
    return a.pos < b.pos;
}

inline int getp( int x ){
    int st = 0, dr = Norm.size() - 1;
    while( st <= dr ){
        int mid = ( st + dr ) >> 1;
        if( Norm[mid] <= x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr + 1;
}

void dfs( int v ){
    wh_set[v] = v;

    if( edge[v].empty() ){
        ans[v] = col[ wh_set[v] ].size();
        return;
    }

    for( auto son : edge[v] )
        dfs( son );

    int heavy_son = v;
    for( auto son : edge[v] ){
        if( col[ wh_set[son] ] > col[ wh_set[heavy_son] ] )
            heavy_son = son;
    }

    wh_set[v] = heavy_son;
    for( auto son : edge[v] ){
        if( son != wh_set[v] ){
            for( set<int>::iterator it = col[ wh_set[son] ].begin(); it != col[ wh_set[son] ].end(); it++ )
                col[ wh_set[v] ].insert( (*it) );
        }
    }

    if( wh_set[v] != v )
        for( set<int>::iterator it = col[v].begin(); it != col[v].end(); it++ )
            col[ wh_set[v] ].insert( (*it) );
    ans[v] = col[ wh_set[v] ].size();
    return;
}

int main(){

    cin >> N >> M;
    for( int i = 1; i <= N; i++ ){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        arr.push_back( {1, x1, y1, y2, i + 1} );
        arr.push_back( {3, x2, y1, y2, i + 1} );
        Norm.push_back( y1 );
        Norm.push_back( y2 );
    }

    for( int i = 1; i <= M; i++ ){
        int x, y, c; cin >> x >> y >> c;
        arr.push_back( {2, x, y, y, c} );
        Norm.push_back( y );
    }

    sort( Norm.begin(), Norm.end() );
    Norm.resize( distance( Norm.begin(), unique( Norm.begin() , Norm.end() ) ) );

    sort( arr.begin(), arr.end(), cmp );
    int n = N + 1;
    N = Norm.size();
    build( 1, 1, N );

    for( int i = 0; i < arr.size(); i++ ){
        event curr = arr[i];
        if( arr[i].tip == 1 ){
            int p1 = getp( arr[i].x ), p2 = getp( arr[i].y );
            t[ arr[i].ind ] = query( 1, 1, N, p1 );
            edge[ t[ arr[i].ind ] ].push_back( arr[i].ind );
            update( 1, 1, N, p1, p2, arr[i].ind );
        }

        if( arr[i].tip == 2 ){
            int nod = query( 1, 1, N, getp( arr[i].x ) );
            col[nod].insert( arr[i].ind );
        }

        if( arr[i].tip == 3 ){
            int p1 = getp( arr[i].x ), p2 = getp( arr[i].y );
            update( 1, 1, N, p1, p2, t[ arr[i].ind ] );
        }
    }

    dfs( 1 );

    for( int i = 2; i <= n; i++ )
        cout << ans[i] << "\n";
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0; i < arr.size(); i++ ){
                     ~~^~~~~~~~~~~~
plahte.cpp:148:15: warning: variable 'curr' set but not used [-Wunused-but-set-variable]
         event curr = arr[i];
               ^~~~

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