QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55236 | #1762. Low Effort League | abdelrahman001# | WA | 2ms | 3648kb | C++ | 1.4kb | 2022-10-12 20:14:30 | 2022-10-12 20:14:34 |
Judging History
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'