fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         InputReader in = new InputReader(System.in);
  8.         OutputWriter out = new OutputWriter(System.out);
  9.         TaskD solver = new TaskD(in, out);
  10.         solver.solve();
  11.         out.close();
  12.     }
  13.  
  14.     static class TaskD {
  15.         static private final int[] dx = {1, -1, 0, 0};
  16.         static private final int[] dy = {0, 0, 1, -1};
  17.  
  18.         static int n, m;
  19.         static int total;
  20.  
  21.         static int[][] f;
  22.         static int[] posX;
  23.         static int[] posY;
  24.         static int[] leftBound;
  25.  
  26.         List<Integer>[] edges;
  27.         LinkCutTree lct;
  28.         InputReader in;
  29.         OutputWriter out;
  30.  
  31.         TaskD(InputReader in, OutputWriter out) {
  32.             this.in = in;
  33.             this.out = out;
  34.         }
  35.  
  36.         private void solve() {
  37.             n = in.readInt();
  38.             m = in.readInt();
  39.             total = n * m;
  40.             f = new int[n][m];
  41.             posX = new int[total];
  42.             posY = new int[total];
  43.             for(int i = 0; i < n; ++i) {
  44.                 for(int j = 0; j < m; ++j) {
  45.                     f[i][j] = in.readInt() - 1;
  46.                     posX[f[i][j]] = i;
  47.                     posY[f[i][j]] = j;
  48.                 }
  49.             }
  50.             edges = new ArrayList[total];
  51.             leftBound = new int[total];
  52.             lct = new LinkCutTree(total);
  53.             for(int i = 0; i < total; ++i) {
  54.                 edges[i] = new ArrayList<>();
  55.             }
  56.             for(int l = 0, r = 0; r < total; ++r) {
  57.                l = addCell(l, r);
  58.                leftBound[r] = l;
  59.             }
  60.             long ans = 0;
  61.             SegmentTree t = new SegmentTree(total + 4);
  62.             for(int r = 0; r < total; ++r) {
  63.                 int x = posX[r];
  64.                 int y = posY[r];
  65.                 List<Integer> seg = new ArrayList<>();
  66.                 for(int i = 0; i < 4; ++i) {
  67.                     int px = x + dx[i];
  68.                     int py = y + dy[i];
  69.                     if (px < 0 || px >= n) continue;
  70.                     if (py < 0 || py >= m) continue;
  71.                     int to = f[px][py];
  72.                     if (to > r) continue;
  73.                     seg.add(to);
  74.                 }
  75.                 seg.add(-1);
  76.                 seg.add(r);
  77.                 Collections.sort(seg);
  78.                 for(int i = seg.size() - 1, comp = 1; i > 0; --i) {
  79.                     if (seg.get(i - 1) + 1 > seg.get(i)) {
  80.                         --comp;
  81.                         continue;
  82.                     }
  83.                     t.inc(seg.get(i - 1) + 1, seg.get(i) + 1, comp);
  84.                     --comp;
  85.                 }
  86.                 ans += t.query(leftBound[r], r + 1);
  87.             }
  88.             out.print(ans);
  89.         }
  90.  
  91.         private int addCell(int l, int r) {
  92.             int x = posX[r];
  93.             int y = posY[r];
  94.             for(int i = 0; i < 4; ++i) {
  95.                 int px = x + dx[i];
  96.                 int py = y + dy[i];
  97.                 if (px < 0 || px >= n) continue;
  98.                 if (py < 0 || py >= m) continue;
  99.                 int to = f[px][py];
  100.                 while (l <= to && to <= r) {
  101.                     if (lct.link(to, r)) {
  102.                         edges[to].add(r);
  103.                         break;
  104.                     }
  105.                     removeCell(l);
  106.                     ++l;
  107.                 }
  108.             }
  109.             return l;
  110.         }
  111.  
  112.         private void removeCell(int c) {
  113.             for(int to : edges[c]) {
  114.                 lct.cut(c, to);
  115.             }
  116.             edges[c].clear();
  117.         }
  118.     }
  119.  
  120.     static class SegmentTree {
  121.         int size;
  122.         int height;
  123.         int[] t;
  124.         int[] cnt;
  125.         int[] push;
  126.  
  127.         SegmentTree(int n) {
  128.             this.size = n;
  129.             this.height = 0;
  130.             int temp = n;
  131.             while (temp > 0) {
  132.                 temp >>= 1;
  133.                 ++this.height;
  134.             }
  135.             t = new int[n << 1];
  136.             cnt = new int[n << 1];
  137.             push = new int[n];
  138.             for(int i = 0; i < n; ++i) {
  139.                 cnt[i + n] = 1;
  140.             }
  141.             for(int i = n - 1; i >= 0; --i) {
  142.                 cnt[i] = cnt[i << 1] + cnt[i << 1 | 1];
  143.             }
  144.         }
  145.  
  146.         private void apply(int p, int value) {
  147.             t[p] += value;
  148.             if (p < size) push[p] += value;
  149.         }
  150.  
  151.         private void recalc(int p) {
  152.             while (p > 1) {
  153.                 p >>= 1;
  154.                 t[p] = Math.min(t[p << 1], t[p << 1 | 1]) + push[p];
  155.                 cnt[p] = (t[p] == t[p << 1] + push[p] ? cnt[p << 1] : 0)
  156.                         + (t[p] == t[p << 1 | 1] + push[p] ? cnt[p << 1 | 1] : 0);
  157.             }
  158.         }
  159.  
  160.         private void push(int p) {
  161.             for (int s = height; s > 0; s--) {
  162.                 int i = p >> s;
  163.                 if (push[i] != 0) {
  164.                     apply(i << 1, push[i]);
  165.                     apply(i << 1 | 1, push[i]);
  166.                     push[i] = 0;
  167.                 }
  168.             }
  169.         }
  170.  
  171.         private void inc(int l, int r, int value) {
  172.             l += size;
  173.             r += size;
  174.             int l0 = l;
  175.             int r0 = r;
  176.             for (; l < r; l >>= 1, r >>= 1) {
  177.                 if ((l & 1) != 0) apply(l++, value);
  178.                 if ((r & 1) != 0) apply(--r, value);
  179.             }
  180.             recalc(l0);
  181.             recalc(r0 - 1);
  182.         }
  183.  
  184.         private int query(int l, int r) {
  185.             l += size;
  186.             r += size;
  187.             push(l);
  188.             push(r - 1);
  189.             int min = Integer.MAX_VALUE;
  190.             int minCount = 0;
  191.             for (; l < r; l >>= 1, r >>= 1) {
  192.                 if ((l & 1) != 0) {
  193.                     if (min > t[l]) {
  194.                         min = t[l];
  195.                         minCount = cnt[l];
  196.                     } else if (min == t[l]) {
  197.                         minCount += cnt[l];
  198.                     }
  199.                     ++l;
  200.                 }
  201.                 if ((r & 1) != 0) {
  202.                     --r;
  203.                     if (min > t[r]) {
  204.                         min = t[r];
  205.                         minCount = cnt[r];
  206.                     } else if (min == t[r]) {
  207.                         minCount += cnt[r];
  208.                     }
  209.                 }
  210.             }
  211.             return minCount;
  212.         }
  213.     }
  214.  
  215.     static class LinkCutTree {
  216.  
  217.         private static class Node {
  218.             Node left;
  219.             Node right;
  220.             Node parent;
  221.             boolean revert;
  222.  
  223.             boolean isRoot() {
  224.                 return parent == null || (parent.left != this && parent.right != this);
  225.             }
  226.  
  227.             void push() {
  228.                 if (revert) {
  229.                     revert = false;
  230.                     Node t = left;
  231.                     left = right;
  232.                     right = t;
  233.                     if (left != null)   left.revert = !left.revert;
  234.                     if (right != null)  right.revert = !right.revert;
  235.                 }
  236.             }
  237.         }
  238.  
  239.         static int size;
  240.         Node[] nodes;
  241.  
  242.         LinkCutTree(int n) {
  243.             LinkCutTree.size = n;
  244.             nodes = new Node[n];
  245.             for(int i = 0; i < n; ++i) {
  246.                 nodes[i] = new Node();
  247.             }
  248.         }
  249.  
  250.         private boolean link(int x, int y) {
  251.             return link(nodes[x], nodes[y]);
  252.         }
  253.  
  254.         private void cut(int x, int y) {
  255.             cut(nodes[x], nodes[y]);
  256.         }
  257.  
  258.         private static boolean link(Node x, Node y) {
  259.             if (connected(x, y))
  260.                 return false;
  261.             makeRoot(x);
  262.             x.parent = y;
  263.             return true;
  264.         }
  265.  
  266.         private static void cut(Node x, Node y) {
  267.             makeRoot(x);
  268.             expose(y);
  269.             if (y.right != x || x.left != null || x.right != null) {
  270.                 throw new RuntimeException("error: no edge (x,y)");
  271.             }
  272.             y.right.parent = null;
  273.             y.right = null;
  274.         }
  275.  
  276.         static void connect(Node ch, Node p, Boolean isLeftChild) {
  277.             if (ch != null)
  278.                 ch.parent = p;
  279.             if (isLeftChild != null) {
  280.                 if (isLeftChild)
  281.                     p.left = ch;
  282.                 else
  283.                     p.right = ch;
  284.             }
  285.         }
  286.  
  287.         static void rotate(Node x) {
  288.             Node p = x.parent;
  289.             Node g = p.parent;
  290.             boolean isRootP = p.isRoot();
  291.             boolean leftChildX = (x == p.left);
  292.             connect(leftChildX ? x.right : x.left, p, leftChildX);
  293.             connect(p, x, !leftChildX);
  294.             connect(x, g, !isRootP ? p == g.left : null);
  295.         }
  296.  
  297.         static void splay(Node x) {
  298.             while (!x.isRoot()) {
  299.                 Node p = x.parent;
  300.                 Node g = p.parent;
  301.                 if (!p.isRoot())
  302.                     g.push();
  303.                 p.push();
  304.                 x.push();
  305.                 if (!p.isRoot())
  306.                     rotate((x == p.left) == (p == g.left) ? p/*zig-zig*/ : x/*zig-zag*/);
  307.                 rotate(x);
  308.             }
  309.             x.push();
  310.         }
  311.  
  312.         // makes node x the root of the virtual tree, and also x becomes the leftmost node in its splay tree
  313.         static Node expose(Node x) {
  314.             Node last = null;
  315.             for (Node y = x; y != null; y = y.parent) {
  316.                 splay(y);
  317.                 y.left = last;
  318.                 last = y;
  319.             }
  320.             splay(x);
  321.             return last;
  322.         }
  323.  
  324.         private static void makeRoot(Node x) {
  325.             expose(x);
  326.             x.revert = !x.revert;
  327.         }
  328.  
  329.         private static boolean connected(Node x, Node y) {
  330.             if (x == y)
  331.                 return true;
  332.             expose(x);
  333.             expose(y);
  334.             return x.parent != null;
  335.         }
  336.     }
  337.  
  338.     static class OutputWriter {
  339.         private final PrintWriter writer;
  340.  
  341.         public OutputWriter(OutputStream outputStream) {
  342.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  343.         }
  344.  
  345.         public OutputWriter(Writer writer) {
  346.             this.writer = new PrintWriter(writer);
  347.         }
  348.  
  349.         public void print(Object... objects) {
  350.             for (int i = 0; i < objects.length; i++) {
  351.                 if (i != 0) {
  352.                     writer.print(' ');
  353.                 }
  354.                 writer.print(objects[i]);
  355.             }
  356.             writer.println();
  357.         }
  358.  
  359.         public void close() {
  360.             writer.close();
  361.         }
  362.  
  363.     }
  364.  
  365.     static class InputReader {
  366.         private InputStream stream;
  367.         private byte[] buf = new byte[1024];
  368.         private int curChar;
  369.         private int numChars;
  370.         private InputReader.SpaceCharFilter filter;
  371.  
  372.         public InputReader(InputStream stream) {
  373.             this.stream = stream;
  374.         }
  375.  
  376.         public int read() {
  377.             if (numChars == -1) {
  378.                 throw new InputMismatchException();
  379.             }
  380.             if (curChar >= numChars) {
  381.                 curChar = 0;
  382.                 try {
  383.                     numChars = stream.read(buf);
  384.                 } catch (IOException e) {
  385.                     throw new InputMismatchException();
  386.                 }
  387.                 if (numChars <= 0) {
  388.                     return -1;
  389.                 }
  390.             }
  391.             return buf[curChar++];
  392.         }
  393.  
  394.         public int readInt() {
  395.             int c = read();
  396.             while (isSpaceChar(c)) {
  397.                 c = read();
  398.             }
  399.             int sgn = 1;
  400.             if (c == '-') {
  401.                 sgn = -1;
  402.                 c = read();
  403.             }
  404.             int res = 0;
  405.             do {
  406.                 if (c < '0' || c > '9') {
  407.                     throw new InputMismatchException();
  408.                 }
  409.                 res *= 10;
  410.                 res += c - '0';
  411.                 c = read();
  412.             } while (!isSpaceChar(c));
  413.             return res * sgn;
  414.         }
  415.  
  416.         public boolean isSpaceChar(int c) {
  417.             if (filter != null) {
  418.                 return filter.isSpaceChar(c);
  419.             }
  420.             return isWhitespace(c);
  421.         }
  422.  
  423.         public static boolean isWhitespace(int c) {
  424.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  425.         }
  426.  
  427.         public double readDouble() {
  428.             int c = read();
  429.             while (isSpaceChar(c)) {
  430.                 c = read();
  431.             }
  432.             int sgn = 1;
  433.             if (c == '-') {
  434.                 sgn = -1;
  435.                 c = read();
  436.             }
  437.             double res = 0;
  438.             while (!isSpaceChar(c) && c != '.') {
  439.                 if (c == 'e' || c == 'E') {
  440.                     return res * Math.pow(10, readInt());
  441.                 }
  442.                 if (c < '0' || c > '9') {
  443.                     throw new InputMismatchException();
  444.                 }
  445.                 res *= 10;
  446.                 res += c - '0';
  447.                 c = read();
  448.             }
  449.             if (c == '.') {
  450.                 c = read();
  451.                 double m = 1;
  452.                 while (!isSpaceChar(c)) {
  453.                     if (c == 'e' || c == 'E') {
  454.                         return res * Math.pow(10, readInt());
  455.                     }
  456.                     if (c < '0' || c > '9') {
  457.                         throw new InputMismatchException();
  458.                     }
  459.                     m /= 10;
  460.                     res += (c - '0') * m;
  461.                     c = read();
  462.                 }
  463.             }
  464.             return res * sgn;
  465.         }
  466.  
  467.         public interface SpaceCharFilter {
  468.             public boolean isSpaceChar(int ch);
  469.         }
  470.  
  471.     }
  472. }
Runtime error #stdin #stdout #stderr 0.05s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at Main$InputReader.read(Main.java:378)
	at Main$InputReader.readInt(Main.java:397)
	at Main$TaskD.solve(Main.java:37)
	at Main$TaskD.access$000(Main.java:14)
	at Main.main(Main.java:10)
https://ideone.com/GWzJof
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!