QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358405#6626. Real MountainsKiharaTouma0 2ms8276kbC++231.5kb2024-03-19 19:40:392024-03-19 19:40:39

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 19:40:39]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:8276kb
  • [2024-03-19 19:40:39]
  • 提交

answer

//qoj6626
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
void solve();int main(){ solve(); return 0; }

const int N = 1e6 + 10;
int n, a[N], b[N];
tuple<int, int, int> q[N*2];
ll ans;

ll Sum(int x, int y){
	return (ll)y * (y-1) / 2 - (ll)x * (x-1) / 2;
}
int qrl(int x, int mn){
	int ans = 2e9;
	for(int i = x; i >= 1; -- i){
		if(a[i] > mn){
			ans = min(ans, a[i]);
		}
	}
	return ans;
}
int qrr(int x, int mn){
	int ans = 2e9;
	for(int i = x; i <= n; ++ i){
		if(a[i] > mn){
			ans = min(ans, a[i]);
		}
	}
	return ans;
}

void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
		q[i] = { a[i], i, -1 };
	}
	int mx = 0;
	for(int i = 1; i <= n; ++ i){
		mx = max(mx, a[i]);
		b[i] = mx;
	}
	mx = 0;
	for(int i = n; i >= 1; -- i){
		mx = max(mx, a[i]);
		b[i] = min(b[i], mx);
		q[i+n] = { b[i], i, 1 };
	}
	sort(q + 1, q + n + n + 1);
	set<int> st;
	for(int i = 1; i < n + n; ++ i){
		if(get<2>(q[i]) == -1){
			st.insert(get<1>(q[i]));
		} else {
			st.erase(get<1>(q[i]));
		}
		if(get<0>(q[i]) != get<0>(q[i+1]) && st.size()){
			int fr = get<0>(q[i]), to = get<0>(q[i+1]);
			int l = *st.begin(), r = *st.rbegin(), k = st.size();
			int p = qrl(l, fr), q = qrr(r, fr);
			if(k == 1){
				ans += Sum(fr, to);
				ans += (p + q) * 1ll * (to - fr);
			} else {
				ans += (p + q + min(p, q) + k + k - 3) * 1ll * (to - fr);
				ans += 3 * (k - 1) * Sum(fr, to);
			}
		}
	}
	printf("%lld\n", ans);
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 3
Accepted
time: 0ms
memory: 8084kb

input:

3
29 9 9

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8116kb

input:

3
62 20 71

output:

7287

result:

ok 1 number(s): "7287"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7868kb

input:

10
72 33 22 22 13 49 53 57 72 85

output:

40403

result:

ok 1 number(s): "40403"

Test #4:

score: -3
Wrong Answer
time: 2ms
memory: 8276kb

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 97 97 97 97 9...

output:

49481200

result:

wrong answer 1st numbers differ - expected: '481053', found: '49481200'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%