oj.uz

Submission #792491

# Submission time Handle Problem Language Result Execution time Memory
792491 2023-07-25T05:49:48 Z 박상훈(#10052) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 13 ms 24404 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef long long ll;

constexpr ll INF = 4e18;

int n;
ll a[1001000], b[1001000];
vector<array<int, 2>> Ev[1001000];

struct Seg{
	ll tree[2002000];
	int sz;

	void init(int n){
		sz = n;
		for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
		for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
	}

	void update(int p, ll x){
		p += sz;
		tree[p] = x;
		for (p>>=1;p;p>>=1) tree[p] = min(tree[p<<1], tree[p<<1|1]);
	}

	ll query(int l, int r){
		++r;
		ll ret = INF;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret = min(ret, tree[l++]);
			if (r&1) ret = min(ret, tree[--r]);
		}

		return ret;
	}
}tree;

void genB(){
	int idx = max_element(a+1, a+n+1) - a;
	
	int cur = 0;
	for (int i=1;i<=idx;i++){
		if (cur <= a[i]){
			b[i] = a[i];
			cur = a[i];
		}

		else b[i] = cur;
	}

	cur = 0;
	for (int i=n;i>=idx;i--){
		if (cur <= a[i]){
			b[i] = a[i];
			cur = a[i];
		}

		else b[i] = cur;
	}
}

ll rans;
int cnt;
void dfs(vector<int> A, ll cur){
	cnt++;
	if (cnt > 1e7) {rans = -1; return;}
	// for (auto &x:A) printf("%d ", x);
	// printf("-> %lld\n", cur);

	int idx = max_element(A.begin(), A.end()) - A.begin();
	bool flag = 1;
	for (int i=0;i<idx;i++) if (A[i] > A[i+1]) flag = 0;
	for (int i=(int)A.size()-1;i>idx;i--) if (A[i] > A[i-1]) flag = 0;

	if (flag){
		// printf("ok cur = %lld\n", cur);
		rans = min(rans, cur);
		return;
	}

	for (int i=0;i<(int)A.size();i++){
		for (int j=i+1;j<(int)A.size();j++){
			for (int k=j+1;k<(int)A.size();k++){
				cnt++;
				if (cnt > 1e7) {rans = -1; return;}

				if (A[i] > A[j] && A[j] < A[k]){
					cur += A[i] + A[j] + A[k];
					A[j]++;

					dfs(A, cur);

					A[j]--;
					cur -= A[i] + A[j] + A[k];

				}

				// if (i==0 && j==1 && k==6) printf("ok %d %d %d\n", A[i], A[j], A[k]);
			} 
		}
	}
}

ll naive(){
	cnt = 0;
	vector<int> A;
	for (int i=1;i<=n;i++) A.push_back(a[i]);

	rans = INF;
	dfs(A, 0);
	
	return rans;
}

ll solve(){
	a[0] = INF;

	int H = *max_element(a+1, a+n+1);
	for (int i=1;i<=H;i++) Ev[i].clear();

	// scanf("%d", &n);
	// for (int i=1;i<=n;i++) scanf("%lld", a+i);

	// printf("%lld\n", naive());

	genB();
	
	for (int i=1;i<=n;i++){
		Ev[a[i]].push_back({0, i});
		Ev[b[i]].push_back({1, i});
	}

	
	multiset<int> st;
	tree.init(n+1);
	ll ans = 0;

	for (int i=1;i<=H;i++){
		sort(Ev[i].begin(), Ev[i].end());

		for (auto &[typ, pos]:Ev[i]){
			if (typ==0){
				tree.update(pos, INF);
				st.insert(pos);
			}

			else{
				st.erase(st.find(pos));
			}
		}

		int cnt = st.size();
		if (cnt==0) continue;

		int s = *st.begin(), e = *st.rbegin();
		ll p0 = tree.query(1, s-1), pk = tree.query(e+1, n), p = tree.query(1, n);

		// printf("\n%d -> %d:\n", i, i+1);
		// for (auto &x:st) printf("%d ", x);
		// printf("\n");
		// printf(" ok %lld %lld %lld\n", p0, pk, p);

		assert(p0 < INF && pk < INF && p < INF);
		if (cnt >= 2) ans += p0 + pk + p + (ll)(i+1) * (cnt*2 - 3) + (ll)i*cnt;
		else ans += p0 + pk + i;
	}

	return ans;
}

mt19937 seed(1557);
uniform_int_distribution<int> rng(0, 2147483647);
int getrand(int l, int r){return rng(seed) % (r-l+1) + l;}

void gen(){
	n = getrand(1, 10);
	for (int i=1;i<=n;i++) a[i] = getrand(1, 10);
}

void stress(int tc){
	printf("--------------------------------------\n");
	printf("Stress #%d\n", tc);
	gen();

	printf("Input:\n");
	printf("%d\n", n);
	for (int i=1;i<=n;i++) printf("%lld ", a[i]);
	printf("\n");

	ll ans = naive();
	ll out = solve();
	printf("Answer: %lld\n", ans);
	printf("Output: %lld\n", out);

	assert(ans==out || ans==-1);
}

signed main(){
	// for (int i=1;;i++) stress(i);

	scanf("%lld", &n);
	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	printf("%lld\n", solve());
}

Compilation message

Main.cpp: In function 'void stress(long long int)':
Main.cpp:185:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  185 |  printf("Stress #%d\n", tc);
      |                  ~^     ~~
      |                   |     |
      |                   int   long long int
      |                  %lld
Main.cpp:189:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  189 |  printf("%d\n", n);
      |          ~^     ~
      |           |     |
      |           int   long long int
      |          %lld
Main.cpp: In function 'int main()':
Main.cpp:204:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp:205:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24404 KB Output isn't correct
5 Halted 0 ms 0 KB -