fork download 
  1. {
  2. 	"WrongAwnser": {
  3. 	  "prefix": "WrongAwnser",
  4. 	  "body": [
  5. 		"#include <bits/stdc++.h>",
  6. 		"using namespace std;",
  7. 		"mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());",
  8. 		"",
  9. 		"using i16 = short int;",
  10. 		"using i32 = int32_t;",
  11. 		"using i64 = int64_t;",
  12. 		"using ui16 = unsigned short int;",
  13. 		"using ui32 = uint32_t;",
  14. 		"using ui64 = uint64_t;",
  15. 		"",
  16. 		"template<class T>",
  17. 		"using v = vector<T>;",
  18. 		"",
  19. 		"#define all(a) (a).begin(), (a).end()",
  20. 		"#define open(x) freopen(#x \".inp\", \"r\", stdin), freopen(#x \".out\", \"w\", stdout)",
  21. 		"",
  22. 		"template<class X, class Y> bool mimi(X &x, const Y &y) {if(x > y) {x = y; return 1;} return 0;}",
  23. 		"template<class X, class Y> bool mama(X &x, const Y &y) {if(x < y) {x = y; return 1;} return 0;}",
  24. 		"",
  25. 		"const i32 N = 2 * 1e5;",
  26. 		"const i32 M = 1000000007;",
  27. 		"const i32 inf = 1000000009;",
  28. 		"const i64 infll = (i64)1000000000000000018;",
  29. 		"",
  30. 		"void sad(i32 testID) {",
  31. 		"	$0",
  32. 		"}",
  33. 		"",
  34. 		"i32 main() {",
  35. 		"    auto begin = std::chrono::high_resolution_clock::now();",
  36. 		"    ios_base::sync_with_stdio(false);",
  37. 		"    cin.tie(NULL); cout.tie(NULL);",
  38. 		"",
  39. 		"    i32 t = 1;",
  40. 		"    cin >> t;",
  41. 		"    for(i32 testID = 1; testID <= t; testID++) {",
  42. 		"        // cout << \"Case #\" << testID << \":\\n\";",
  43. 		"        sad(testID);",
  44. 		"    }",
  45. 		"    auto end = std::chrono::high_resolution_clock::now();",
  46. 		"    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);",
  47. 		"    cerr << endl << \"Time measured: \" << elapsed.count() * 1e-9 << \" seconds.\" << endl; ",
  48. 		"    return 0;",
  49. 		"}",
  50. 		""
  51. 	  ],
  52. 	  "description": "WrongAwnser"
  53. 	}
  54. 	"Accepted": {
  55.   "prefix": "Accepted",
  56.   "body": [
  57.     "#include <bits/stdc++.h>",
  58.     "using namespace std;",
  59. 	"mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());",
  60.     "",
  61.     "#define i32 int",
  62.     "#define i64 long long int",
  63.     "#define ui32 unsigned int",
  64.     "#define ui64 unsigned long long int",
  65.     "",
  66.     "#define all(a) (a).begin(), (a).end()",
  67.     "#define open(x) freopen(#x \".inp\", \"r\", stdin), freopen(#x \".out\", \"w\", stdout)",
  68.     "",
  69.     "const i32 N = 2 * 1e5;",
  70.     "const i32 M = 1000000007;",
  71.     "const i32 inf = 1000000009;",
  72.     "const i64 infll = (i64)1000000000000000018;",
  73.     "",
  74.     "void sad(i32 testID) {",
  75.     "    ",
  76.     "}",
  77.     "",
  78.     "i32 main() {",
  79. 	"    auto begin = std::chrono::high_resolution_clock::now();",
  80.     "    ios_base::sync_with_stdio(false);",
  81.     "    cin.tie(NULL); cout.tie(NULL);",
  82.     "",
  83.     "    i32 t = 1;",
  84.     "    cin >> t;",
  85.     "    for(i32 testID = 1; testID <= t; testID++) {",
  86.     "        // cout << \"Case #\" << testID << \":\\n\";",
  87.     "        sad(testID);",
  88.     "    }",
  89. 	"    auto end = std::chrono::high_resolution_clock::now();",
  90. 	"    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);",
  91. 	"    cerr << endl << \"Time measured: \" << elapsed.count() * 1e-9 << \" seconds.\" << endl; ",
  92.     "    return 0;",
  93.     "}",
  94.     ""
  95.   ],
  96.   "description": "Accepted"
  97. }
  98. 		  "Power": {
  99. 	  "prefix": "Power",
  100. 	  "body": [
  101. 		"i64 power(i64 base, i64 exp, i64 mod) {",
  102. 		"    i64 result = 1;",
  103. 		"    for(; exp; exp >>= 1, base = (base * base) % mod) if(exp & 1) result = (result * base) % mod;",
  104. 		"    return result;",
  105. 		"}"
  106. 	  ],
  107. 	  "description": "Power"
  108. 	}
  109.  
  110. 		  "Sieve": {
  111. 			"prefix": "Sieve",
  112. 			"body": [
  113. 			  "vector<i32> p(maxn + 1, 0);",
  114. 			  "void Sieve() {",
  115. 			  "    for (i32 i = 2; i * i <= maxn; ++i) if (p[i] == 0) for (i32 j = i * i; j <= maxn; j += i) if (p[j] == 0) p[j] = i;",
  116. 			  "    for (i32 i = 2; i <= maxn; ++i) if (p[i] == 0)  p[i] = i;",
  117. 			  "    return;",
  118. 			  "}"
  119. 			],
  120. 			"description": "Sieve"
  121. 		  }
  122.  
  123. 		  "primeFactorization": {
  124. 			"prefix": "primeFactorization",
  125. 			"body": [
  126. 			  "vector<i64> factored;",
  127. 			  "void factor(i32 n) {",
  128. 			  "    factored.clear();",
  129. 			  "    while (n != 1) {",
  130. 			  "        factored.push_back(v[n]);",
  131. 			  "        n /= v[n];",
  132. 			  "    }",
  133. 			  "}",
  134. 			  "",
  135. 			  "void sqrfactor(i64 n) {",
  136. 			  "    factored.clear();",
  137. 			  "    while (n % 2 == 0) {",
  138. 			  "        factored.push_back(2);",
  139. 			  "        n /= 2;",
  140. 			  "    }",
  141. 			  "",
  142. 			  "    for (i32 i = 3; i * i <= n; i += 2) {",
  143. 			  "        while (n % i == 0) {",
  144. 			  "            factored.push_back(i);",
  145. 			  "            n /= i;",
  146. 			  "        }",
  147. 			  "    }",
  148. 			  "",
  149. 			  "    if (n > 1) {",
  150. 			  "        factored.push_back(n);",
  151. 			  "    }",
  152. 			  "}"
  153. 			],
  154. 			"description": "primeFactorization"
  155. 		  }
  156.  
  157. 		  "EulerTotient": {
  158. 			"prefix": "EulerTotient",
  159. 			"body": [
  160. 			  "map<i64, i64>  mp;",
  161. 			  "i64 res = 1;",
  162. 			  "i64 eulerTotient(const i32& n){",
  163. 			  "    i64 res = 1;",
  164. 			  "    for (i32 it : factored) {",
  165. 			  "        if(mp[it] >= 1){",
  166. 			  "        	res *= it;",
  167. 			  "			mp[it] ++;",
  168. 			  "		}",
  169. 			  "		else{",
  170. 			  "			mp[it] ++;",
  171. 			  "			res *= it - 1;",
  172. 			  "		}",
  173. 			  "    }",
  174. 			  "",
  175. 			  "    return res;",
  176. 			  "}"
  177. 			],
  178. 			"description": "primeFactorization"
  179. 		  }
  180.  
  181. 		  "Matrix": {
  182. 			"prefix": "Matrix",
  183. 			"body": [
  184. 			  "class Matrix {",
  185. 			  "private:",
  186. 			  "    i64 row, col;",
  187. 			  "    vector<vector<i64>> data;",
  188. 			  "",
  189. 			  "pubi64c:",
  190. 			  "    Matrix(const vector<vector<i64>>& base) : row(base.size()), col(base[0].size()), data(base) {}",
  191. 			  "",
  192. 			  "    Matrix(i64 r, i64 c, i64 val) : row(r), col(c), data(vector<vector<i64>>(r, vector<i64>(c, val))) {}",
  193. 			  "",
  194. 			  "    void fill(const i64& value) {",
  195. 			  "        for(auto& row : data)",
  196. 			  "            std::fill(row.begin(), row.end(), value);",
  197. 			  "    }",
  198. 			  "",
  199. 			  "    void fix(const i64& current, const i64& value) {",
  200. 			  "        for(auto& row : data)",
  201. 			  "            for(auto& cell : row)",
  202. 			  "                if(cell == current) cell = value;",
  203. 			  "    }",
  204. 			  "",
  205. 			  "    Matrix& operator=(const Matrix& that) {",
  206. 			  "        if (this != &that) {",
  207. 			  "            row = that.row;",
  208. 			  "            col = that.col;",
  209. 			  "            data = that.data;",
  210. 			  "        }",
  211. 			  "        return *this;",
  212. 			  "    }",
  213. 			  "",
  214. 			  "    static i64 multiply(i64 a, i64 b) {",
  215. 			  "        if(mod <= 1e9 + 7) return (a * b) % mod;",
  216. 			  "        i64 res = 0;",
  217. 			  "        a %= mod;",
  218. 			  "        while (b > 0) {",
  219. 			  "            if (b & 1)",
  220. 			  "                res = (res + a) % mod;",
  221. 			  "            a = (2 * a) % mod;",
  222. 			  "            b >>= 1;",
  223. 			  "        }",
  224. 			  "        return res;",
  225. 			  "    }",
  226. 			  "",
  227. 			  "    static i64 cal(i64 a, i64 b) {",
  228. 			  "        return (a + b % mod) % mod;",
  229. 			  "    }",
  230. 			  "",
  231. 			  "    Matrix operator*(const Matrix& that) const {",
  232. 			  "        if (col != that.row) {",
  233. 			  "            throw runtime_error(\"segmentation fault\");",
  234. 			  "        }",
  235. 			  "        Matrix res(row, that.col, 0);",
  236. 			  "        for(i32 i = 0; i < row; i++) {",
  237. 			  "            for(i32 j = 0; j < that.col; j++) {",
  238. 			  "                for(i32 k = 0; k < col; k++) {",
  239. 			  "                    res.data[i][j] = cal(res.data[i][j], multiply(data[i][k], that.data[k][j]));",
  240. 			  "                }",
  241. 			  "            }",
  242. 			  "        }",
  243. 			  "        return res;",
  244. 			  "    }",
  245. 			  "",
  246. 			  "    Matrix operator^(i64 exp) const {",
  247. 			  "        Matrix res(row, col, 0);",
  248. 			  "        Matrix base = *this;",
  249. 			  "        for(i32 i = 0; i < row; i++) res.data[i][i] = 1; ",
  250. 			  "",
  251. 			  "        while (exp > 0) {",
  252. 			  "            if (exp & 1) res = res * base;",
  253. 			  "            base = base * base;",
  254. 			  "            exp >>= 1;",
  255. 			  "        }",
  256. 			  "        return res;",
  257. 			  "    }",
  258. 			  "",
  259. 			  "    Matrix& operator*=(const Matrix& that) {",
  260. 			  "        *this = *this * that;",
  261. 			  "        return *this;",
  262. 			  "    }",
  263. 			  "",
  264. 			  "    Matrix& operator^=(i64 exp) {",
  265. 			  "        *this = *this ^ exp;",
  266. 			  "        return *this;",
  267. 			  "    }",
  268. 			  "",
  269. 			  "    bool operator==(const Matrix& that) const {",
  270. 			  "        return row == that.row && col == that.col && data == that.data;",
  271. 			  "    }",
  272. 			  "",
  273. 			  "    i64 rows() const { return row; }",
  274. 			  "    i64 cols() const { return col; }",
  275. 			  "",
  276. 			  "    const vector<i64>& operator[](i32 i) const { return data[i]; }",
  277. 			  "    vector<i64>& operator[](i32 i) { return data[i]; }",
  278. 			  "",
  279. 			  "    void print() const {",
  280. 			  "        for(const auto& row : data) {",
  281. 			  "            for(const auto& cell : row) {",
  282. 			  "                cout << cell << \" \";",
  283. 			  "            }",
  284. 			  "            cout << endl;",
  285. 			  "        }",
  286. 			  "    }",
  287. 			  "};"
  288. 			],
  289. 			"description": "Matrix"
  290. 		  }
  291.  
  292. 		  "max_subarray_sum": {
  293. 			"prefix": "max_subarray_sum",
  294. 			"body": [
  295. 			  "vector<i32> res;",
  296. 			  "void max_subarray_sum(const vector<i32>& arr) {",
  297. 			  "    i32 max_sum = -inf;",
  298. 			  "    i32 current_sum = 0;",
  299. 			  "    i32 start_index = 0;",
  300. 			  "    i32 end_index = 0;",
  301. 			  "    i32 temp_start_index = 0;",
  302. 			  "",
  303. 			  "    for (i32 i = 0; i < arr.size(); ++i) {",
  304. 			  "        current_sum += arr[i];",
  305. 			  "",
  306. 			  "        if (current_sum > max_sum) {",
  307. 			  "            max_sum = current_sum;",
  308. 			  "            start_index = temp_start_index;",
  309. 			  "            end_index = i;",
  310. 			  "        }",
  311. 			  "",
  312. 			  "        if (current_sum < 0) {",
  313. 			  "            current_sum = 0;",
  314. 			  "            temp_start_index = i + 1;",
  315. 			  "        }",
  316. 			  "    }",
  317. 			  "",
  318. 			  "    res = vector<i32>(arr.begin() + start_index, arr.begin() + end_index + 1);",
  319. 			  "}"
  320. 			],
  321. 			"description": "max_subarray_sum"
  322. 		  }
  323.  
  324. 		  "SegmentTree": {
  325.   "prefix": "SegmentTree",
  326.   "body": [
  327.     "struct STN {i32 val, lazy;};",
  328.     "struct SegmentTree {",
  329.     "    vector<STN> node;",
  330.     "    const STN DEADNODE = {0, 0};",
  331.     "    i32 uu, vv, n;",
  332.     "    SegmentTree(i32 size) : n(size) {",
  333.     "        node.resize(4 * n + 10, DEADNODE);",
  334.     "        this->uu = 0;",
  335.     "        this->vv = n;",
  336.     "    }",
  337.     "    void relength(i32 size){",
  338.     "        n = size;",
  339.     "        node.resize(4 * n + 10, DEADNODE);",
  340.     "        this->uu = 0;",
  341.     "        this->vv = n;",
  342.     "    }",
  343.     "    STN merge(STN a, STN b) {",
  344.     "        return {a.val + b.val, 0};",
  345.     "    }",
  346.     "    void lazy_update(i32 id, i32 l, i32 r){",
  347.     "        if(node[id].lazy != 0){",
  348.     "            node[id << 1].lazy += node[id].lazy;",
  349.     "            node[id << 1 | 1].lazy += node[id].lazy;",
  350.     "            i32 mid = (r + l) >> 1;",
  351.     "            node[id << 1].val += node[id].lazy * (mid - l + 1);",
  352.     "            node[id << 1 | 1].val += node[id].lazy * (r - mid);",
  353.     "            node[id].lazy = 0;",
  354.     "        }",
  355.     "    }",
  356.     "    void updateV(i32 pos, i32 val) {updateV(pos, pos, val, 1, uu, vv);}",
  357.     "    void updateV(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {",
  358.     "        if (l > v || r < u) return;",
  359.     "        if (u <= l && r <= v) {",
  360.     "            node[id].val = val;",
  361.     "            return;",
  362.     "        }",
  363.     "        lazy_update(id, l, r);",
  364.     "        i32 mid = (l + r) >> 1;",
  365.     "        updateV(u, v, val, id << 1, l, mid);",
  366.     "        updateV(u, v, val, id << 1 | 1, mid + 1, r);",
  367.     "        node[id] = merge(node[id << 1], node[id << 1 | 1]);",
  368.     "    }",
  369.     "    void update(i32 u, i32 v, i32 val) {update(u, v, val, 1, uu, vv);}",
  370.     "    void update(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {",
  371.     "        if (l > v || r < u) return;",
  372.     "        if (u <= l && r <= v) {",
  373.     "            node[id].lazy += val;",
  374.     "            node[id].val += val * (r - l + 1);",
  375.     "            return;",
  376.     "        }",
  377.     "        lazy_update(id, l, r);",
  378.     "        i32 mid = (l + r) >> 1;",
  379.     "        update(u, v, val, id << 1, l, mid);",
  380.     "        update(u, v, val, id << 1 | 1, mid + 1, r);",
  381.     "        node[id] = merge(node[id << 1], node[id << 1 | 1]);",
  382.     "    }",
  383.     "    STN get(i32 u, i32 v) {return get(u, v, 1, uu, vv);}",
  384.     "    STN get(i32 u, i32 v, i32 id, i32 l, i32 r) {",
  385.     "        if (l > v || r < u) return DEADNODE;",
  386.     "        if (u <= l && r <= v) return node[id];",
  387.     "        lazy_update(id, l, r);",
  388.     "        i32 mid = (l + r) >> 1;",
  389.     "        return merge(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));",
  390.     "    }",
  391.     "};",
  392.     ""
  393.   ],
  394.   "description": "SegmentTree"
  395. }
  396.  
  397. 		  "FenwickTree": {
  398. 			"prefix": "FenwickTree",
  399. 			"body": [
  400. 			  "struct FenwickTree {",
  401. 			  "    vector<i64> bit1, bit2;",
  402. 			  "    i64 n;",
  403. 			  "",
  404. 			  "    FenwickTree(i64 size) : n(size) {",
  405. 			  "        bit1.resize(n + 1, 0);",
  406. 			  "        bit2.resize(n + 1, 0);",
  407. 			  "    }",
  408. 			  "",
  409. 			  "    void update(vector<i64>& b, i64 u, i64 v) {",
  410. 			  "        i64 idx = u;",
  411. 			  "        while (idx <= n) {",
  412. 			  "            b[idx] += v;",
  413. 			  "            idx += (idx & (-idx));",
  414. 			  "        }",
  415. 			  "    }",
  416. 			  "",
  417. 			  "    void update(i64 pos, i64 val){",
  418. 			  "        update(pos, pos, val);",
  419. 			  "    }",
  420. 			  "",
  421. 			  "    void update(i64 l, i64 r, i64 val) {",
  422. 			  "        update(bit1, l, (n - l + 1) * val);",
  423. 			  "        update(bit1, r + 1, -(n - r + 1) * val);",
  424. 			  "        update(bit2, l, val);",
  425. 			  "        update(bit2, r + 1, -val);",
  426. 			  "    }",
  427. 			  "",
  428. 			  "    i64 getNode(vector<i64>& b, i64 u) {",
  429. 			  "        i64 idx = u, ans = 0;",
  430. 			  "        while (idx > 0) {",
  431. 			  "            ans += b[idx];",
  432. 			  "            idx -= (idx & (-idx));",
  433. 			  "        }",
  434. 			  "        return ans;",
  435. 			  "    }",
  436. 			  "",
  437. 			  "    i64 prefSum(i64 u) {",
  438. 			  "        return getNode(bit1, u) - getNode(bit2, u) * (n - u);",
  439. 			  "    }",
  440. 			  "",
  441. 			  "    i64 get(i64 x) {",
  442. 			  "        return prefSum(x) - prefSum(x - 1);",
  443. 			  "    }",
  444. 			  "",
  445. 			  "    i64 get(i64 l, i64 r) {",
  446. 			  "        return prefSum(r) - prefSum(l - 1);",
  447. 			  "    }",
  448. 			  "};"
  449. 			],
  450. 			"description": "FenwickTree"
  451. 		  }
  452.  
  453. 		  "Dijkstra": {
  454.   "prefix": "Dijkstra",
  455.   "body": [
  456.     "struct Edge {i32 v; i64 c;};",
  457.     "struct Node {i32 idx; i64 val;bool operator<(const Node& other) const {return val > other.val;}};",
  458.     "void dijkstra(i32 n, i32 s, const vector<vector<Edge>>& graph, vector<i64>& dp, vector<i32>& trace) {",
  459.     "    dp.resize(n, infll); dp[s] = 0;",
  460.     "    trace.resize(n, -1);",
  461.     "    priority_queue<Node> pq;",
  462.     "    pq.push({s, 0});",
  463.     "    while (!pq.empty()) {",
  464.     "        Node current = pq.top();",
  465.     "        pq.pop();",
  466.     "        i32 u = current.idx;",
  467.     "        i64 d = current.val;",
  468.     "        if (d > dp[u]) continue;",
  469.     "        for (const Edge& edge : graph[u]) {",
  470.     "            i32 v = edge.v; i64 c = edge.c;",
  471.     "            if (dp[u] + c < dp[v]) {",
  472.     "                dp[v] = dp[u] + c;",
  473.     "                trace[v] = u;",
  474.     "                pq.push({v, dp[v]});",
  475.     "            }",
  476.     "        }",
  477.     "    }",
  478.     "}"
  479.   ],
  480.   "description": "Dijkstra"
  481. }
  482.  
  483. 		  "Miller_rabin": {
  484. 			"prefix": "Miller_rabin",
  485. 			"body": [
  486. 			  "bool miller_rabin(i64 n, i64 k) {",
  487. 			  "    if (n <= 1) return false;",
  488. 			  "    if (n == 2 || n == 3) return true;",
  489. 			  "    if (n % 2 == 0) return false;",
  490. 			  "",
  491. 			  "    i64 r = 0, d = n - 1;",
  492. 			  "    while (!(d & 1)) {",
  493. 			  "        r++;",
  494. 			  "        d /= 2;",
  495. 			  "    }",
  496. 			  "",
  497. 			  "    for(i64 i = 0; i < k; i ++)",
  498. 			  "        i64 a = rand() % (n - 4) + 2; ",
  499. 			  "        i64 x = power(a, d, n);",
  500. 			  "",
  501. 			  "        if (x == 1 || x == n - 1) continue;",
  502. 			  "",
  503. 			  "        for(i64 j = 0; j < r - 1; j ++){",
  504. 			  "            x = power(x, 2, n);",
  505. 			  "            if (x == n - 1) break;",
  506. 			  "        }",
  507. 			  "",
  508. 			  "        if (x != n - 1) return false; ",
  509. 			  "    }",
  510. 			  "	",
  511. 			  "    return true; ",
  512. 			  "}"
  513. 			],
  514. 			"description": "Miller_rabin"
  515. 		  }
  516.  
  517. 		  "SparseTable": {
  518. 			"prefix": "SparseTable",
  519. 			"body": [
  520. 			  "struct SparseTableNode{i64 val;};",
  521. 			  "struct SparseTable {",
  522. 			  "    i64 n;",
  523. 			  "    vector<vector<SparseTableNode>> dp;",
  524. 			  "    void rebuild(const vector<i32>& a) {",
  525. 			  "        n = a.size(); dp.clear();",
  526. 			  "        dp.resize(n, vector<SparseTableNode>(__lg(n) + 1));",
  527. 			  "        build(a);",
  528. 			  "    }",
  529. 			  "    SparseTable(const vector<i32>& a) : n(a.size()) {",
  530. 			  "        dp.clear();",
  531. 			  "        dp.resize(n, vector<SparseTableNode>(__lg(n) + 1));",
  532. 			  "        build(a);",
  533. 			  "    }",
  534. 			  "    SparseTableNode merge(SparseTableNode a, SparseTableNode b) {",
  535. 			  "        if(a.val < b.val) return a; return b;",
  536. 			  "    }",
  537. 			  "    void build(const vector<i32>& a) {",
  538. 			  "        for(i32 i = 0; i < n; i ++) dp[i][0] = {a[i]};",
  539. 			  "        for(i32 j = 1; j <= __lg(n); j ++)",
  540. 			  "            for(i32 i = 0; i < n - (1 << j) + 1; i ++)",
  541. 			  "                dp[i][j] = merge(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);",
  542. 			  "    }",
  543. 			  "    SparseTableNode get(i64 l, i64 r) {",
  544. 			  "        i64 minlen = __lg(r - l + 1);",
  545. 			  "        return merge(dp[l][minlen], dp[r - (1 << minlen) + 1][minlen]);",
  546. 			  "    }",
  547. 			  "};"
  548. 			],
  549. 			"description": "SparseTable"
  550. 		  }
  551.  
  552. 		  "Trie": {
  553. 			"prefix": "Trie",
  554. 			"body": [
  555. 			  "const i64 max_ = 26;",
  556. 			  "struct Trie{",
  557. 			  "    struct Node{",
  558. 			  "        Node *child[max_];",
  559. 			  "        i64 exist, cnt;",
  560. 			  "        Node() {for(i32 i = 0; i < max_; i ++) child[i] = NULL; exist = cnt = 0;}",
  561. 			  "    };",
  562. 			  " ",
  563. 			  "    i64 cur; Node *root;",
  564. 			  "    Trie() : cur(0) {root = new Node();};",
  565. 			  "    void add(string s) {",
  566. 			  "        Node *p = root;",
  567. 			  "        for (auto f : s) {",
  568. 			  "            i64 c = f - 'a';",
  569. 			  "            if (p->child[c] == NULL) p->child[c] = new Node();",
  570. 			  "            p = p->child[c]; p->cnt++;",
  571. 			  "        }",
  572. 			  "        p->exist++;",
  573. 			  "    }",
  574. 			  "",
  575. 			  "    bool delete_str(Node *p, string& s, i64 i) {",
  576. 			  "        if (i != (i64)s.size()) {",
  577. 			  "            i64 c = s[i] - 'a';",
  578. 			  "            bool is_deleted = delete_str(p->child[c], s, i + 1);",
  579. 			  "            if (is_deleted) p->child[c] = NULL;",
  580. 			  "        }",
  581. 			  "        else p->exist--;",
  582. 			  "        if (p != root) {",
  583. 			  "            p->cnt--;",
  584. 			  "            if (p->cnt == 0) {delete(p); return true;}",
  585. 			  "        }",
  586. 			  "        return false;",
  587. 			  "    }",
  588. 			  "    void erase(string s) {",
  589. 			  "        if (find(s) == false) return;",
  590. 			  "        delete_str(root, s, 0);",
  591. 			  "    }",
  592. 			  "    bool find(string s) {",
  593. 			  "        Node *p = root;",
  594. 			  "        for (auto f : s) {",
  595. 			  "            i64 c = f - 'a';",
  596. 			  "            if (p->child[c] == NULL) return false;",
  597. 			  "            p = p->child[c];",
  598. 			  "        }",
  599. 			  "        return (p->exist != 0);",
  600. 			  "    }",
  601. 			  "};"
  602. 			],
  603. 			"description": "Trie"
  604. 		  }
  605.  
  606. 		  "LIS": {
  607. 			"prefix": "LIS",
  608. 			"body": [
  609. 			  "void tracei64S(const vector<i32>& a, const vector<i32>& dp, const vector<i32>& b, vector<i32>& trace){",
  610. 			  "    i32 res = *max_element(dp.begin(), dp.end()) + 1;",
  611. 			  "    for(i32 p = b.size() - 1; p >= 0; p --) if (res == dp[p] + 1) res--, trace.push_back(a[p]);",
  612. 			  "    reverse(all(trace));",
  613. 			  "}",
  614. 			  "i64 LIS(vector<i32>& a, bool with_trace, vector<i32>& trace){",
  615. 			  "    i64 n = a.size(); vector<i32> b(n, inf), dp(n, 0);",
  616. 			  "    i64 res = 1;",
  617. 			  "    for(i32 i = 0; i < n; i ++) {",
  618. 			  "        dp[i] = lower_bound(b.begin(), b.begin() + res, a[i]) - b.begin();",
  619. 			  "        res = max(res, dp[i] + 1);",
  620. 			  "        b[dp[i]] = a[i];",
  621. 			  "    }",
  622. 			  "    if(with_trace) tracei64S(a, dp, b, trace);",
  623. 			  "    return res;",
  624. 			  "}"
  625. 			],
  626. 			"description": "LIS"
  627. 		  }
  628.  
  629. 		  "LISpair": {
  630. 			"prefix": "LISpair",
  631. 			"body": [
  632. 			  "void tracei64S(const vii& a, const vector<i32>& dp, const vector<i32>& b, vii& trace){",
  633. 			  "    i32 res = *max_element(dp.begin(), dp.end()) + 1;",
  634. 			  "    for(i32 p = b.size() - 1; p >= 0; p --) if (res == dp[p] + 1) res--, trace.push_back(a[p]);",
  635. 			  "    reverse(all(trace));",
  636. 			  "}",
  637. 			  "",
  638. 			  "i64 LIS(vii& a, bool with_trace, vii& trace){",
  639. 			  "    i64 n = a.size();",
  640. 			  "    vector<i32> b(n, inf), dp(n, 0);",
  641. 			  "    sort(all(a));",
  642. 			  "    i64 res = 1;",
  643. 			  "    for(i32 i = 0; i < n; i ++) {",
  644. 			  "        dp[i] = lower_bound(b.begin(), b.begin() + res, a[i].se) - b.begin();",
  645. 			  "        res = max(res, dp[i] + 1);",
  646. 			  "        b[dp[i]] = a[i].se;",
  647. 			  "    }",
  648. 			  "    if(with_trace) tracei64S(a, dp, b, trace);",
  649. 			  "    return res;",
  650. 			  "}"
  651. 			],
  652. 			"description": "LISpair"
  653. 		  }
  654.  
  655. 		  "Matrix": {
  656.   "prefix": "Matrix",
  657.   "body": [
  658.     "class Matrix {",
  659.     "private:",
  660.     "    i64 row, col;",
  661.     "    vector<vector<i64>> data;",
  662.     "",
  663.     "public:",
  664.     "    Matrix(const vector<vector<i64>>& base) {",
  665.     "        row = base.size();",
  666.     "        col = base[0].size();",
  667.     "        data = base;",
  668.     "    }",
  669.     "    Matrix(i64 r, i64 c, i64 val) : row(r), col(c), data(vector<vector<i64>>(r, vector<i64>(c, val))) {}",
  670.     "    void fill(const i64& that){for(i32 i = 0; i < data.size(); i ++) for(i32 j = 0; j < data[i].size(); j ++) data[i][j] = that;}",
  671.     "    void fix(const i64& cur, const i64& that){ for(i32 i = 0; i < data.size(); i ++) for(i32 j = 0; j < data[i].size(); j ++) if(data[i][j] == cur) data[i][j] = that;}",
  672.     "    Matrix& operator=(const Matrix& that) {",
  673.     "        if (this != &that) {",
  674.     "            row = that.row;",
  675.     "            col = that.col;",
  676.     "            data = that.data;",
  677.     "        }",
  678.     "        return *this;",
  679.     "    }",
  680.     "    static i64 multiply(i64 a, i64 b){",
  681.     "        if(M <= 1e9 + 7) return (a * b) % M;",
  682.     "        i64 res = 0;",
  683.     "        a %= M;",
  684.     "        while (b > 0) {",
  685.     "            if (b & 1)",
  686.     "                res = (res + a) % M;",
  687.     "            a = (2 * a) % M;",
  688.     "            b >>= 1;",
  689.     "        }",
  690.     "        return res;",
  691.     "    }",
  692.     "",
  693.     "    static i64 cal(i64 a, i64 b){return (a + b) % M;}",
  694.     "    Matrix operator*(const Matrix& that) const {",
  695.     "        if (col != that.row) throw std::runtime_error(\"segmentation fault\");",
  696.     "        Matrix res(row, that.col, 0);",
  697.     "        for(i32 i = 0; i < row; i ++) ",
  698.     "            for(i32 j = 0; j < that.col; j ++) ",
  699.     "                for(i32 k = 0; k < col; k ++) ",
  700.     "                    res.data[i][j] = cal(res.data[i][j], multiply(data[i][k], that.data[k][j]));",
  701.     "        return res;",
  702.     "    }",
  703.     "    Matrix operator^(i64 exp){",
  704.     "        i64 i = row;",
  705.     "        Matrix res(i, i, 0);",
  706.     "        Matrix temp = *this;",
  707.     "        for(i32 j = 0; j < i; j ++) res.data[j][j] = 1;",
  708.     "        while (exp) {",
  709.     "            if (exp & 1) res = res * temp;",
  710.     "            temp = temp * temp;",
  711.     "            exp >>= 1;",
  712.     "        }",
  713.     "        return res;",
  714.     "    }",
  715.     "    Matrix& operator*=(const Matrix& that) {",
  716.     "        if (col != that.row) throw std::runtime_error(\"segmentation fault\");",
  717.     "        Matrix result = (*this) * that;",
  718.     "        (*this) = result;",
  719.     "        return *this;",
  720.     "    }",
  721.     "    Matrix& operator^=(i64 exp) {",
  722.     "        if (exp == 0) {",
  723.     "            Matrix res(row, col, 0);",
  724.     "            for(i32 i = 0; i < row; i ++) res[i][i] = 1;",
  725.     "            (*this) = res;",
  726.     "            return *this;",
  727.     "        }",
  728.     "        Matrix res = *this;",
  729.     "        exp--;",
  730.     "        while (exp > 0) {",
  731.     "            if (exp & 1) (*this) *= res;",
  732.     "            res *= res;",
  733.     "            exp >>= 1;",
  734.     "        }",
  735.     "        return *this;",
  736.     "    }",
  737.     "    bool operator==(const Matrix& that) const {",
  738.     "        if (row != that.row || col != that.col) return false;",
  739.     "        for(i32 i = 0; i < row; i ++) ",
  740.     "            for(i32 j = 0; j < col; j ++) ",
  741.     "                if (data[i][j] != that.data[i][j]) return false;",
  742.     "        return true;",
  743.     "    }",
  744.     "    const vector<i64>& operator[](i32 i) const {return data[i];}",
  745.     "    vector<i64>& operator[](i32 i) {return data[i];}",
  746.     "    void print() const {",
  747.     "        for(i32 i = 0; i < row; i ++){",
  748.     "            for(i32 j = 0; j < col; j ++){",
  749.     "                cout << data[i][j] << \" \";",
  750.     "            }",
  751.     "            cout << endl;",
  752.     "        }",
  753.     "    }",
  754.     "};"
  755.   ],
  756.   "description": "Matrix"
  757. }
  758.  
  759. 		  "BerklampMassey": {
  760. 			"prefix": "BerklampMassey",
  761. 			"body": [
  762. 			  "i64 power(i64 base, i64 exp, i64 mod) {",
  763. 			  "    i64 temp = base, res = 1;",
  764. 			  "    while (exp) {",
  765. 			  "        if (exp % 2) res = (res * temp) % mod;",
  766. 			  "        temp = (temp * temp) % mod;",
  767. 			  "        exp /= 2;",
  768. 			  "    }",
  769. 			  "    return res;",
  770. 			  "}",
  771. 			  "",
  772. 			  "template<typename T>",
  773. 			  "vector<T> berlekampMassey(vector<T> s) {",
  774. 			  "    if (s.empty()) return {};",
  775. 			  "",
  776. 			  "    i32 n = s.size(), L = 0, m = 0; // m = i - f",
  777. 			  "    vector<T> C(n), D(n), oldC;",
  778. 			  "    C[0] = D[0] = 1;",
  779. 			  "    T df1 = 1;  // d(f+1)",
  780. 			  "    for (i32 i = 0; i < n; i++) {",
  781. 			  "        ++m;",
  782. 			  "        // check if C(i) == a(i)",
  783. 			  "        // delta = s_i - sum( cj * s(i-j) ) = d(f+1)?",
  784. 			  "        T delta = s[i];",
  785. 			  "        for (i32 j = 1; j <= L; j++) {",
  786. 			  "            delta += C[j] * s[i-j];  // C(j) is already multipi64ed by -1",
  787. 			  "            delta %= mod;",
  788. 			  "        }",
  789. 			  "        if (delta == 0) continue;  // C(i) is correct",
  790. 			  "",
  791. 			  "        // Update c = c + d",
  792. 			  "        oldC = C;",
  793. 			  "        T coeff = delta * power(df1, mod - 2, mod) % mod;",
  794. 			  "        for (i32 j = m; j < n; j++) {",
  795. 			  "            C[j] -= coeff * D[j - m];  // prepend D with m zeroes, multiply by coeff and add to C",
  796. 			  "            C[j] = (C[j] + mod * mod) % mod;",
  797. 			  "        }",
  798. 			  "        if (2*L > i) continue;",
  799. 			  "        L = i + 1 - L, D = oldC, df1 = delta, m = 0;",
  800. 			  "    }",
  801. 			  "    C.resize(L + 1);",
  802. 			  "    C.erase(C.begin());",
  803. 			  "    for (auto& x : C) x = -x, x = (x + mod * mod) % mod;",
  804. 			  "    return C;",
  805. 			  "}",
  806. 			  "",
  807. 			  "// Helper function",
  808. 			  "template<typename T>",
  809. 			  "vector<T> mul(const vector<T> &a, const vector<T> &b, const vector<T>& c) {",
  810. 			  "    vector<T> ret(a.size() + b.size() - 1);",
  811. 			  "    // ret = a * b",
  812. 			  "    for (i32 i=0; i<(i32)a.size(); i++)",
  813. 			  "        for (i32 j=0; j<(i32)b.size(); j++)",
  814. 			  "            ret[i+j] += a[i] * b[j], ret[i + j] %= mod;",
  815. 			  "",
  816. 			  "    i32 n = c.size();",
  817. 			  "    // reducing ret mod f(x)",
  818. 			  "    for (i32 i=(i32)ret.size()-1; i>=n; i--)",
  819. 			  "        for (i32 j=n-1; j>=0; j--)",
  820. 			  "            ret[i-j-1] += ret[i] * c[j], ret[i - j - 1] %= mod;",
  821. 			  "    ret.resize(min((i32) ret.size(), n));",
  822. 			  "    return ret;",
  823. 			  "}",
  824. 			  "",
  825. 			  "// Find k-th element in i64near recurrence: O(d^2 * logn)",
  826. 			  "// Need faster code? See https://j...content-available-to-author-only...o.jp/problem/kth_term_of_i64nearly_recurrent_sequence",
  827. 			  "//   (but usually not needed since bottleneck is BerlekampMassey",
  828. 			  "//",
  829. 			  "// Params:",
  830. 			  "// - c: as returned by berlekampMassey",
  831. 			  "// - s: s0, s1, ..., s(N-1)",
  832. 			  "// Returns: s(k)",
  833. 			  "template<typename T>",
  834. 			  "T check(const vector<T> &c, const vector<T> &s, i64 k) {",
  835. 			  "    i32 n = (i32) c.size();",
  836. 			  "    assert(c.size() <= s.size());",
  837. 			  "",
  838. 			  "    vector<T> a = n == 1 ? vector<T>{c[0]} : vector<T>{0, 1}, x{1};",
  839. 			  "    for (; k>0; k/=2) {",
  840. 			  "        if (k % 2)",
  841. 			  "            x = mul(x, a, c);  // mul(a, b) computes a(x) * b(x) mod f(x)",
  842. 			  "        a = mul(a, a, c);",
  843. 			  "    }",
  844. 			  "    x.resize(n);",
  845. 			  "",
  846. 			  "    T ret = 0;",
  847. 			  "    for (i32 i=0; i<n; i++)",
  848. 			  "        ret += x[i] * s[i], ret %= mod;",
  849. 			  "    return ret;",
  850. 			  "}",
  851. 			  "",
  852. 			  "// Result for f[n]",
  853. 			  "template<typename T>",
  854. 			  "T main_cal(const vector<T> &f, i64 k) {",
  855. 			  "    vector<i64> c = berlekampMassey(f);",
  856. 			  "    return check(c, f, k);",
  857. 			  "}"
  858. 			],
  859. 			"description": "BerklampMassey"
  860. 		  }
  861.  
  862. 		  "dptools": {
  863.   "prefix": "dptools",
  864.   "body": [
  865.     "void add(i32 &a, i32 b) {a = (a + b) % M;}",
  866.     "void gmin(i32 &a, i32 b) {a = min(a, b);}",
  867.     "void gmax(i32 &a, i32 b) {a = max(a, b);}",
  868.     "bool get(i32 mask, i32 idx){return ((mask >> idx) & 1);}",
  869.     "void print(i32 mask, string s) {bitset<3> a(mask); cout << a.to_string() << s;}"
  870.   ],
  871.   "description": "dptools"
  872. }
  873. 		  "Tree": {
  874.   "prefix": "Tree",
  875.   "body": [
  876.     "class Tree{",
  877.     "    private:",
  878.     "        vv<vv<i32>> up;",
  879.     "        vv<i32> h;",
  880.     "        i32 n;",
  881.     "    public:",
  882.     "        Tree(i32 size, vv<vv<i32>>& a) : n(size) {",
  883.     "            up = vv<vv<i32>>(__lg(n) + 1, vv<i32>(n, 0));",
  884.     "            h = vv<i32>(n, 0);",
  885.     "            queue<i32> q; q.push(0);",
  886.     "            while (!q.empty()) {",
  887.     "                i32 node = q.front(); q.pop();",
  888.     "                for (auto x : a[node]) {",
  889.     "                    if (x == up[0][node]) continue;",
  890.     "                    up[0][x] = node;",
  891.     "                    h[x] = h[node] + 1;",
  892.     "                    q.push(x);",
  893.     "                }",
  894.     "            }",
  895.     "            for (i16 i = 1; i <= __lg(n); i++)",
  896.     "                for (i32 j = 0; j < n; j++)",
  897.     "                    up[i][j] = up[i - 1][up[i - 1][j]];",
  898.     "        }",
  899.     "        i32 lca(i32 u, i32 v) {",
  900.     "            if (h[u] > h[v]) swap(u, v);",
  901.     "            if (h[u] != h[v]) {",
  902.     "                i32 dif = h[v] - h[u];",
  903.     "                for (i16 i = __lg(dif); i >= 0; i--)",
  904.     "                    if (dif >= (1 << i)) v = up[i][v], dif -= (1 << i);",
  905.     "            }",
  906.     "            if (u == v) return u;",
  907.     "            for (i16 i = __lg(n); i >= 0; i--)",
  908.     "                if (up[i][u] != up[i][v])",
  909.     "                    u = up[i][u], v = up[i][v];",
  910.     "            return up[0][u];",
  911.     "        }",
  912.     "};",
  913.     ""
  914.   ],
  915.   "description": "Tree"
  916. }
  917.  
  918. "DisjointSets": {
  919.   "prefix": "DisjointSets",
  920.   "body": [
  921.     "struct Save {",
  922.     "    i32 v, rnkv, u, rnku;",
  923.     "    Save() {}",
  924.     "    Save(i32 _v, i32 _rnkv, i32 _u, i32 _rnku)",
  925.     "        : v(_v), rnkv(_rnkv), u(_u), rnku(_rnku) {}",
  926.     "};",
  927.     "struct DisjointSets {",
  928.     "    vector<i32> par, rank;",
  929.     "    i32 comps;",
  930.     "    vector<Save> history;",
  931.     "",
  932.     "    DisjointSets() {}",
  933.     "    DisjointSets(i32 n) {",
  934.     "        par.resize(n); rank.resize(n, 0);",
  935.     "        for (i32 i = 0; i < n; i++) par[i] = i;",
  936.     "        comps = n;",
  937.     "    }",
  938.     "",
  939.     "    i32 root(i32 v) {",
  940.     "        return (v == par[v]) ? v : root(par[v]);",
  941.     "    }",
  942.     "",
  943.     "    bool merge(i32 v, i32 u) {",
  944.     "        v = root(v); u = root(u);",
  945.     "        if (v == u) return false;",
  946.     "        comps--;",
  947.     "        if (rank[v] > rank[u]) swap(v, u);",
  948.     "        history.push_back(Save(v, rank[v], u, rank[u]));",
  949.     "        par[v] = u;",
  950.     "        if (rank[u] == rank[v]) rank[u] ++;",
  951.     "        return true;",
  952.     "    }",
  953.     "",
  954.     "    void rollback() {",
  955.     "        if (history.empty()) return;",
  956.     "        Save x = history.back();",
  957.     "        history.pop_back();",
  958.     "        par[x.v] = x.v; rank[x.v] = x.rnkv;",
  959.     "        par[x.u] = x.u; rank[x.u] = x.rnku;",
  960.     "        comps++;",
  961.     "    }",
  962.     "};"
  963.   ],
  964.   "description": "DisjointSets"
  965. }
  966. "SqrtDecomposition": {
  967.   "prefix": "SqrtDecomposition",
  968.   "body": [
  969.     "vector<vector<i32>> blocks;",
  970.     "vector<vector<i32>> block_freq;",
  971.     "i32 block_size; i32 sq_temp[N];",
  972.     "void sqrt_decomposition(i32 n, i32 k) {",
  973.     "    block_size = sqrt(n);",
  974.     "    blocks.resize((n + block_size - 1) / block_size);",
  975.     "    block_freq.resize(blocks.size(), vector<i32>(k));",
  976.     "    for(i32 i = 0; i < n; i++) {",
  977.     "        blocks[i / block_size].push_back(sq_temp[i]);",
  978.     "        block_freq[i / block_size][sq_temp[i]]++;",
  979.     "    }",
  980.     "}",
  981.     "i32 sqrt_query(i32 q_l, i32 q_r, i32 k) {",
  982.     "    i32 block_l = q_l / block_size;",
  983.     "    i32 block_r = q_r / block_size, cnt = 0;",
  984.     "    if (block_l == block_r) {",
  985.     "        for (i32 i = q_l; i <= q_r; i++) ",
  986.     "            if(sq_temp[i] < k) cnt ++;",
  987.     "    } ",
  988.     "    else {",
  989.     "        for (i32 i = q_l; i < (block_l + 1) * block_size; i++) ",
  990.     "            if(sq_temp[i] < k) cnt++;",
  991.     "        for (i32 i = block_l + 1; i < block_r; i++) ",
  992.     "            for (i32 j = 0; j < k; j++) ",
  993.     "                cnt += block_freq[i][j];",
  994.     "        for (i32 i = block_r * block_size; i <= q_r; i++) ",
  995.     "            if(sq_temp[i] < k) cnt ++;",
  996.     "    }",
  997.     "    return cnt;",
  998.     "}"
  999.   ],
  1000.   "description": "SqrtDecomposition"
  1001. }
  1002.  
  1003. "FenwickTree": {
  1004.   "prefix": "FenwickTree",
  1005.   "body": [
  1006.     "struct FenwickTree {",
  1007.     "    vector<i64> node;",
  1008.     "    FenwickTree(i32 n) : node(n + 8, 0) {}",
  1009.     "    void update(i32 pos, i64 val) {",
  1010.     "        for (; pos < node.size(); pos += pos & -pos) ",
  1011.     "            node[pos] += val;",
  1012.     "    }",
  1013.     "    i64 getSum(i32 pos) {",
  1014.     "        i64 res = 0;",
  1015.     "        for (; pos > 0; pos -= pos & -pos) ",
  1016.     "            res += node[pos];",
  1017.     "        return res;",
  1018.     "    }",
  1019.     "    i64 get(i32 l, i32 r) {",
  1020.     "        return getSum(r) - getSum(l - 1);",
  1021.     "    }",
  1022.     "};",
  1023.     ""
  1024.   ],
  1025.   "description": "FenwickTree"
  1026. }
  1027.  
  1028. "FenwickTree2D": {
  1029.   "prefix": "FenwickTree2D",
  1030.   "body": [
  1031.     "struct FenwickTree2D {",
  1032.     "    vector<vector<i64>> node;",
  1033.     "    FenwickTree2D(i32 n, i32 m) : node(n + 8, vector<i64>(m + 8, 0)) {}",
  1034.     "    void update(i32 x, i32 y, i64 val) {",
  1035.     "        for (i32 i = x; i < node.size(); i += i & -i) ",
  1036.     "            for (i32 j = y; j < node[0].size(); j += j & -j) ",
  1037.     "                node[i][j] += val;",
  1038.     "    }",
  1039.     "    i64 getSum(i32 x, i32 y) {",
  1040.     "        i64 res = 0;",
  1041.     "        for (i32 i = x; i > 0; i -= i & -i) ",
  1042.     "            for (i32 j = y; j > 0; j -= j & -j) ",
  1043.     "                res += node[i][j];",
  1044.     "        return res;",
  1045.     "    }",
  1046.     "    i64 get(i32 x1, i32 y1, i32 x2, i32 y2) {",
  1047.     "        return getSum(x2, y2) - getSum(x1 - 1, y2) - getSum(x2, y1 - 1) + getSum(x1 - 1, y1 - 1);",
  1048.     "    }",
  1049.     "};",
  1050.     ""
  1051.   ],
  1052.   "description": "FenwickTree2D"
  1053. }
  1054.  
  1055. "FenwickTree3D": {
  1056.   "prefix": "FenwickTree3D",
  1057.   "body": [
  1058.     "struct FenwickTree3D {",
  1059.     "    vector<vector<vector<i64>>> node;",
  1060.     "    FenwickTree3D(i32 n, i32 m, i32 p) : node(n + 8, vector<vector<i64>>(m + 8, vector<i64>(p + 8, 0))) {}",
  1061.     "    ",
  1062.     "    void update(i32 x, i32 y, i32 z, i64 val) {",
  1063.     "        for (i32 i = x; i < node.size(); i += i & -i) ",
  1064.     "            for (i32 j = y; j < node[0].size(); j += j & -j) ",
  1065.     "                for (i32 k = z; k < node[0][0].size(); k += k & -k) ",
  1066.     "                    node[i][j][k] += val;",
  1067.     "    }",
  1068.     "",
  1069.     "    i64 getSum(i32 x, i32 y, i32 z) {",
  1070.     "        i64 res = 0;",
  1071.     "        for (i32 i = x; i > 0; i -= i & -i) ",
  1072.     "            for (i32 j = y; j > 0; j -= j & -j) ",
  1073.     "                for (i32 k = z; k > 0; k -= k & -k) ",
  1074.     "                    res += node[i][j][k];",
  1075.     "        return res;",
  1076.     "    }",
  1077.     "    ",
  1078.     "    i64 get(i32 x1, i32 y1, i32 z1, i32 x2, i32 y2, i32 z2) {",
  1079.     "        return getSum(x2, y2, z2) ",
  1080.     "            - getSum(x1 - 1, y2, z2) - getSum(x2, y1 - 1, z2) - getSum(x2, y2, z1 - 1)",
  1081.     "            + getSum(x1 - 1, y1 - 1, z2) + getSum(x1 - 1, y2, z1 - 1) + getSum(x2, y1 - 1, z1 - 1)",
  1082.     "            - getSum(x1 - 1, y1 - 1, z1 - 1);",
  1083.     "    }",
  1084.     "};",
  1085.     ""
  1086.   ],
  1087.   "description": "FenwickTree3D"
  1088. }
  1089.  
  1090. "FastSet": {
  1091.   "prefix": "FastSet",
  1092.   "body": [
  1093.     "struct FastSet {",
  1094.     "    static constexpr i32 BASE = 6;",
  1095.     "    static constexpr i32 RANGE = 1 << BASE;",
  1096.     "    static constexpr i32 FILTER = RANGE - 1;",
  1097.     "    i32 N, log;",
  1098.     "    vector<vector<i64>> seg;",
  1099.     "",
  1100.     "    FastSet(i32 _N = 0, bool val = 0) { build(_N, val); }",
  1101.     "    ",
  1102.     "    void build(i32 _N = 0, bool val = 0) {",
  1103.     "        seg.clear(); N = _N, log = 0;",
  1104.     "        while(true) {",
  1105.     "            seg.emplace_back((_N + FILTER) >> BASE, (val ? ~0ull : 0ull)); ++log;",
  1106.     "            if(seg.back().size() <= 1) break;",
  1107.     "            _N = seg.back().size();",
  1108.     "        }",
  1109.     "    }",
  1110.     "    ",
  1111.     "    void insert(i32 k) {",
  1112.     "        i32 id = k >> BASE;",
  1113.     "        for(i32 i = 0; i < seg.size(); ++i, k >>= BASE, id >>= BASE) {",
  1114.     "            if(seg[i][id] >> (k & FILTER) & 1) break;",
  1115.     "            seg[i][id] |= i64(1) << (k & FILTER);",
  1116.     "        }",
  1117.     "    }",
  1118.     "",
  1119.     "    void erase(i32 k) {",
  1120.     "        if(!(*this)[k]) return;",
  1121.     "        i32 id = k >> BASE;",
  1122.     "        for(i32 i = 0; i < seg.size(); ++i, k >>= BASE, id >>= BASE) {",
  1123.     "            seg[i][id] ^= i64(1) << (k & FILTER);",
  1124.     "            if(bool(seg[i][id])) break;",
  1125.     "        }",
  1126.     "    }",
  1127.     "",
  1128.     "    bool operator[](i32 k) {",
  1129.     "        assert(0 <= k && k < N);",
  1130.     "        return seg[0][k >> BASE] >> (k & FILTER) & 1;",
  1131.     "    }",
  1132.     "",
  1133.     "    i32 next(i32 k) {",
  1134.     "        i32 id = k >> BASE;",
  1135.     "        for(i32 i = 0; i < seg.size(); ++i) {",
  1136.     "            if((id = (k >> BASE)) >= seg[i].size()) break;",
  1137.     "            i64 x = seg[i][id] >> (k & FILTER);",
  1138.     "            if(!x) { k = id + 1; continue; }",
  1139.     "            k += __builtin_ctzll(x);",
  1140.     "            for(i32 j = i - 1; j >= 0; --j) k = (k << 6) | __builtin_ctzll(seg[j][k]);",
  1141.     "            return k;",
  1142.     "        }",
  1143.     "        return N;",
  1144.     "    }",
  1145.     "",
  1146.     "    i32 prev(i32 k) {",
  1147.     "        k = min(k, N - 1);",
  1148.     "        i32 id;",
  1149.     "        for(i32 i = 0; i < seg.size(); ++i) {",
  1150.     "            if(k < 0) break;",
  1151.     "            i64 x = seg[i][id = (k >> BASE)] << (FILTER - (k & FILTER));",
  1152.     "            if(!x) { k = id - 1; continue; }",
  1153.     "            k -= __builtin_clz
  1154. 	ll(x);",
  1155.     "            for(i32 j = i - 1; j >= 0; --j) k = (k << BASE) | (FILTER - __builtin_clzll(seg[j][k]));",
  1156.     "            return k;",
  1157.     "        }",
  1158.     "        return -1;",
  1159.     "    }",
  1160.     "};"
  1161.   ],
  1162.   "description": "FastSet"
  1163. }
  1164. "ConvexHullTrick": {
  1165.   "prefix": "ConvexHullTrick",
  1166.   "body": [
  1167.     "struct Line {",
  1168.     "    mutable i64 k, m, p;",
  1169.     "    bool operator<(const Line& o) const {return k < o.k;}",
  1170.     "    bool operator<(i64 x) const {return p < x;}",
  1171.     "};",
  1172.     "struct ConvexHullTrick : multiset<Line, less<>> {",
  1173.     "    static const i64 INF = LLONG_MAX;",
  1174.     "    i64 div(i64 a, i64 b) {",
  1175.     "        return a / b - ((a ^ b) < 0 && a % b); ",
  1176.     "    }",
  1177.     "    bool isect(iterator x, iterator y) {",
  1178.     "        if (y == end()) return x->p = INF, 0;",
  1179.     "        if (x->k == y->k) x->p = x->m > y->m ? INF : -INF;",
  1180.     "        else x->p = div(y->m - x->m, x->k - y->k);",
  1181.     "        return x->p >= y->p;",
  1182.     "    }",
  1183.     "    void push(i64 k, i64 m) {",
  1184.     "        auto z = insert({k, m, 0}), y = z ++, x = y;",
  1185.     "        while (isect(y, z)) z = erase(z);",
  1186.     "        if (x != begin() && isect(-- x, y)) isect(x, y = erase(y));",
  1187.     "        while ((y = x) != begin() && (-- x)->p >= y->p)",
  1188.     "        isect(x, erase(y));",
  1189.     "    }",
  1190.     "    i64 get(i64 x) {",
  1191.     "        assert(!empty());",
  1192.     "        auto l = *lower_bound(x);",
  1193.     "        return l.k * x + l.m;",
  1194.     "    }",
  1195.     "};",
  1196.     ""
  1197.   ],
  1198.   "description": "ConvexHullTrick"
  1199. }
  1200. "FastSegmentTree": {
  1201.   "prefix": "FastSegmentTree",
  1202.   "body": [
  1203.     "#include <immintrin.h> ",
  1204.     "const int _SIZE = 1 << 20, INF = 1e9 + 9;",
  1205.     "using T = uint32_t;",
  1206.     "T st[2 * _SIZE]; ",
  1207.     "const T identity_element = INF;  ",
  1208.     "__attribute__((target(\"avx2\"))) __m256i reduce(__m256i a, __m256i b) {",
  1209.     "    return _mm256_min_epi32(a, b);",
  1210.     "}",
  1211.     "T reduce(T a, T b) {",
  1212.     "    return min(a, b);",
  1213.     "}",
  1214.     "void build(int n, const T a[]) {",
  1215.     "    for (int i = 0; i < n; i++) st[i + _SIZE] = a[i + 1];",
  1216.     "    for (int i = _SIZE - 1; i > 0; i--) {",
  1217.     "        st[i] = reduce(st[i << 1], st[i << 1 | 1]);",
  1218.     "    }",
  1219.     "}",
  1220.     "__attribute__((target(\"avx2\"))) T query_parallel(int l, int r) {",
  1221.     "    T res = identity_element;",
  1222.     "    l += _SIZE, r += _SIZE;",
  1223.     "    __m256i vec_res = _mm256_set1_epi32(res);  ",
  1224.     "",
  1225.     "    while (l <= r) {",
  1226.     "        if (l & 1) {",
  1227.     "            __m256i vec_l = _mm256_set1_epi32(st[l]);",
  1228.     "            vec_res = reduce(vec_res, vec_l); ",
  1229.     "            ++l;",
  1230.     "        }",
  1231.     "        if (!(r & 1)) {",
  1232.     "            __m256i vec_r = _mm256_set1_epi32(st[r]);",
  1233.     "            vec_res = reduce(vec_res, vec_r);  ",
  1234.     "            --r;",
  1235.     "        }",
  1236.     "        l >>= 1, r >>= 1;",
  1237.     "    }",
  1238.     "",
  1239.     "    T result[8];",
  1240.     "    _mm256_storeu_si256((__m256i*)result, vec_res);",
  1241.     "    for (int i = 0; i < 8; i++) {",
  1242.     "        res = reduce(res, result[i]);",
  1243.     "    }",
  1244.     "    return res;",
  1245.     "}",
  1246.     "void upd(int p, T val) {",
  1247.     "    for (st[p += _SIZE] = val; p > 1; p >>= 1) {",
  1248.     "        st[p >> 1] = reduce(st[p], st[p ^ 1]);",
  1249.     "    }",
  1250.     "}",
  1251.     "void update(int pos, int val) {upd(pos - 1, val);}",
  1252.     "T get(int l, int r) {return query_parallel(l - 1, r - 1);}"
  1253.   ],
  1254.   "description": "FastSegmentTree"
  1255. },
  1256.  
  1257. "Checker": {
  1258.   "prefix": "Checker",
  1259.   "body": [
  1260.     "#include <bits/stdc++.h>",
  1261.     "using namespace std;",
  1262.     "",
  1263.     "using i32 = int32_t;",
  1264.     "using i64 = int64_t;",
  1265.     "",
  1266.     "template<class T>",
  1267.     "using v = vector<T>;",
  1268.     "",
  1269.     "#define all(a) (a).begin(), (a).end()",
  1270.     "",
  1271.     "string file = \"DRAWATREE\";",
  1272.     "",
  1273.     "i64 rand(i64 l, i64 h) {",
  1274.     "    return l + (rand() % (h - l + 1));",
  1275.     "}",
  1276.     "",
  1277.     "void check() {",
  1278.     "    ofstream out(file + \".inp\");",
  1279.     "",
  1280.     "    i32 n = 600; out << n << endl;",
  1281.     "    for (i32 i = 0; i < n - 1; i++) {",
  1282.     "        for (i32 j = i + 1; j < n; j++) {",
  1283.     "            out << (rand(0, 2) == 0? 'N' : 'Y');",
  1284.     "        }",
  1285.     "        out << endl;",
  1286.     "    }",
  1287.     "",
  1288.     "    out.close();",
  1289.     "}",
  1290.     "",
  1291.     "void sad(i32 testID) {",
  1292.     "    srand(time(NULL));",
  1293.     "    for (i32 i = 1; i <= 100; i++) { ",
  1294.     "        check();",
  1295.     "        system((file + \".exe\").c_str());      ",
  1296.     "        system((file + \"_trau.exe\").c_str());  ",
  1297.     "        if (system((\"fc \" + (file + \".out\") + \" \" + (file + \".ans\")).c_str())) {",
  1298.     "            // cout << \"Test \" << i << \" failed!\\n\";",
  1299.     "            return;",
  1300.     "        }",
  1301.     "    }",
  1302.     "}",
  1303.     "",
  1304.     "i32 main() {",
  1305.     "    ios_base::sync_with_stdio(false);",
  1306.     "    cin.tie(NULL); cout.tie(NULL);",
  1307.     "",
  1308.     "    i32 t = 1;",
  1309.     "    for (i32 testID = 1; testID <= t; testID++) {",
  1310.     "        sad(testID);",
  1311.     "    }",
  1312.     "    return 0;",
  1313.     "}",
  1314.     ""
  1315.   ],
  1316.   "description": "Checker"
  1317. },
  1318. "mul": {
  1319.   "prefix": "mul",
  1320.   "body": [
  1321.     "ui64 modmul(ui64 a, ui64 b, ui64 M){",
  1322.     "    i64 ret = a * b - M * ui64(1.L / M * a * b);",
  1323.     "    return ret + M * (ret < 0) - M * (ret >= (i64)M);",
  1324.     "}"
  1325.   ],
  1326.   "description": "mul"
  1327. }
  1328. "PollardRho": {
  1329.   "prefix": "PollardRho",
  1330.   "body": [
  1331.     "ui64 PollardRho(ui64 n){",
  1332.     "    auto f = [n](ui64 x){return modmul(x, x, n) + 1;};",
  1333.     "    ui64 x=0, y=0, t=30, prd=2, i=1, q;",
  1334.     "    while (t++ % 40 || __gcd(prd, n) == 1){",
  1335.     "        if (x == y) x = ++i, y = f(x);",
  1336.     "        if ((q = modmul(prd, max(x, y) - min(x, y), n))) prd = q;",
  1337.     "        x = f(x), y = f(f(y));",
  1338.     "    }",
  1339.     "    return __gcd(prd, n);",
  1340.     "}",
  1341.     "vector<ui64> factor(ui64 n){",
  1342.     "    if (n == 1) return{};",
  1343.     "}"
  1344.   ],
  1345.   "description": "PollardRho"
  1346. }
  1347. "BetterSieve": {
  1348.   "prefix": "BetterSieve",
  1349.   "body": [
  1350.     "vector<i32> _checkPrime(N >> 6), _prime;",
  1351.     "void Sieve() {",
  1352.     "    #define set(n) (_checkPrime[n >> 6] |= (1<<((n & 63) >> 1)))",
  1353.     "    #define get(n) (_checkPrime[n >> 6] & (1 << ((n & 63) >> 1)))",
  1354.     "    ",
  1355.     "    _prime.push_back(2); i32 t = sqrt(N);",
  1356.     "    for (i32 i = 3; i < N; i += 2)",
  1357.     "        if (!get(i)) {",
  1358.     "            _prime.push_back(i);",
  1359.     "            if (i > t) continue;",
  1360.     "            for (i32 j = i * i; j < N; j += (i << 1)) set(j);",
  1361.     "        }",
  1362.     "}"
  1363.   ],
  1364.   "description": "BetterSieve"
  1365. }
  1366. "gcd_withExtendedEuclidean": {
  1367.   "prefix": "gcd_withExtendedEuclidean",
  1368.   "body": [
  1369.     "i64 gcd_withExtendedEuclidean(i64 a, i64 b, i64 &x, i64 &y) {",
  1370.     "    if (b == 0) {x = 1, y = 0; return a;}",
  1371.     "    i64 x1, y1, g = gcd_withExtendedEuclidean(b, a % b, x1, y1);",
  1372.     "    x = y1; y = x1 - a / b * y1;",
  1373.     "    return g;",
  1374.     "}"
  1375.   ],
  1376.   "description": "gcd_withExtendedEuclidean"
  1377. }
  1378. "custom_hash ": {
  1379.   "prefix": "custom_hash ",
  1380.   "body": [
  1381.     "// Source: http://x...content-available-to-author-only...i.it/splitmix64.c",
  1382.     "struct custom_hash {",
  1383.     "    static uint64_t splitmix64(uint64_t x) {",
  1384.     "        x += 0x9e3779b97f4a7c15;",
  1385.     "        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;",
  1386.     "        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;",
  1387.     "        return x ^ (x >> 31);",
  1388.     "    }",
  1389.     "    size_t operator()(uint64_t x) const {",
  1390.     "        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();",
  1391.     "        return splitmix64(x + FIXED_RANDOM);",
  1392.     "    }",
  1393.     "};"
  1394.   ],
  1395.   "description": "custom_hash "
  1396. }
  1397. "MergeSortTree ": {
  1398.   "prefix": "MergeSortTree ",
  1399.   "body": [
  1400.     "struct MSTN {vector<i32> val;};",
  1401.     "struct MergeSortTree {",
  1402.     "    vector<MSTN> node;",
  1403.     "    i32 uu, vv, n;",
  1404.     "    MergeSortTree(i32 size) : n(size) {",
  1405.     "        node.resize(4 * n + 10);",
  1406.     "        this->uu = 1;",
  1407.     "        this->vv = n;",
  1408.     "    }",
  1409.     "    void relength(i32 size){",
  1410.     "        n = size;",
  1411.     "        node.resize(4 * n + 10);",
  1412.     "        this->uu = 1;",
  1413.     "        this->vv = n;",
  1414.     "    }",
  1415.     "    void merge(MSTN &a, MSTN &b, MSTN &c) {",
  1416.     "        a.val.clear();",
  1417.     "        i32 p1 = 0, p2 = 0;",
  1418.     "        while(true) {",
  1419.     "            if(p1 == b.val.size()) {",
  1420.     "                if(p2 == c.val.size()) break;",
  1421.     "                else a.val.push_back(c.val[p2 ++]);",
  1422.     "            }",
  1423.     "            else {",
  1424.     "                if(p2 == c.val.size()) a.val.push_back(b.val[p1 ++]);",
  1425.     "                else if(b.val[p1] < c.val[p2]) a.val.push_back(b.val[p1 ++]);",
  1426.     "                else a.val.push_back(c.val[p2 ++]);",
  1427.     "            }",
  1428.     "        }",
  1429.     "    }",
  1430.     "    void build(vector<i32> &a) {build(1, 1, n, a);}",
  1431.     "    void build(i32 id, i32 l, i32 r, vector<i32> &a) {",
  1432.     "        if (l == r) {",
  1433.     "            node[id].val.push_back(a[l]);",
  1434.     "            return;",
  1435.     "        }",
  1436.     "        i32 mid = (l + r) >> 1;",
  1437.     "        build(id << 1, l, mid, a);",
  1438.     "        build(id << 1 | 1, mid + 1, r, a);",
  1439.     "        merge(node[id], node[id << 1], node[id << 1 | 1]);",
  1440.     "    }",
  1441.     "    void updateV(i32 pos, i32 x, i32 y) {updateV(pos, x, y, 1, uu, vv);}",
  1442.     "    void updateV(i32 pos, i32 x, i32 y, i32 id, i32 l, i32 r) {",
  1443.     "        if (l > pos || r < pos) return;",
  1444.     "        if (l == r) {",
  1445.     "            i32 ll = 0, rr = node[id].val.size() - 1, res = 0;",
  1446.     "            while(ll <= rr) {",
  1447.     "                i32 mid = (ll + rr) >> 1;",
  1448.     "                if(node[id].val[mid] >= x) rr = (res = mid) - 1;",
  1449.     "                else ll = mid + 1;",
  1450.     "            }",
  1451.     "            if(node[id].val[res] == x) node[id].val[res] = y;",
  1452.     "            else throw std::runtime_error(\"Value not found\");",
  1453.     "            sort(all(node[id].val));",
  1454.     "            return;",
  1455.     "        }",
  1456.     "        i32 mid = (l + r) >> 1;",
  1457.     "        updateV(pos, x, y, id << 1, l, mid);",
  1458.     "        updateV(pos, x, y, id << 1 | 1, mid + 1, r);",
  1459.     "        merge(node[id], node[id << 1], node[id << 1 | 1]);",
  1460.     "    }",
  1461.     "    i32 get(i32 u, i32 v, i32 k) {return get(u, v, k, 1, uu, vv);}",
  1462.     "    i32 get(i32 u, i32 v, i32 k, i32 id, i32 l, i32 r) {",
  1463.     "        if (l > v || r < u) return 0;",
  1464.     "        if (u <= l && r <= v) {",
  1465.     "            i32 ll = 0, rr = node[id].val.size() - 1, res = node[id].val.size();",
  1466.     "            while(ll <= rr) {",
  1467.     "                i32 mid = (ll + rr) >> 1;",
  1468.     "                if(node[id].val[mid] > k) rr = (res = mid) - 1;",
  1469.     "                else ll = mid + 1;",
  1470.     "            }",
  1471.     "            return node[id].val.size() - res;",
  1472.     "        }",
  1473.     "        i32 mid = (l + r) >> 1;",
  1474.     "        return get(u, v, k, id << 1, l, mid) + get(u, v, k, id << 1 | 1, mid + 1, r);",
  1475.     "    }",
  1476.     "};"
  1477.   ],
  1478.   "description": "MergeSortTree "
  1479. }
  1480. "DynamicConnectivity": {
  1481.   "prefix": "DynamicConnectivity",
  1482.   "body": [
  1483.     "struct Connect {",
  1484.     "    i32 v, u;",
  1485.     "    bool united;",
  1486.     "    Connect(i32 _v, i32 _u) : v(_v), u(_u) {",
  1487.     "    }",
  1488.     "};",
  1489.     "struct DynamicConnectivity {",
  1490.     "    vector<vector<Connect>> t;",
  1491.     "    DisjointSets dsu;",
  1492.     "    i32 T;",
  1493.     "",
  1494.     "    DynamicConnectivity() {}",
  1495.     "    DynamicConnectivity(i32 _T, i32 n) : T(_T) {",
  1496.     "        dsu = DisjointSets(n);",
  1497.     "        t.resize(4 * T + 4);",
  1498.     "    }",
  1499.     "",
  1500.     "    void add(i32 v, i32 l, i32 r, i32 ul, i32 ur, Connect& q) {",
  1501.     "        if (ul > ur)",
  1502.     "            return;",
  1503.     "        if (l == ul && r == ur) {",
  1504.     "            t[v].push_back(q);",
  1505.     "            return;",
  1506.     "        }",
  1507.     "        i32 mid = (l + r) >> 1;",
  1508.     "        add(v << 1, l, mid, ul, min(ur, mid), q);",
  1509.     "        add(v << 1 | 1, mid + 1, r, max(ul, mid + 1), ur, q);",
  1510.     "    }",
  1511.     "    void add(Connect q, i32 l, i32 r) {",
  1512.     "        add(1, 0, T - 1, l, r, q);",
  1513.     "    }",
  1514.     "",
  1515.     "    void dfs(i32 v, i32 l, i32 r, vector<i32>& ans) {",
  1516.     "        for (Connect& q : t[v]) {",
  1517.     "            q.united = dsu.merge(q.v, q.u);",
  1518.     "        }",
  1519.     "        if (l == r) ans[l] = dsu.comps;",
  1520.     "        else {",
  1521.     "            i32 mid = (l + r) >> 1;",
  1522.     "            dfs(v << 1, l, mid, ans);",
  1523.     "            dfs(v << 1 | 1, mid + 1, r, ans);",
  1524.     "        }",
  1525.     "        for (Connect q : t[v]) if (q.united) dsu.rollback();",
  1526.     "    }",
  1527.     "    vector<i32> compute() {",
  1528.     "        vector<i32> ans(T);",
  1529.     "        dfs(1, 0, T - 1, ans);",
  1530.     "        return ans;",
  1531.     "    }",
  1532.     "};"
  1533.   ],
  1534.   "description": "DynamicConnectivity"
  1535. }
  1536. 	}
  1537.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
Main.java:1: error: class, interface, or enum expected
{
^
Main.java:1153: error: unclosed string literal
    "            k -= __builtin_clz
    ^
Main.java:1154: error: unclosed string literal
	ll(x);",
	      ^
Main.java:1155: error: class, interface, or enum expected
    "            for(i32 j = i - 1; j >= 0; --j) k = (k << BASE) | (FILTER - __builtin_clzll(seg[j][k]));",
                                                                                                          ^
4 errors
stdout 
Standard output is empty
https://ideone.com/7IG641
language:
Java (HotSpot 12)
created:
227 days 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!