oj.uz

Submission #37674

# Submission time Handle Problem Language Result Execution time Memory
37674 2017-12-26T21:24:37 Z wasyl Deda (COCI17_deda) C++11
140 / 140
 416 ms 14100 KB 
#include <set>
#include <vector>
#include <cstdio>
#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;
	scanf( "%d%d", &n, &q );
	odp.resize( q, INT_MAX );
	for ( int i = 0; i < q; ++i )
	{
		char r;
		bool typ; int nr, val;
//		cin >> r;	
		scanf( " %c", &r );
		typ = ( r == 'D' );
//		cin >> val >> nr;
		scanf( "%d%d", &val, &nr );
		evs.eb( typ, nr, val, i );
	}
	foo( 0, (int)evs.size() - 1 );
	for ( int i = 0; i < evs.size(); ++i )
		if ( evs[i].typ )
		{
//			cout << ( odp[i] == INT_MAX? -1 : odp[i] ) << '\n';
			printf("%d\n", ( odp[i] == INT_MAX? -1 : odp[i] ) );
		}
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < evs.size(); ++i )
                     ^
deda.cpp:64:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf( "%d%d", &n, &q );
                         ^
deda.cpp:71:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf( " %c", &r );
                     ^
deda.cpp:74:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf( "%d%d", &val, &nr );
                             ^

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1936 KB Output is correct
2 Correct 0 ms 1936 KB Output is correct
3 Correct 6 ms 2324 KB Output is correct
4 Correct 279 ms 12016 KB Output is correct
5 Correct 416 ms 14100 KB Output is correct
6 Correct 399 ms 13296 KB Output is correct
7 Correct 386 ms 12784 KB Output is correct