diff options
author | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2018-05-23 21:46:57 +0700 |
---|---|---|
committer | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2018-05-23 21:46:57 +0700 |
commit | 18419b2b07ffbc1f390c7309ca78cfc7820411eb (patch) | |
tree | 7a00c7f34466f14b6fcf770e54078f1258bc267e /THT/C/TP-2018/mab.cpp | |
parent | 96a3779265c2476d25b6a5c6b616aecca3689f07 (diff) | |
download | cp-18419b2b07ffbc1f390c7309ca78cfc7820411eb.tar.gz |
Thêm đề bảng C Tin học trẻ Hà Nội XXIII
Diffstat (limited to 'THT/C/TP-2018/mab.cpp')
-rw-r--r-- | THT/C/TP-2018/mab.cpp | 77 |
1 files changed, 77 insertions, 0 deletions
diff --git a/THT/C/TP-2018/mab.cpp b/THT/C/TP-2018/mab.cpp new file mode 100644 index 0000000..7b8dbb8 --- /dev/null +++ b/THT/C/TP-2018/mab.cpp @@ -0,0 +1,77 @@ +#include <iostream> +#include <fstream> +#include <set> +#include <vector> +using namespace std; + +int +main() +{ + ifstream infile; + infile.open("MAB.INP"); + int m, n, k; + infile >> m >> n >> k; + + int i, j; + long tmp; + vector<vector<long>> a; + a.resize(m); + vector<set<long>> r; + r.resize(m); + vector<set<long>> c; + c.resize(n); + for (i = 0; i < m; i++) + for (j = 0; j < n; j++) + { + infile >> tmp; + a[i].push_back(tmp); + r[i].insert(tmp); + c[j].insert(tmp); + } + + vector<vector<long>> rows, columns; + rows.resize(m); + for (i = 0; i < m; i++) + for (auto& item : r[i]) + rows[i].push_back(item); + columns.resize(n); + for (i = 0; i < n; i++) + for (auto& item : c[i]) + columns[i].push_back(item); + + int alpha, beta; + vector<vector<long>> mem; + mem.resize(m); + for (i = 0; i < m; i++) + mem[i].resize(n); + for (i = 0; i < m; i++) + for (j = 0; j < n; j++) + { + tmp = a[i][j]; + alpha = lower_bound(rows[i].begin(), rows[i].end(), tmp) - rows[i].begin(); + beta = lower_bound(columns[j].begin(), columns[j].end(), tmp) - columns[j].begin(); + mem[alpha][n - beta - 1]++; + } + for (i = 0; i < m; i++) + for (j = 1; j < n; j++) + mem[i][j] += mem[i][j - 1]; + for (i = 1; i < m; i++) + for (j = 0; j < n; j++) + mem[i][j] += mem[i - 1][j]; + + ofstream outfile; + outfile.open("MAB.OUT"); + while (k--) + { + infile >> alpha >> beta; + if (alpha == m) + alpha--; + if (beta == n) + beta--; + outfile << mem[alpha][beta] << endl; + } + + infile.close(); + outfile.close(); + return 0; +} |