#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 32100;
const int K = 110;
const int PW = 20;
struct edge{
int x, y, cap, flow;
edge(int _x, int _y, int _c, int _f): x(_x), y(_y), cap(_c), flow(_f) {}
};
vector<edge> edges;
queue<int> q;
vector<int> g[N];
int ans = 0, s, t, n, m, k, dst[N], ptr[N], X[N], Y[N];
void add_edge(int x, int y, int cap){
g[x].PB(sz(edges));
edges.PB(edge(x, y, cap, 0));
g[y].PB(sz(edges));
edges.PB(edge(y, x, 0, 0));
}
bool bfs(){
fill(dst, dst + t + 1, oo);
dst[s] = 0;
while (sz(q)) q.pop();
q.push(s);
while (sz(q)){
int v = q.front(); q.pop();
for (int nm : g[v]){
edge u = edges[nm];
if (u.cap > u.flow && dst[u.y] > dst[v] + 1){
dst[u.y] = dst[v] + 1;
q.push(u.y);
}
}
}
return (dst[t] < oo);
}
int dfs(int v, int pshd){
if (pshd == 0) return 0;
if (v == t) return pshd;
for (; ptr[v] < sz(g[v]); ptr[v]++){
int nm = g[v][ptr[v]];
edge u = edges[nm];
if (dst[u.y] != dst[v] + 1) continue;
int nw = dfs(u.y, min(pshd, u.cap - u.flow));
if (nw){
edges[nm].flow += nw;
edges[nm ^ 1].flow -= nw;
return nw;
}
}
return 0;
}
bool ok(int l, int r){
if (r - l + 1 < m) return 0;
for (int i = 0; i <= t; i++)
g[i].clear();
edges.clear();
for (int i = 0; i < k; i++){
if (Y[i] < l || Y[i] > r) continue;
add_edge(X[i], m + Y[i], 1);
}
for (int i = 0; i < m; i++)
add_edge(s, i, 1);
for (int i = l; i <= r; i++)
add_edge(m + i, t, 1);
int flow = 0;
while (bfs()){
fill(ptr, ptr + t + 1, 0);
int pshd = dfs(s, oo);
while (pshd > 0){
flow += pshd;
pshd = dfs(s, oo);
}
}
return (flow == m);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < k; i++){
cin >> Y[i] >> X[i];
Y[i]--; X[i]--;
}
s = n + m;
t = n + m + 1;
for (int l = 0, r = 0; l < n; l++){
while (r < n && !ok(l, r))
r++;
if (r >= n) break;
ans += n - r;
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 17 |
Correct |
3 ms |
1148 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 19 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1144 KB |
Output is correct |
| 21 |
Correct |
4 ms |
1144 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1144 KB |
Output is correct |
| 23 |
Correct |
5 ms |
1272 KB |
Output is correct |
| 24 |
Correct |
5 ms |
1272 KB |
Output is correct |
| 25 |
Correct |
94 ms |
1528 KB |
Output is correct |
| 26 |
Correct |
87 ms |
1296 KB |
Output is correct |
| 27 |
Correct |
24 ms |
1144 KB |
Output is correct |
| 28 |
Correct |
20 ms |
1144 KB |
Output is correct |
| 29 |
Correct |
147 ms |
1976 KB |
Output is correct |
| 30 |
Correct |
122 ms |
1712 KB |
Output is correct |
| 31 |
Execution timed out |
1570 ms |
3136 KB |
Time limit exceeded |
| 32 |
Correct |
362 ms |
1892 KB |
Output is correct |
| 33 |
Correct |
102 ms |
1292 KB |
Output is correct |
| 34 |
Correct |
122 ms |
1424 KB |
Output is correct |
| 35 |
Incorrect |
69 ms |
1912 KB |
Output isn't correct |
| 36 |
Runtime error |
36 ms |
9552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 37 |
Execution timed out |
1568 ms |
3016 KB |
Time limit exceeded |
| 38 |
Incorrect |
318 ms |
2296 KB |
Output isn't correct |
| 39 |
Execution timed out |
1582 ms |
2116 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1575 ms |
2008 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1573 ms |
2392 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1563 ms |
2680 KB |
Time limit exceeded |
| 43 |
Execution timed out |
1560 ms |
3124 KB |
Time limit exceeded |
| 44 |
Execution timed out |
1577 ms |
3200 KB |
Time limit exceeded |
| 45 |
Execution timed out |
1565 ms |
2516 KB |
Time limit exceeded |
| 46 |
Runtime error |
30 ms |
4592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 47 |
Execution timed out |
1557 ms |
2920 KB |
Time limit exceeded |
| 48 |
Execution timed out |
1572 ms |
3400 KB |
Time limit exceeded |
| 49 |
Execution timed out |
1570 ms |
2548 KB |
Time limit exceeded |
| 50 |
Execution timed out |
1576 ms |
2344 KB |
Time limit exceeded |
