oj.uz

답안 #684646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684646 2023-01-22T09:02:42 Z pragmatist Money (IZhO17_money) C++17
0 / 100
 12 ms 15960 KB 
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;

const int N = (int)1e6 + 7; // make sure this is right
const int M = (int)1e7 + 7;
const int inf = (int)2e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)1e9 + 7; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

int n, a[N], dp[N], p[N];
int timer, tree[N], t[M], L[M], R[M], lim = 1e6;

void build(int v, int tl, int tr) {
	if(tl == tr) {
		return;
	}
	int mid = (tl + tr) >> 1;
	L[v] = ++timer;
	build(L[v], tl, mid);
	R[v] = ++timer;
	build(R[v], mid + 1, tr);
}

void upd(int prev, int v, int tl, int tr, int id) {
	if(tl == tr) {
		t[v] = t[prev] + 1;
		return;
	}
	int mid = (tl + tr) >> 1;
	if(id <= mid) {
		L[v] = ++timer;
		R[v] = R[prev];
		upd(L[prev], L[v], tl, mid, id); 
	} else {
		R[v] = ++timer;
		L[v] = L[prev];
		upd(R[prev], R[v], mid + 1, tr, id);
	}
	t[v] = t[L[v]] + t[R[v]];
} 

int get(int v, int tl, int tr, int id) {
	if(tl == tr) {
		return tl;
	}	
	int mid = (tl + tr) >> 1;
	if(t[L[v]] >= mid) return get(L[v], tl, mid, id);
	else return get(R[v], mid + 1, tr, id - t[L[v]]);
}

int get(int i, int j) {	
	return get(tree[i], 1, lim, j);
}

void solve() {
	cin >> n;
	tree[0] = ++timer;
	build(1, 1, lim);
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		tree[i] = ++timer;
		upd(tree[i - 1], tree[i], 1, lim, a[i]);
		if(i > 1) p[i] = p[i - 1] + (a[i - 1] <= a[i]);
	}
	int j = 1;
	for(int i = 1; i <= n; ++i) {
	    dp[i] = inf;
	    while(j <= i) {
	    	if(p[i] - p[j] != i - j) {
	    	    j++;
	    		continue;
	    	}
        	bool can = (a[j] >= get(j - 1, j - 1) || a[i] <= get(j - 1, 1));
        	
        	int l = 1, r = j - 2, k = -1;
        	while(l <= r) {
        		int mid = (l + r) >> 1;
        		if(a[i] <= get(j - 1, mid + 1)) {
        			k = mid;
        			r = mid - 1;
        		} else {
        			l = mid + 1;
        		}
        	}
        	if(k != -1) {
        		can |= (a[j] >= get(j - 1, k));
        	}
        	if(can) {
        		dp[i] = min(dp[i], dp[j - 1] + 1);
        		break;
        	} else {
        		j++;
        	}
		}				
	}
	cout << dp[n];
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15956 KB Output is correct
2 Incorrect 10 ms 15960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15956 KB Output is correct
2 Incorrect 10 ms 15960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15956 KB Output is correct
2 Incorrect 10 ms 15960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15956 KB Output is correct
2 Incorrect 10 ms 15960 KB Output isn't correct
3 Halted 0 ms 0 KB -