{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eDCE Coders admins are way much geekier than they actually seem! Kartik has been following that tradition lately. How? Well, he took the inversion count problem to a whole new level!\u003c/p\u003e\r\n\u003cp\u003eSounds pretty normal to you, huh? Wanna challenge him? Try solving his version of inversion count then!\u003c/p\u003e\r\n\u003cp\u003eYou are given a 2-d array of integers. You need to find out the inversion count of that array. A pair of integers in the 2-d array counts as an inversion pair (A,B) if and only if:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThere exists a valid path from top-left corner (0,0) to bottom right corner (r, c) such that A and B integers lie on that path.\u003c/li\u003e\r\n\u003cli\u003eA occurs before B on that path.\u003c/li\u003e\r\n\u003cli\u003eAnd, A \u0026gt; B.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eA valid path is defined as a path that can be traversed from top-left corner (0, 0) to bottom-right corner (r, c) by moving only in right or downwards direction, without moving out of the grid.\u003c/p\u003e\r\n\u003cp\u003eAre you geekier than Kartik?\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eConstraints:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e0 \u0026lt; R, C \u0026lt;\u003d 300\u003c/p\u003e\r\n\u003cp\u003e0 \u0026lt; Ai \u0026lt;\u003d 10^5, where Ai stands for an integer in the array.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line contains space separated 2 integers, R and C, denoting the number of rows and columns.\u003c/p\u003e\r\n\u003cp\u003eNext R lines contain C space separated integers representing the 2-d array.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput the number of inversion pairs as described in the problem statement.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\r\n3 4 2 5\r\n1 7 11 16\r\n8 9 6 12\r\n10 13 15 14\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\u003c/div\u003e"}}]}