Submission #8635001


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, K, A[201010];
int sm[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 1, N + 1) cin >> A[i];

	if (K == 1) {
		cout << 0 << endl;
		return;
	}

	map<int, int> cnt;
	cnt[0] = 1;
	sm[0] = 0;

	rep(i, 1, N + 1) sm[i] = (sm[i - 1] + A[i]) % K;

	ll ans = 0;
	rep(R, 1, N + 1) {
		int x = (((sm[R] - R) % K) + K) % K;
		ans += cnt[x];
		cnt[x]++;
		if (0 <= R - K + 1) {
			int y = (((sm[R - K + 1] - (R - K + 1)) % K) + K) % K;
			cnt[y]--;

		}
	}
	cout << ans << endl;
}





Submission Info

Submission Time
Task E - Rem of Sum is Num
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1894 Byte
Status
Exec Time 128 ms
Memory 11264 KB

Test Cases

Set Name Score / Max Score Test Cases
sample 0 / 0 sample01, sample02, sample03
All 500 / 500 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 16 ms 1792 KB
few02 23 ms 1792 KB
few03 25 ms 1792 KB
hand01 1 ms 256 KB
hand02 21 ms 1024 KB
hand03 28 ms 1792 KB
hand04 24 ms 1792 KB
large01 104 ms 10240 KB
large02 116 ms 11136 KB
large03 111 ms 10880 KB
max01 73 ms 11264 KB
max02 77 ms 11264 KB
max03 128 ms 11264 KB
mid01 2 ms 256 KB
mid02 2 ms 384 KB
mid03 2 ms 256 KB
mid04 2 ms 256 KB
mid05 2 ms 256 KB
min01 38 ms 1408 KB
min02 35 ms 1408 KB
min03 39 ms 1408 KB
sample01 1 ms 256 KB
sample02 1 ms 256 KB
sample03 1 ms 256 KB
small01 1 ms 256 KB
small02 1 ms 256 KB
small03 1 ms 256 KB
small04 1 ms 256 KB
small05 1 ms 256 KB