Submission #8622850


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef long long ll;
const int maxn = 200005;
const int mod = 1000000007;

ll s[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  unordered_map<int,int>mp;
  int n,K;
  cin>>n>>K;
  mp[0] = 1;
  ll sum = 0,ret = 0;
  for(int i=1;i<=n;i++){
    if(i>=K){
      mp[s[i-K]%K-(i-K)]--;
    }
    int x;
    cin>>x;
    sum+=x;
    s[i] = sum;
    int tt = sum%K-i;
    //bug2(i,tt)
    ret+=mp[tt];
    tt = sum%K - i + K;
    ret+=mp[tt];
    //if(i==5)bug2(tt,mp[tt]);
    mp[sum%K-i]++;
  }
  if(K==1)ret=0;
  cout<<ret<<endl;
  return 0;
}

Submission Info

Submission Time
Task E - Rem of Sum is Num
User suiyuan2009
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1175 Byte
Status AC
Exec Time 171 ms
Memory 18420 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 29
Set Name Test Cases
sample sample01, sample02, sample03
All few01, few02, few03, hand01, hand02, hand03, hand04, large01, large02, large03, max01, max02, max03, mid01, mid02, mid03, mid04, mid05, min01, min02, min03, sample01, sample02, sample03, small01, small02, small03, small04, small05
Case Name Status Exec Time Memory
few01 AC 44 ms 1792 KB
few02 AC 73 ms 1792 KB
few03 AC 78 ms 1792 KB
hand01 AC 1 ms 256 KB
hand02 AC 116 ms 10056 KB
hand03 AC 117 ms 9672 KB
hand04 AC 92 ms 1792 KB
large01 AC 148 ms 17140 KB
large02 AC 171 ms 18292 KB
large03 AC 156 ms 17908 KB
max01 AC 147 ms 18420 KB
max02 AC 148 ms 18420 KB
max03 AC 136 ms 18420 KB
mid01 AC 2 ms 384 KB
mid02 AC 3 ms 384 KB
mid03 AC 3 ms 384 KB
mid04 AC 2 ms 384 KB
mid05 AC 3 ms 384 KB
min01 AC 85 ms 6308 KB
min02 AC 81 ms 6052 KB
min03 AC 90 ms 8356 KB
sample01 AC 1 ms 256 KB
sample02 AC 1 ms 256 KB
sample03 AC 1 ms 256 KB
small01 AC 1 ms 256 KB
small02 AC 1 ms 256 KB
small03 AC 1 ms 256 KB
small04 AC 1 ms 256 KB
small05 AC 1 ms 256 KB