QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55236#1762. Low Effort Leagueabdelrahman001#WA 2ms3648kbC++1.4kb2022-10-12 20:14:302022-10-12 20:14:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 20:14:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3648kb
  • [2022-10-12 20:14:30]
  • 提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
int r, a[N], who[N << 2];
ll sum[N << 2];
ll get(int x, int y) {
	if(a[y] < a[x])
		return 0;
	return 1ll * (a[y] - a[x]) * (a[y] - a[x]);
}
void solve(int node, int s, int e) {
	if(s == e) {
		who[node] = s;
		sum[node] = 0;
		return;
	}
	int mid = s + e >> 1;
	solve(node << 1, s, mid);
	solve(node << 1 | 1, mid + 1, e);
	int left_winner = who[node << 1];
	int right_winner = who[node << 1 | 1];
	if(s == 1) {
		who[node] = 1;
		sum[node] = get(left_winner, right_winner);
	} else {
		if(a[left_winner] < a[1])
			who[node] = right_winner;
		else if(a[right_winner] < a[1])
			who[node] = left_winner;
		else {
			if(a[left_winner] > a[right_winner]) {
				who[node] = right_winner;
				sum[node] = get(right_winner, left_winner);
			} else {
				who[node] = left_winner;
				sum[node] = get(left_winner, right_winner);
			}
		}
	}
	sum[node] += sum[node << 1] + sum[node << 1 | 1];
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> r;
    for(int i = 1;i <= (1 << r);i++)
		cin >> a[i];
	solve(1, 1, (1 << r));
	cout << sum[1];
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3648kb

input:

3
77 64 99 28 15 16 76 13

output:

484

result:

ok single line: '484'

Test #2:

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

input:

5
50 10 30 20 90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 40

output:

1600

result:

ok single line: '1600'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3548kb

input:

7
442 77 280 657 4 262 285 147 294 50 290 664 36 563 440 807 687 18 65 931 989 387 567 46 550 1040 166 955 15 493 33 362 451 514 245 922 709 20 542 47 326 21 446 258 196 124 825 237 141 384 626 999 303 897 276 517 164 439 848 492 1044 114 398 692 417 150 877 201 267 3 197 19 91 148 543 603 215 83 17...

output:

3362590

result:

wrong answer 1st lines differ - expected: '774858', found: '3362590'