oj.uz

Submission #792479

# Submission time Handle Problem Language Result Execution time Memory
792479 2023-07-25T05:24:26 Z 박상훈(#10052) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 13 ms 24276 KB 
#include <bits/stdc++.h>

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

int main(){
	a[0] = INF;

	scanf("%d", &n);
	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	genB();
	
	for (int i=1;i<=n;i++){
		Ev[a[i]].push_back({0, i});
		Ev[b[i]].push_back({1, i});
	}

	int H = *max_element(a+1, a+n+1);
	set<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;
	}

	printf("%lld\n", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:68:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 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 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 13 ms 24276 KB Output isn't correct
5 Halted 0 ms 0 KB -