제출 #37673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37673		wasyl	Deda (COCI17_deda)	C++11	40 / 140	389 ms	14304 KiB

deda

#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';
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 140