| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 37675 |
2017-12-26T21:39:10 Z |
wasyl |
Plahte (COCI17_plahte) |
C++11 |
|
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 |
- |
