Submission #1883314
Source Code Expand
#include<iostream> #include <algorithm> using namespace std; struct node{ long long num; int id; int numx; }a[200007]; node b[200007]; long long tree[200007]; inline int lowbit(int x) { return (x & -x); } void add(int x, int v) { for (int i = x; i <= 200007; i += lowbit(i)) { tree[i] += v; } } long long get(int x) { long long sum = 0; for (int i = x; i ; i -= lowbit(i)) { sum += tree[i]; } return sum; } int cmp(node a,node b){ return a.num<b.num; } int cmp2(node a,node b){ return a.id<b.id; } int main() { ios::sync_with_stdio(0); int n, k; cin >> n >> k; b[0].num=a[0].num=0; for(int i = 1; i <= n; i++) { cin >> a[i].num; a[i].num-=k; a[i].id=i; b[i].num=b[i-1].num+a[i].num; b[i].id=i; } b[0].id=0; sort(b,b+1+n,cmp); int t=1; b[0].numx=1; for (int i = 1; i <=n ; ++i) { b[i].numx=b[i].num==b[i-1].num?t:++t; } sort(b,b+1+n,cmp2); int sum=0; for (int i = 0; i <=n ; ++i) { //cout<<a[i].num<<" "<<b[i].num<<" "<<b[i].numx<<endl; } for(int i=n;i>=0;i--){ // cout<<i<<" "<<b[i].numx-1<<" "<<get(n+1)<<" "<<get(b[i].numx-1)<<endl; sum+=get(n+1)-get(b[i].numx-1); add(b[i].numx,1); } cout << sum << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Meaningful Mean |
User | vjudge5 |
Language | Bash (GNU bash v4.3.11) |
Score | 0 |
Code Size | 1177 Byte |
Status | RE |
Exec Time | 188 ms |
Memory | 21300 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | RE | 188 ms | 21300 KB |
a02 | RE | 50 ms | 7476 KB |
a03 | RE | 50 ms | 7480 KB |
b04 | RE | 50 ms | 7512 KB |
b05 | RE | 50 ms | 7484 KB |
b06 | RE | 50 ms | 7480 KB |
b07 | RE | 50 ms | 7500 KB |
b08 | RE | 50 ms | 7488 KB |
b09 | RE | 50 ms | 7484 KB |
b10 | RE | 50 ms | 7508 KB |
b11 | RE | 50 ms | 7472 KB |
b12 | RE | 50 ms | 7488 KB |
b13 | RE | 50 ms | 7476 KB |
b14 | RE | 50 ms | 7480 KB |
b15 | RE | 50 ms | 7472 KB |
b16 | RE | 50 ms | 7476 KB |
b17 | RE | 50 ms | 7484 KB |
b18 | RE | 50 ms | 7488 KB |
b19 | RE | 50 ms | 7484 KB |
b20 | RE | 50 ms | 7488 KB |
b21 | RE | 50 ms | 7504 KB |
b22 | RE | 50 ms | 7484 KB |
b23 | RE | 50 ms | 7512 KB |