Submission #401364
Source Code Expand
#include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #include <functional> #include <iostream> #include <iomanip> #include <iterator> #include <map> #include <queue> #include <set> #include <sstream> #include <utility> #include <vector> using namespace std; typedef long long Long; #define Whole(xs) xs.begin(), xs.end() template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; os << "[" << vs[0]; for (int i = 1; i < vs.size(); i++) os << " " << vs[i]; return os << "]"; } const int IINF = 1<<28; const Long LINF = 1LL<<56; #define INF IINF struct P { int y, x; P(int y=0, int x=0) : y(y), x(x) {} }; int R, C, K; int N; vector<P> F; vector< vector<int> > sR; void Input() { cin >> R >> C >> K; cin >> N; F.clear(); F.resize(N); sR.clear(); sR.resize(R); for (int i = 0; i < N; i++) { int y, x; cin >> y >> x; y--; x--; F[i].y = y; F[i].x = x; sR[y].push_back(x); } } struct S { int value, index; S(int v = 0, int i = 0) : value(v), index(i) {} bool operator<(const S& s) const { return value < s.value; } }; ostream& operator<<(ostream& os, const S& s) { os << "(" << s.value << "," << s.index << ")"; return os; } void Solve() { vector<int> cR(R, 0); vector<S> cC(C); for (int i = 0; i < C; i++) { cC[i].index = i; } for (int i = 0; i < N; i++) { int y = F[i].y, x = F[i].x; cR[y]++; cC[x].value++; } Long Ans = 0; for (int i = 0; i < N; i++) { int y = F[i].y, x = F[i].x; if (cR[y] + cC[x].value - 1 == K) { Ans++; } } sort(cC.begin(), cC.end()); vector<int> rTable(C, 0); for (int i = 0; i < C; i++) { rTable[ cC[i].index ] = i; } //cerr << cR << endl; //cerr << cC << endl; //cerr << "INIT" << Ans << endl; for (int r = 0; r < R; r++) { int LB, UB; int k = K - cR[r]; if (k < 0) continue; int lb = 0, ub = C; if (cC[lb].value >= k) { lb = ub = 0; } else { while (lb + 1 < ub) { int mid = (lb + ub) / 2; if (cC[mid].value < k) { lb = mid; } else { ub = mid; } } } LB = ub; lb = 0, ub = C; //cerr << k << " " << cC << endl; if (cC[ub - 1].value <= k) { ub = C; } else { while (lb + 1 < ub) { int mid = (lb + ub) / 2; if (cC[mid].value <= k) { lb = mid; } else { ub = mid; } } } UB = ub; //cerr << k << ", " << "(" << LB << ", " << UB << ")" << endl; for (int i = 0; i < sR[r].size(); i++) { int z = sR[r][i]; if (LB <= rTable[z] && rTable[z] < UB) { Ans--; } } Ans += UB - LB; } cout << Ans << endl; } int main() { Input(); Solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 収集王 |
User | izuru |
Language | C++ (GCC 4.9.2) |
Score | 100 |
Code Size | 3427 Byte |
Status | AC |
Exec Time | 170 ms |
Memory | 7460 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt |
Subtask1 | subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt |
Subtask2 | subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample01.txt | AC | 29 ms | 736 KB |
subtask0-sample02.txt | AC | 25 ms | 804 KB |
subtask0-sample03.txt | AC | 26 ms | 796 KB |
subtask1-01.txt | AC | 26 ms | 928 KB |
subtask1-02.txt | AC | 26 ms | 924 KB |
subtask1-03.txt | AC | 26 ms | 800 KB |
subtask1-04.txt | AC | 26 ms | 800 KB |
subtask1-05.txt | AC | 26 ms | 924 KB |
subtask1-06.txt | AC | 26 ms | 808 KB |
subtask1-07.txt | AC | 26 ms | 800 KB |
subtask1-08.txt | AC | 26 ms | 800 KB |
subtask1-09.txt | AC | 25 ms | 792 KB |
subtask1-10.txt | AC | 26 ms | 800 KB |
subtask1-11.txt | AC | 26 ms | 844 KB |
subtask1-12.txt | AC | 26 ms | 924 KB |
subtask1-13.txt | AC | 26 ms | 784 KB |
subtask1-14.txt | AC | 26 ms | 920 KB |
subtask1-15.txt | AC | 26 ms | 736 KB |
subtask2-01.txt | AC | 27 ms | 924 KB |
subtask2-02.txt | AC | 28 ms | 800 KB |
subtask2-03.txt | AC | 53 ms | 1320 KB |
subtask2-04.txt | AC | 122 ms | 3192 KB |
subtask2-05.txt | AC | 126 ms | 3356 KB |
subtask2-06.txt | AC | 169 ms | 7456 KB |
subtask2-07.txt | AC | 106 ms | 2344 KB |
subtask2-08.txt | AC | 169 ms | 7392 KB |
subtask2-09.txt | AC | 169 ms | 7452 KB |
subtask2-10.txt | AC | 170 ms | 7460 KB |
subtask2-11.txt | AC | 164 ms | 7408 KB |
subtask2-12.txt | AC | 169 ms | 7460 KB |
subtask2-13.txt | AC | 165 ms | 7400 KB |
subtask2-14.txt | AC | 166 ms | 7460 KB |
subtask2-15.txt | AC | 169 ms | 7460 KB |