QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358433#6626. Real MountainsKiharaTouma3 2ms8312kbC++231.5kb2024-03-19 19:51:502024-03-19 19:51:51

Judging History

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

  • [2024-03-19 19:51:51]
  • 评测
  • 测评结果:3
  • 用时:2ms
  • 内存:8312kb
  • [2024-03-19 19:51:50]
  • 提交

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;
const ll P = 1e6 + 3;
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);
			}
			ans %= P;
		}
	}
	printf("%lld\n", ans);
}

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 1ms
memory: 7912kb

input:

3
29 9 9

output:

0

result:

ok 1 number(s): "0"

Test #2:

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

input:

3
62 20 71

output:

7287

result:

ok 1 number(s): "7287"

Test #3:

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

input:

10
72 33 22 22 13 49 53 57 72 85

output:

40403

result:

ok 1 number(s): "40403"

Test #4:

score: 0
Accepted
time: 2ms
memory: 8240kb

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:

481053

result:

ok 1 number(s): "481053"

Test #5:

score: 0
Accepted
time: 2ms
memory: 8024kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 2ms
memory: 8128kb

input:

5000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

12595

result:

ok 1 number(s): "12595"

Test #7:

score: 0
Accepted
time: 2ms
memory: 8056kb

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 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 100 100 100 100 100 100 100 100...

output:

299

result:

ok 1 number(s): "299"

Test #8:

score: 0
Accepted
time: 2ms
memory: 8284kb

input:

5000
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

224232

result:

ok 1 number(s): "224232"

Test #9:

score: 0
Accepted
time: 2ms
memory: 8052kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4...

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

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 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 99 99 99 99 9...

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 2ms
memory: 8312kb

input:

5000
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4...

output:

499735

result:

ok 1 number(s): "499735"

Test #12:

score: 0
Accepted
time: 2ms
memory: 8244kb

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 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 99 99 99 99 9...

output:

461407

result:

ok 1 number(s): "461407"

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #13:

score: 0
Wrong Answer
time: 2ms
memory: 8244kb

input:

5000
37 39 93 78 85 71 59 21 57 96 61 59 23 16 57 90 13 59 85 70 62 67 78 97 16 60 8 48 28 53 4 24 1 97 97 98 57 87 96 91 74 54 100 76 86 86 46 39 100 57 70 76 73 55 84 93 64 6 84 39 75 94 30 15 3 31 11 34 27 10 6 81 30 76 60 9 4 47 1 88 17 71 61 30 19 10 4 57 79 37 22 74 84 8 91 58 15 45 7 98 32 46...

output:

217081

result:

wrong answer 1st numbers differ - expected: '216624', found: '217081'

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:

100%
Accepted

Dependency #2:

0%