QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55236#1762. Low Effort Leagueabdelrahman001#WA 2ms3648kbC++1.4kb2022-10-12 20:14:302022-10-12 20:14:34

Judging History

This is the latest submission verdict.

  • [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]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3648kb
  • [2022-10-12 20:14:30]
  • Submitted

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


詳細信息

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'