Submission #37675

# Submission time Handle Problem Language Result Execution time Memory
37675 2017-12-26T21:39:10 Z wasyl Plahte (COCI17_plahte) C++11
0 / 160
339 ms 32128 KB
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define d(...) 
#define EB(...) emplace_back(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template< typename t >
using V = vector< t >;

constexpr int maxM = 80000;
constexpr int INF = 1e9 + 1;

struct Ev
{
	int typ;
	int lo, hi;
	int x;
	int id;
	Ev( int typ, int lo, int hi, int x, int id ) : 
	typ( typ ), lo( lo ), hi( hi ), x( x ), id( id ) {}
};

inline bool operator< ( const Ev& mn, const Ev& wc )
{
	return mn.x == wc.x? mn.typ < wc.typ : mn.x < wc.x;
}

inline ostream& operator<< ( ostream& s, const Ev& ev )
{
	return s << ev.typ << ' ' << ev.lo << ' ' << ev.hi << ' ' << ev.x << ' ' << ev.id;
}

struct Cords
{
	int x, y, color;
	Cords( int x, int y, int color ) 
	: x( x ), y( y ), color( color ) {}
};

inline bool operator< ( const Cords& mn, const Cords& wc )
{
	return mn.color < wc.color;
}

inline ostream& operator<< ( ostream& s, const Cords& a )
{
	return s << a.x << ' ' << a.y << ' ' << a.color;
}

struct Node : V< int >
{
	set< int > S;
};

struct TreeNode
{
	int val, t;
};

int t;
int n, m, rozm = 1;
V< Node > graf;
V< TreeNode > tree;
V< Cords > points;
V< Ev > evs;
V< int > low;
V< int > ojc;
V< int > odp;

inline int query ( int v )
{
	v += rozm;
	int t = -1, res = 0;
	while ( v >= 1 )
	{
		if ( tree[v].t > t )
		{
			t = tree[v].t;
			res = tree[v].val;
		}
		v /= 2;
	}
	return res;
}

inline void insert ( int l, int p, int co )
{
	++t;
	l += rozm; p += rozm;
	tree[l].val = co;
	tree[l].t = t;
	tree[p].val = co;
	tree[p].t = t;
	while ( l / 2 != p / 2 )
	{
		if ( l % 2 == 0 )
		{
			tree[l + 1].val = co;
			tree[l + 1].t = t;
		}
		if ( p % 2 == 1 )
		{
			tree[p - 1].val = co;
			tree[p - 1].t = t;
		}
		l /= 2; p /= 2;
	}
}

inline void proceed ( const Ev& ev )
{
	d( cerr << ev << '\n' );
	if ( ev.typ == 0 )
	{
		int l = lower_bound( ALL( low ), ev.lo ) - low.begin();
		int p = lower_bound( ALL( low ), ev.hi ) - low.begin();
		int oj = query( l );
		ojc[ev.id] = oj;
		d( cerr << "ojciec: " << oj << '\n' );
		graf[oj].push_back( ev.id );
		insert( l, p, ev.id );
	}	
	if ( ev.typ == 1 )
	{
		int p = lower_bound( ALL( low ), ev.lo ) - low.begin();
		int v = query( p );
		d( cerr << "zawiera sie w: " << v << '\n' );
		graf[v].S.insert( points[ev.id].color );
	}
	if ( ev.typ == 2 )
	{
		int l = lower_bound( ALL( low ), ev.lo ) - low.begin();
		int p = lower_bound( ALL( low ), ev.hi ) - low.begin();
		d( cerr << "podmieniam: " << ev.id << " na " << ojc[ev.id] << '\n' );
		insert( l, p, ojc[ev.id] );
	}
}

inline void dfs ( int v )
{
	for ( int s : graf[v] )
		dfs( s );
	if ( v != 0 )
		for ( int s : graf[v] )
		{
			if ( graf[s].S.size() > graf[v].S.size() )
				swap( graf[s].S, graf[v].S );
			for ( int k : graf[s].S )
				graf[v].S.insert( k );
		}
	odp[v] = graf[v].S.size();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	graf.resize( n + 1 );
	ojc.resize( n + 1 );
	odp.resize( n + 1 );
	for ( int i = 0; i < n; ++i )
	{
		int x, y, x2, y2;
		cin >> x >> y >> x2 >> y2;
		evs.push_back( Ev( 0, y, y2, x, i + 1 ) );
		evs.push_back( Ev( 2, y, y2, x2, i + 1 ) );	
	}
	
	for ( int i = 0; i < m; ++i )
	{
		int x, y, k;
		cin >> x >> y >> k;
		points.push_back( Cords( x, y, k ) );			
	}				

	sort( ALL( points ) );
	int tmp = 0;
	
//	d( cerr << "przed: \n" );
//	for ( auto p : points )
//		d( cerr << p << '\n' );
	
	for ( int i = 0; i < points.size(); ++i )
	{
		bool fl = false;
		if ( i + 1 < points.size() and points[i].color != points[i + 1].color )
			fl = true;
		points[i].color = tmp;
		if ( fl ) ++tmp;
	}
		
//	d( cerr << "punkty: \n" );
//	for ( auto p : points )
//		d( cerr << p << '\n' );

	for ( int i = 0; i < points.size(); ++i )
		evs.push_back( Ev( 1, points[i].y, points[i].y, points[i].x, i ) );

	low.push_back( 0 );
	low.push_back( INF );
		
	for ( auto ev : evs )
	{
		low.push_back( ev.lo );
		low.push_back( ev.hi );
	}
	
	for ( auto p : points )
		low.push_back( p.y );
	
	sort( ALL( low ) );
	low.resize( unique( ALL( low ) ) - low.begin() ); 	

//	for ( int i : low )
//		d( cerr << i << ' ' );
//	d( cerr << '\n' );

	while ( rozm < low.size() )
		rozm <<= 1;
	
	tree.resize( rozm * 2 );	

	sort( ALL( evs ) );
	for ( auto ev : evs )
		proceed( ev );		

	dfs( 0 );

	for ( int i = 1; i <= n; ++i )
		cout << odp[i] << '\n';
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:188:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < points.size(); ++i )
                     ^
plahte.cpp:191:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if ( i + 1 < points.size() and points[i].color != points[i + 1].color )
              ^
plahte.cpp:201:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < points.size(); ++i )
                     ^
plahte.cpp:223:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while ( rozm < low.size() )
               ^
# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 12808 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 13380 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 199 ms 23640 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 339 ms 32128 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 326 ms 31076 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -