Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
JOI 2017 Yo 5th
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <utility>
using Pair = std::pair<int, int>;
int h, w;
int arr[1010][1010];
int dy[] = {0, 0, -1, 1}, dx[] = {1, -1, 0, 0};
std::vector<std::vector<std::set<Pair>>> check;
int main() {
std::cin >> h >> w;
std::map<int, Pair> pos;
for(int i = 0; i < h; ++i) {
for(int j = 0; j < w; ++j) {
std::cin >> arr[i][j];
pos.insert({arr[i][j], {i, j}});
}
}
check.resize(h, std::vector<std::set<Pair>>(w));
for(auto&& p : pos) {
int y = p.second.first;
int x = p.second.second;
int q = p.first;
for(int i = 0; i < 4; ++i) {
int py = y + dy[i], px = x + dx[i];
if(py < 0 || py >= h || px < 0 || px >= w)
continue;
if(q < arr[py][px]) {
if(check[y][x].size() == 0) {
check[py][px].insert(p.second);
}else {
for(auto&& r : check[y][x]) {
check[py][px].insert(r);
}
}
}
}
}
int ans = 0;
for(int i = 0; i < h; ++i) {
for(int j = 0; j < w; ++j) {
if(check[i][j].size() > 1) {
++ans;
}
}
}
std::cout << ans << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment