Submission #936932

#	Time	Username	Problem	Language	Result	Execution time	Memory
936932		william950615	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	154 ms	26608 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mkp make_pair
#define MEM(x) memset(x,0,sizeof(x))
#define ALL(x) begin(x), end(x)
#define PH push
#define PB push_back
#define REP(i,N) for( int i = 0; i <(N); ++i )
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i )

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
template<typename T>
using V = vector<T>;

void solve() {
	int N; cin >> N;
	V<pii> vc(N);
	for( auto &i : vc ) cin >> i.F >> i.S;
	sort( ALL(vc) );

	V<pii> seg(N);
	auto FindLeft = [&]() {
		V<int> val(N);
		REP(i,N) val[ i ] = vc[i].S - vc[i].F;
		V<pii> stk;

		REP(i,N) {
			int minl = i;
			while( !stk.empty() && stk.back().F <= val[i] ) {
				minl = stk.back().S;
				stk.pop_back();
			}
			seg[ i ].F = minl;
			stk.PB( mkp( val[i], minl) );
		}
	};
	auto FindRight = [&]() {
		V<int> val(N);
		REP(i,N) val[i] = vc[i].S + vc[i].F;
		V<pii> stk;
		for( int i = N-1; i >= 0; --i ) {
			int maxr = i;
			while( !stk.empty() && stk.back().F <= val[i] ) {
				maxr = stk.back().S;
				stk.pop_back();
			}
			seg[ i ].S = maxr;
			stk.PB( mkp(val[i],maxr) );
		}
	};

	FindLeft();
	FindRight();

	auto output = [&]() {
		for( auto &i : seg ) {
			cout << i.F << ' ' << i.S << '\n';
		}
	};
	//output();

	auto GetMaxSize = [&]() {
		int ans = 0;
		sort( ALL(seg) );
		int r=-1;
		int pos=0;
		for( ; ; ) {
			int mx = r+1;
			while( pos<seg.size() && seg[pos].F<=r+1 ) {
				mx = max( seg[pos].S, mx );
				++pos;
			}
			++ans;
			r=mx;
			//fprintf(stderr, "r:(%d)\n", r );
			if( r == N-1 ) break;
		}
		return ans;
	};
	int ans = GetMaxSize();
	cout << ans << '\n';
}

int main () {
	int T=1;
#ifdef LOCAL
	freopen( "input.txt", "r", stdin );
	freopen( "output.txt", "w", stdout );
	cin >> T;
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
	while(T--) solve();
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:75:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    while( pos<seg.size() && seg[pos].F<=r+1 ) {
      |           ~~~^~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:61:7: warning: variable 'output' set but not used [-Wunused-but-set-variable]
   61 |  auto output = [&]() {
      |       ^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31