Submission #3240184
Source Code Expand
#include<iostream> #include<vector> #include<algorithm> #include<functional> #include<queue> #include<stack> #include<set> #include<map> #include<unordered_map> #include<climits> #include<cstdlib> #include<cmath> #include<string> #include<iomanip> using namespace std; #define INF 1 << 29 #define LL long long int LL const MOD = 1000000007; template<typename T> class SegmentTree{ int n; int realsize; T initialvalue; vector<T> tree; public: SegmentTree(int size,T initial):realsize(size),initialvalue(initial){ n = 1; while(n < size)n *= 2; tree = vector<T>(2*n + 1,initial); } //1-indexed void insert(int i,T data){ int ind = n+i-1; tree[ind] = data; ind >>= 1; while(ind > 0){ tree[ind] = tree[ind*2] + tree[ind*2+1]; ind >>= 1; } } void add(int i,T data){ int ind = n+i-1; tree[ind] += data; ind >>= 1; while(ind > 0){ tree[ind] = tree[ind*2] + tree[ind*2+1]; ind >>= 1; } } T get(int l,int r){ if(l > realsize || r > realsize || l <= 0 || r <= 0)return initialvalue; l = n+l-1; r = n+r-1; if(l == r)return tree[l]; int prel = l; int prer = r; T lnum = tree[l]; T rnum = tree[r]; l >>= 1; r >>= 1; while(l != r){ if(l*2 == prel){ lnum += tree[l*2+1]; } if(r*2+1 == prer){ rnum += tree[r*2]; } prel = l; prer = r; l >>= 1; r >>= 1; } return lnum+rnum; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); LL n,k; cin >> n >> k; vector<LL> a(n+1); for(LL i = 1; i < n+1; i++){ cin >> a[i]; } vector<LL> sum(n+1,0); for(LL i = 1; i < n+1; i++){ sum[i] += sum[i-1] + a[i] - k; } vector<LL> cpy = sum; sort(sum.begin(),sum.end()); SegmentTree<LL> st(sum.size(),0); st.add(lower_bound(sum.begin(),sum.end(),0) - sum.begin() + 1,1); LL ans = 0; for(LL i = 1; i < n+1; i++){ auto itr = lower_bound(sum.begin(),sum.end(),cpy[i-1]); ans += sum.end() - itr; ans -= st.get(itr - sum.begin() + 1,sum.size()); auto itr2 = lower_bound(sum.begin(),sum.end(),cpy[i]); st.add(itr2 - sum.begin() + 1,1); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Meaningful Mean |
User | rtia1227 |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 2652 Byte |
Status | AC |
Exec Time | 88 ms |
Memory | 9088 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 | 1 ms | 256 KB |
a02 | AC | 1 ms | 256 KB |
a03 | AC | 1 ms | 256 KB |
b04 | AC | 1 ms | 256 KB |
b05 | AC | 50 ms | 9088 KB |
b06 | AC | 66 ms | 9088 KB |
b07 | AC | 81 ms | 9088 KB |
b08 | AC | 81 ms | 9088 KB |
b09 | AC | 69 ms | 9088 KB |
b10 | AC | 73 ms | 9088 KB |
b11 | AC | 1 ms | 256 KB |
b12 | AC | 1 ms | 256 KB |
b13 | AC | 30 ms | 3968 KB |
b14 | AC | 88 ms | 9088 KB |
b15 | AC | 50 ms | 9088 KB |
b16 | AC | 68 ms | 9088 KB |
b17 | AC | 86 ms | 9088 KB |
b18 | AC | 86 ms | 9088 KB |
b19 | AC | 67 ms | 9088 KB |
b20 | AC | 55 ms | 9088 KB |
b21 | AC | 47 ms | 9088 KB |
b22 | AC | 81 ms | 9088 KB |
b23 | AC | 79 ms | 9088 KB |