Submission #8631780


Source Code Expand

Copy
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n,k;
	std::cin >> n >> k;
	std::vector<int> a(n);
	rep(i,n) {
		std::cin >> a[i];
		a[i]-=1;
		a[i]%=k;
	}
	std::vector<int> ac(n+1,0);
	rep(i,n) ac[i+1] = (ac[i] + a[i])%k;
	debug(ac);
	int count = 0;
	// from the back count the numbers
	std::map<int,std::vector<int> > map;
	for(int i=n;i>=0;i--) {
		int x=std::lower_bound(map[ac[i]].rbegin(),map[ac[i]].rend(),i+k)-map[ac[i]].rbegin();
		debug(i,x,ac[i],map[ac[i]]);
		count+=x;
		map[ac[i]].emplace_back(i);
	}
	print(count);
	return 0;
}

Submission Info

Submission Time
Task E - Rem of Sum is Num
User zln
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1289 Byte
Status AC
Exec Time 289 ms
Memory 25216 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 47 ms 5492 KB
few02 AC 73 ms 5108 KB
few03 AC 77 ms 4968 KB
hand01 AC 1 ms 256 KB
hand02 AC 92 ms 5492 KB
hand03 AC 93 ms 5108 KB
hand04 AC 95 ms 5492 KB
large01 AC 215 ms 23040 KB
large02 AC 239 ms 25216 KB
large03 AC 229 ms 24320 KB
max01 AC 201 ms 25216 KB
max02 AC 201 ms 25216 KB
max03 AC 289 ms 25216 KB
mid01 AC 2 ms 384 KB
mid02 AC 3 ms 384 KB
mid03 AC 3 ms 384 KB
mid04 AC 3 ms 384 KB
mid05 AC 3 ms 384 KB
min01 AC 87 ms 4352 KB
min02 AC 83 ms 4096 KB
min03 AC 92 ms 4480 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 2 ms 256 KB
small04 AC 1 ms 256 KB
small05 AC 1 ms 256 KB