提出 #8635001


ソースコード 拡げる

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;
}





提出情報

提出日時
問題 E - Rem of Sum is Num
ユーザ hamayanhamayan
言語 C++14 (GCC 5.4.1)
得点 500
コード長 1894 Byte
結果
実行時間 128 ms
メモリ 11264 KB

テストケース

セット名 得点 / 配点 テストケース
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
ケース名 結果 実行時間 メモリ
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