Submission #2208759
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> P; const ll MOD=10000; const ll INF=1000000000; const int MAX=100001; const double EPS=1e-10; using namespace std; struct BIT{ int bit[200010]; int n; int sum(int i){ int s=0; while(i>0){ s+=bit[i]; i-=i&-i; } return s; } void add(int i,int x){ while(i<=n){ bit[i]+=x; i+=i&-i; } } }; ll b[200010]; map<ll,int> m; void compress(int n){ vector<int> v; for(int i=0;i<=n;i++){ v.push_back(b[i]); } sort(v.begin(),v.end()); for(int i=0;i<(int)v.size();i++){ m[v[i]]=i+1; } } int main() { int n;ll k;ll a[200010]; cin>>n>>k; ll sum=0; b[0]=0; m[0]=0; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; b[i+1]=sum-(i+1)*k; } compress(n); BIT bit; bit.n=n+1; int ans=0; for(int i=0;i<=n;i++){ int x=m[b[i]]; ans+=bit.sum(x); bit.add(x,1); } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | E - Meaningful Mean |
User | TAISA_ |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1182 Byte |
Status | WA |
Exec Time | 2108 ms |
Memory | 18660 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 | AC | 2 ms | 384 KB |
a02 | WA | 1 ms | 2304 KB |
a03 | AC | 1 ms | 256 KB |
b04 | AC | 1 ms | 256 KB |
b05 | WA | 91 ms | 5240 KB |
b06 | WA | 219 ms | 16628 KB |
b07 | TLE | 2104 ms | 10356 KB |
b08 | TLE | 2104 ms | 10356 KB |
b09 | WA | 215 ms | 16628 KB |
b10 | TLE | 2104 ms | 18660 KB |
b11 | WA | 2 ms | 2304 KB |
b12 | TLE | 2103 ms | 2304 KB |
b13 | TLE | 2104 ms | 6136 KB |
b14 | TLE | 2104 ms | 16628 KB |
b15 | WA | 137 ms | 10356 KB |
b16 | TLE | 2104 ms | 16628 KB |
b17 | TLE | 2104 ms | 16628 KB |
b18 | TLE | 2104 ms | 16628 KB |
b19 | TLE | 2104 ms | 16628 KB |
b20 | TLE | 2104 ms | 4472 KB |
b21 | TLE | 2104 ms | 4472 KB |
b22 | TLE | 2104 ms | 16628 KB |
b23 | TLE | 2108 ms | 16628 KB |