Submission #3596012
Source Code Expand
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef long long ll;
ll n, k, m, ans, a[N], ne[N], fen[N], pre[N];
map < ll , int > h, hh;
map < ll , int > :: iterator it;
void up(int x, int y){
for(; x <= m; x += x&-x)
fen[x] += y;
}
int qu(int x){
int top = 0;
for(; x > 0; x -= x&-x)
top += fen[x];
return top;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("amk.txt", "w", stdout);
scanf("%lld %lld",&n ,&k);
for(int i = 1; i <= n; i++){
scanf("%lld",a + i);
pre[i] = pre[i - 1] + a[i];
}
for(int i = 0; i <= n; i++)
h[i*k - pre[i]]++;
for(it = h.begin(); it != h.end(); it++){
ne[++m] = it->st;
// cout << it->st << " " << m << endl;
hh[it->st] = m;
}
// cout << "amk" << endl;
up(hh[0], 1);
for(int i = 1; i <= n; i++){
int amk = hh[i*k - pre[i]];
ans += qu(m) - qu(amk - 1);
up(amk, 1);
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Meaningful Mean |
User |
ekrem |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1032 Byte |
Status |
AC |
Exec Time |
263 ms |
Memory |
39040 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:30:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&n ,&k);
^
./Main.cpp:32:22: 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 |
2 ms |
6400 KB |
a02 |
AC |
2 ms |
6400 KB |
a03 |
AC |
2 ms |
6400 KB |
b04 |
AC |
2 ms |
6400 KB |
b05 |
AC |
28 ms |
9984 KB |
b06 |
AC |
244 ms |
39040 KB |
b07 |
AC |
151 ms |
26624 KB |
b08 |
AC |
150 ms |
26624 KB |
b09 |
AC |
263 ms |
39040 KB |
b10 |
AC |
219 ms |
39040 KB |
b11 |
AC |
2 ms |
6400 KB |
b12 |
AC |
3 ms |
6528 KB |
b13 |
AC |
64 ms |
17920 KB |
b14 |
AC |
225 ms |
39040 KB |
b15 |
AC |
159 ms |
26624 KB |
b16 |
AC |
193 ms |
39040 KB |
b17 |
AC |
229 ms |
39040 KB |
b18 |
AC |
225 ms |
39040 KB |
b19 |
AC |
189 ms |
39040 KB |
b20 |
AC |
38 ms |
10112 KB |
b21 |
AC |
31 ms |
9984 KB |
b22 |
AC |
195 ms |
39040 KB |
b23 |
AC |
189 ms |
39040 KB |