Submission #2208918
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{ vector<ll>bit; int n=1; void init(ll m){ while(n<m){ n*=2; } bit.resize(n+1); } int sum(ll i){ ll s=0; while(i>0){ s+=bit[i]; i-=i&-i; } return s; } void add(ll i,ll x){ while(i<=n){ bit[i]+=x; i+=i&-i; } } }; ll b[200010]; map<ll,ll> m; void compress(ll n){ vector<ll> v; for(int i=0;i<=n;i++){ v.push_back(b[i]); } sort(v.begin(),v.end()); for(ll i=0;i<(ll)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; for(ll i=1;i<=n;i++){ scanf("%lld",&a[i]); sum+=a[i]; b[i]=sum-i*k; } compress(n); BIT bit; bit.init(n+1); ll ans=0; for(int i=0;i<=n;i++){ ll 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 | 600 |
Code Size | 1272 Byte |
Status | AC |
Exec Time | 165 ms |
Memory | 18004 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:52:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld",&a[i]); ^
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 | 1 ms | 256 KB |
a02 | AC | 1 ms | 256 KB |
a03 | AC | 1 ms | 256 KB |
b04 | AC | 1 ms | 256 KB |
b05 | AC | 37 ms | 5492 KB |
b06 | AC | 135 ms | 17876 KB |
b07 | AC | 121 ms | 11732 KB |
b08 | AC | 123 ms | 11604 KB |
b09 | AC | 152 ms | 17876 KB |
b10 | AC | 143 ms | 17876 KB |
b11 | AC | 1 ms | 256 KB |
b12 | AC | 1 ms | 384 KB |
b13 | AC | 45 ms | 6848 KB |
b14 | AC | 158 ms | 18004 KB |
b15 | AC | 101 ms | 11732 KB |
b16 | AC | 143 ms | 17876 KB |
b17 | AC | 159 ms | 17876 KB |
b18 | AC | 165 ms | 17876 KB |
b19 | AC | 134 ms | 17876 KB |
b20 | AC | 45 ms | 5492 KB |
b21 | AC | 39 ms | 5492 KB |
b22 | AC | 150 ms | 17876 KB |
b23 | AC | 150 ms | 17876 KB |