Submission #523662

#TimeUsernameProblemLanguageResultExecution timeMemory
523662boykutMarriage questions (IZhO14_marriage)C++14
66 / 100
879 ms262148 KiB
#include <bits/stdc++.h> using namespace std; char dp[2002][30003]; int pref[2002][30003]; int n, m, k; int check(int l, int r) { if (r - l + 1 < m) return 0; for (int j = 1; j <= m; j++) { if (pref[j][r] - pref[j][l-1] == 0) return 0; } return 1; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 0; i < k; i++) { int a, b; cin >> a >> b; dp[b][a] = 1; } for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) { pref[j][i] = pref[j][i-1] + dp[j][i]; } } long long ans = 0; for (int l = 1, r = 1; l <= n; l++) { while (r <= n && !check(l, r)) r++; if (r <= n) { ans += n - r + 1; } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...