oj.uz

Submission #936931

# Submission time Handle Problem Language Result Execution time Memory
936931 2024-03-03T04:16:42 Z william950615 Advertisement 2 (JOI23_ho_t2) C++14
0 / 100
 34 ms 4688 KB 

#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=0;
		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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 34 ms 4688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 34 ms 4688 KB Output isn't correct
3 Halted 0 ms 0 KB -