oj.uz

Submission #37673

# Submission time Handle Problem Language Result Execution time Memory
37673 2017-12-26T21:13:33 Z wasyl Deda (COCI17_deda) C++11
40 / 140
 389 ms 14304 KB 
#include <set>
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
#define d(...) __VA_ARGS__
#define all(x) (x).begin(), (x).end()
#define eb(...) emplace_back(__VA_ARGS__)
using namespace std;using ll=long long;
template<class t>using V = vector< t >;

struct Ev
{
	bool typ;
	int nr, val, id;
	Ev( bool typ, int nr, int val, int id ) :
	typ( typ ), nr( nr ), val( val ), id( id ) {}
};

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

int n, q;
V< Ev > evs;
V< int > odp;

void foo ( int l, int p )
{
	int mid = ( l + p ) / 2;
	V< Ev > ilo;
	
	for ( int i = l; i <= mid; ++i )
		if ( evs[i].typ == false )	
			ilo.eb( evs[i] );
	for ( int i = mid + 1; i <= p; ++i )	
		if ( evs[i].typ == true )
			ilo.eb( evs[i] );
	set< int > S;
	S.insert( INT_MAX );
	sort( all( ilo ) );
	for ( auto& ev : ilo )
	{
		if ( ev.typ == false )
			S.insert( ev.nr );
		else
			odp[ev.id] = min( ( *S.lower_bound( ev.nr ) ), odp[ev.id] );
	}
	
	if ( mid > l )
	{
		foo( l, mid );
		foo( mid + 1, p );
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	odp.resize( q, INT_MAX );
	for ( int i = 0; i < q; ++i )
	{
		char r;
		bool typ; int nr, val;
		cin >> r;	
		typ = ( r == 'D' );
		cin >> val >> nr;
		evs.eb( typ, nr, val, i );
	}
	foo( 0, evs.size() - 1 );
	for ( int i = 0; i < evs.size(); ++i )
		if ( evs[i].typ )	
			cout << ( odp[i] == INT_MAX? -1 : odp[i] ) << '\n';
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < evs.size(); ++i )
                     ^

Subtask #1
40.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2184 KB Output is correct
2 Correct 0 ms 2184 KB Output is correct
3 Runtime error 3 ms 2524 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 219 ms 12220 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 389 ms 14304 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 376 ms 13500 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 369 ms 12988 KB Execution killed because of forbidden syscall writev (20)