oj.uz

Submission #37676

# Submission time Handle Problem Language Result Execution time Memory
37676 2017-12-26T21:44:53 Z wasyl Plahte (COCI17_plahte) C++11
160 / 160
 389 ms 31920 KB 
#include <vector>
#include <cstdio>
#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;
	scanf( "%d%d", &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;
		scanf( "%d%d%d%d", &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;
		scanf( "%d%d%d", &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';
		printf( "%d\n", odp[i] );
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:191:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < points.size(); ++i )
                     ^
plahte.cpp:194: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:204:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < points.size(); ++i )
                     ^
plahte.cpp:226:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while ( rozm < low.size() )
               ^
plahte.cpp:163:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf( "%d%d", &n, &m );
                         ^
plahte.cpp:171:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf( "%d%d%d%d", &x, &y, &x2, &y2 );
                                        ^
plahte.cpp:180:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf( "%d%d%d", &x, &y, &k );
                                ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 12604 KB Output is correct
2 Correct 113 ms 13396 KB Output is correct
3 Correct 0 ms 1944 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 13176 KB Output is correct
2 Correct 133 ms 12956 KB Output is correct
3 Correct 0 ms 1944 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 23444 KB Output is correct
2 Correct 206 ms 19900 KB Output is correct
3 Correct 0 ms 1944 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 31920 KB Output is correct
2 Correct 389 ms 31048 KB Output is correct
3 Correct 0 ms 1944 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 30868 KB Output is correct
2 Correct 366 ms 30084 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct