Submission #3235618
Source Code Expand
n,k = (int(i) for i in input().split()) a = [int(input())-k for i in range(n)] b = [[0,0]] for i in range(n): b.append([b[-1][0]+a[i],i+1]) b.sort() num,c = 1,[[b[0][1],1]] for i in range(1,n+1): if b[i][0]!=b[i-1][0]: num+=1 c.append([b[i][1],num]) c,d,ans = sorted(c),[0]*(n+2),0 def add(i): while i<=n+1: d[i] += 1 i += i & -i def get(i): s = 0 while i: s += d[i] i -= i & -i return s for i,j in c: ans+=get(j) add(j) print(ans)
Submission Info
Submission Time | |
---|---|
Task | E - Meaningful Mean |
User | Clamperl |
Language | Python (3.4.3) |
Score | 600 |
Code Size | 470 Byte |
Status | AC |
Exec Time | 1971 ms |
Memory | 76104 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 17 ms | 3064 KB |
a02 | AC | 17 ms | 3064 KB |
a03 | AC | 18 ms | 3064 KB |
b04 | AC | 17 ms | 3064 KB |
b05 | AC | 1570 ms | 55068 KB |
b06 | AC | 1475 ms | 67736 KB |
b07 | AC | 1555 ms | 72000 KB |
b08 | AC | 1611 ms | 72108 KB |
b09 | AC | 1639 ms | 74824 KB |
b10 | AC | 1577 ms | 75248 KB |
b11 | AC | 17 ms | 3064 KB |
b12 | AC | 23 ms | 3316 KB |
b13 | AC | 604 ms | 29044 KB |
b14 | AC | 1969 ms | 75584 KB |
b15 | AC | 1538 ms | 65780 KB |
b16 | AC | 1631 ms | 75168 KB |
b17 | AC | 1971 ms | 75232 KB |
b18 | AC | 1957 ms | 75584 KB |
b19 | AC | 1553 ms | 76104 KB |
b20 | AC | 1865 ms | 68960 KB |
b21 | AC | 1555 ms | 62748 KB |
b22 | AC | 1568 ms | 75148 KB |
b23 | AC | 1586 ms | 75160 KB |