14#include <unordered_set>
20 if(this->
left !=
nullptr && node.
left ==
nullptr) {
23 if(this->
left ==
nullptr && node.
left !=
nullptr) {
26 if(this->
right !=
nullptr && node.
right ==
nullptr) {
29 if(this->
right ==
nullptr && node.
right !=
nullptr) {
32 if(this->
left !=
nullptr && node.
left !=
nullptr && *this->
left != *node.
left) {
38 return this->
val == node.
val;
45 sort(words.begin(), words.end(), [&](
const string &a,
const string &b) { return a.size() < b.size(); });
46 auto ans = vector<string>();
48 for(
const string &word: words) {
49 if(word.length() == 0) {
52 if(node.dfs(&node, word, 0,
false)) {
67 auto *node = this->
nexts[str[0] -
'a'];
70 this->
nexts[str[0] -
'a'] = node;
72 if(str.length() == 1) {
76 return node->insert(str.substr(1));
82 const auto *
const node = this->
nexts[str[start] -
'a'];
86 return node->dfs(root, str, start, flag);
91 if(start == str.length() - 1) {
94 const auto res = root->dfs(root, str, start + 1,
true);
100 if(str[start + 1] -
'a' >= 0) {
101 node = this->
nexts[str[start + 1] -
'a'];
103 return node !=
nullptr && node->
dfs(root, str, start + 1, flag);
110 int length =
static_cast<int>(columnTitle.length());
111 for(
const char c: columnTitle) {
112 sum +=
static_cast<int>(
static_cast<double>(c -
'A' + 1) * pow(26, length-- - 1));
122 while(columnNumber != 0) {
125 ch =
static_cast<char>(columnNumber % 26 + 63);
128 ch =
static_cast<char>(columnNumber % 26 + 64);
130 if(ch ==
'@' && columnNumber >= 26) {
133 }
else if(ch ==
'?' && columnNumber >= 26) {
137 if(
'A' <= ch && ch <=
'Z') {
138 ans.insert(0, 1, ch);
153 if(
m[i] > nums.size() / 2) {
167 for(
int i = 3; i < nums.size(); i++) {
168 for(
int j = 0; j < i - 2; j++) {
172 for(
int k = j + 1; k < i - 1; k++) {
176 for(
int l = k + 1; l < i; l++) {
180 if(nums[k] + nums[j] + nums[l] == nums[i]) {
193 if(hand.size() % groupSize != 0) {
199 sort(hand.begin(), hand.end());
200 const auto len = hand.size() / groupSize;
201 for(
int i = 0; i < len; i++) {
202 int current = *hand.begin();
203 hand.erase(hand.begin());
204 for(
int j = 1; j < groupSize; j++) {
205 auto next = find(hand.begin(), hand.end(), current + 1);
206 if(next == hand.end()) {
221 for(
int i = 1; i < max; i++) {
236 if(root ==
nullptr) {
248 if(node->
left !=
nullptr) {
251 if(node->
right !=
nullptr) {
258 if(node->
left !=
nullptr) {
262 if(node->
right !=
nullptr) {
269 if(sum_node->
right !=
nullptr) {
274 if(sum_node->
left !=
nullptr) {
285 if(original.size() !=
static_cast<unsigned long long>(m) *
static_cast<unsigned long long>(n)) {
288 auto ans = vector<vector<int>>();
290 for(
int i = 0; i < m; i++) {
291 auto row = vector<int>();
292 for(
int j = 0; j < n; j++) {
293 row.push_back(original[count++]);
307 while(num_amount != 1) {
309 if(num_amount % 2 == 1) {
312 }
else if(num_amount % 2 == 0) {
314 const bool left_to_right = loop_cnt % 2 == 0;
332 for(
const char ch: s) {
337 }
else if(ch ==
'b') {
347 if(bank.size() == 1) {
354 while(i < j && i < bank.size() && j < bank.size()) {
360 count += count_i * count_j;
370 for(
const char c: str) {
382 sort(asteroids.begin(), asteroids.end());
383 for(
const int i: asteroids) {
476 const string output[] = {
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday"};
477 const int dayofmonths[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
479 count += (year - 1971) * 365;
480 count += (year - 1) / 4 - 1970 / 4;
481 for(
int m = 0; m < month - 1; m++) {
482 count += dayofmonths[m];
484 if(month > 2 && year % 4 == 0 && year % 100 != 0) {
489 return output[count];
497 memset(
dp, -1,
sizeof dp);
505 if(
dp[mouse][cat][turns] < 0) {
508 }
else if(cat == mouse) {
514 return dp[mouse][cat][turns];
518 const int curMove = turns % 2 == 0 ? mouse : cat;
520 int result = defaultResult;
521 for(
int next:
graph[curMove]) {
522 if(curMove == cat && next == 0) {
525 const int nextMouse = curMove == mouse ? next : mouse;
526 const int nextCat = curMove == cat ? next : cat;
527 const int nextResult =
getResult(nextMouse, nextCat, turns + 1);
528 if(nextResult != defaultResult) {
535 dp[mouse][cat][turns] = result;
541 for(
int i = 0; i < s.size(); i++) {
543 for(
char ch =
'a'; ch <
'z' + 1; ch++) {
544 if(0 <= i - 1 && s[i - 1] == ch) {
547 if(i + 1 < s.size() && s[i + 1] == ch) {
561 auto *
const str_cpy =
new char[path.size() + 1];
562 memcpy(str_cpy, path.c_str(), path.size() + 1);
563 auto *next = strtok(str_cpy,
"/");
564 auto stck = deque<string>();
565 while(next !=
nullptr) {
566 auto nextstr = string(next);
567 if(nextstr ==
"..") {
571 next = strtok(
nullptr,
"/");
575 next = strtok(
nullptr,
"/");
578 stck.emplace_back(next);
579 next = strtok(
nullptr,
"/");
581 auto oss = ostringstream();
585 while(!stck.empty()) {
586 auto pname = stck.front();
600 for(
const char ch: s) {
603 }
else if(ch ==
')') {
616 vector<int> ret(1 << n);
617 for(
int i = 0; i < ret.size(); i++) {
626 const unsigned int n = matrix.size();
627 for(
int i = 0; i < n; i++) {
628 auto *
const row =
new bool[n + 1];
629 memset(row, 1, (n + 1) *
sizeof(
bool));
630 for(
int j = 0; j < n; j++) {
631 if(!row[matrix[i][j]]) {
635 row[matrix[i][j]] =
false;
640 for(
int j = 0; j < n; j++) {
641 auto *
const column =
new bool[n + 1];
642 memset(column, 1, (n + 1) *
sizeof(
bool));
643 for(
int i = 0; i < n; i++) {
644 if(!column[matrix[i][j]]) {
648 column[matrix[i][j]] =
false;
659 for(
const int num: nums) {
669 for(
int i = 0; i < onecount; i++) {
676 for(
int i = 0; i < nums.size(); i++) {
680 if(nums[(onecount + i) % nums.size()] == 0) {
683 if(zerocount < min) {
693 vector<string> &targetWords) {
695 auto start = unordered_set<unsigned int>();
696 for(
const string &word: startWords) {
700 for(
const string &word: targetWords) {
701 const auto bin =
str2bin(word);
702 for(
int i = 0; i < 26; i++) {
703 if((bin & 1 << i) != 0 && start.contains(bin - (1 << i))) {
714 unsigned int ret = 0;
715 for(
const char ch: str) {
716 ret |= 1 << ch -
'a';
724 int max = releaseTimes[0];
726 for(
int i = 1; i < releaseTimes.size(); i++) {
727 const int time = releaseTimes[i] - releaseTimes[i - 1];
731 }
else if(max == time) {
732 if(keysPressed[i] > keysPressed[maxi]) {
737 return keysPressed[maxi];
743 if(num.length() < 3) {
746 auto *
const nums =
new char[num.length()];
747 for(
int i = 0; i < num.length(); i++) {
750 for(
int i = 1; i <= num.length() - i; i++) {
751 const auto n1 =
str2ui(nums, 0, i);
752 for(
int j = i + 1; j - i <= num.length() - j; j++) {
753 const auto n2 =
str2ui(nums, i, j - i);
754 if(
dfs(n1, n2, nums, num.length(), j)) {
769 bool Solution::dfs(
unsigned long long n1,
unsigned long long n2,
const char *nums,
unsigned short length,
unsigned short current) {
770 const auto sum = to_string(n1 + n2);
771 if(sum.length() > length - current) {
775 if(!
equal(sum, nums, current, length)) {
779 if(current + sum.length() == length) {
783 const auto n3 =
str2ui(nums, current, sum.length());
784 return dfs(n2, n3, nums, length, current + sum.length());
787 unsigned long long Solution::str2ui(
const char *str,
unsigned short start,
unsigned short length) {
788 unsigned long long ans = 0;
789 for(
int i = start; i < start + length; i++) {
796 bool Solution::equal(
string sum,
const char *nums,
unsigned short start,
unsigned short length) {
798 for(
int i = start; j < sum.length() && i < length; i++, j++) {
799 if(sum[j] != nums[i]) {
803 return j == sum.length();
809 if(encodedText.empty()) {
812 const int columns = encodedText.length() / rows;
813 auto *
const table =
new char *[rows];
814 for(
int i = 0; i < rows; i++) {
815 table[i] =
new char[columns - rows + 2];
816 for(
int j = i; j - i < columns - rows + 2; j++) {
817 if(i * columns + j < encodedText.length()) {
818 table[i][j - i] = encodedText[i * columns + j];
820 table[i][j - i] =
' ';
824 auto oss = ostringstream();
825 for(
int j = 0; j < columns - rows + 2; j++) {
826 for(
int i = 0; i < rows; i++) {
830 string ans = oss.str();
831 for(
int i = 0; i < rows; i++) {
839 for(
int i = s.length() - 1; i >= 0; i--) {
841 string ans = s.substr(0, i + 1);
851 const int limit = blocked.size() * (blocked.size() - 1) / 2;
852 if(blocked.empty()) {
855 auto *p_source =
new point(source[0], source[1], 0,
nullptr);
856 auto *p_target =
new point(target[0], target[1], 0,
nullptr);
857 auto blocked_set_source = unordered_set<point, point_hash>();
858 auto blocked_set_target = unordered_set<point, point_hash>();
859 for(
auto block: blocked) {
860 blocked_set_source.insert(
point(block[0], block[1], 0,
nullptr));
861 blocked_set_target.insert(
point(block[0], block[1], 0,
nullptr));
863 const unsigned int source_status =
search(blocked_set_source, p_source, p_target, limit);
864 if(source_status == 0) {
867 if(source_status == 1) {
870 const unsigned int target_status =
search(blocked_set_target, p_target, p_source, limit);
873 return target_status != 0;
877 auto pq = priority_queue<point>();
878 pq.push(
point(source->
x, source->
y, 0, target));
881 if(count > limit || pq.size() > limit) {
885 const auto p = pq.top();
887 point nexts[] = {
point(p.x + 1, p.y, p.distance + 1, target),
point(p.x - 1, p.y, p.distance + 1, target),
point(p.x, p.y + 1, p.distance + 1, target),
point(p.x, p.y - 1, p.distance + 1, target)};
888 for(
auto next: nexts) {
889 if(0 <= next.x && next.x < 1000000 && 0 <= next.y && next.y < 1000000 && !block_set.contains(next)) {
890 if(next.x == target->
x && next.y == target->
y) {
894 block_set.insert(next);
909 if(nums.size() < 3) {
912 auto *min =
new int[nums.size()];
913 auto *max =
new int[nums.size()];
915 max[nums.size() - 1] = nums[nums.size() - 1];
916 for(
int i = 1, j = nums.size() - 2; i < nums.size() && j >= 0; i++, j--) {
917 if(min[i - 1] > nums[i]) {
923 if(max[j + 1] < nums[j]) {
929 for(
int i = 0; i < nums.size(); i++) {
930 if(nums[i] > min[i] && nums[i] < max[i]) {
944 if(nums.size() < 2) {
950 if(nums[0] < nums[1]) {
959 for(
int i = 2; i < nums.size(); i++) {
964 }
else if(nums[i] > second) {
968 if(max >= 2 * second) {
977 auto ans = vector<vector<int>>();
978 auto pq = priority_queue<pair>();
979 for(
int i = 0; i < k && i < nums1.size(); i++) {
980 for(
int j = 0; j < k && j < nums2.size(); j++) {
981 pq.push(
pair(nums1[i], nums2[j]));
984 for(
int i = 0; i < k && i < nums1.size() * nums2.size(); i++) {
985 const pair p = pq.top();
987 auto to_add = vector<int>();
991 ans.push_back(to_add);
1001 auto ans = vector<vector<int>>();
1002 if(nums.size() == 1) {
1003 auto next_ans = vector<int>();
1004 next_ans.push_back(nums[0]);
1005 ans.push_back(next_ans);
1008 for(
auto num: nums) {
1009 auto next = vector(nums);
1010 next.erase(find(next.begin(), next.end(), num));
1011 auto next_permutations =
permute(next);
1012 auto new_ans = vector<int>();
1013 new_ans.push_back(num);
1014 for(
auto next_permutation: next_permutations) {
1015 auto next_ans = vector(new_ans);
1016 next_ans.insert(next_ans.end(), next_permutation.begin(), next_permutation.end());
1017 ans.push_back(next_ans);
1026 int sum = n / 7 * (28 + 7 * (n / 7 + 3)) / 2;
1027 for(
int i = 0; i < n % 7; i++) {
1028 sum += n / 7 + 1 + i;
1038 for(
const auto *node =
head; node !=
nullptr; node = node->next, i++) {
1039 if(rand() % i == 0) {
1050 auto ans = vector<string>();
1052 for(; i * k + k < s.length(); i++) {
1053 ans.push_back(s.substr(i * k, k));
1055 if(i * k != s.length()) {
1056 string last = s.substr(i * k);
1057 for(
int j = last.length(); j < k; j++) {
1060 ans.push_back(last);
1069 while(target != 1) {
1070 if(maxDoubles == 0) {
1071 return count + target - 1;
1073 if(target % 2 == 0 && maxDoubles != 0) {
1087 vector<long long> f(questions.size() + 1);
1088 for(
int i = questions.size() - 1; i >= 0; --i) {
1089 auto &q = questions[i];
1090 const int j = i + q[1] + 1;
1091 f[i] = max(f[i + 1], q[0] + (j < questions.size() ? f[j] : 0));
1099 auto check = [&](
long long t) {
1101 for(
const int i: batteries) {
1102 sum += min(t,
static_cast<long long>(i));
1104 return sum / t >= n;
1110 const long long m = (l + r) / 2;
1124 unsigned long long end[5] = {1, 1, 1, 1, 1};
1125 for(
int _i = 1; _i < n; _i++) {
1126 const unsigned long long a = (end[1] + end[2] + end[4]) % 1000000007;
1127 const unsigned long long e = (end[0] + end[2]) % 1000000007;
1128 const unsigned long long i = (end[1] + end[3]) % 1000000007;
1129 const unsigned long long o = end[2] % 1000000007;
1130 const unsigned long long u = (end[2] + end[3]) % 1000000007;
1137 return (end[0] + end[1] + end[2] + end[3] + end[4]) % 1000000007;
1143 auto vec = vector<int>();
1144 for(
string timePoint: timePoints) {
1145 vec.push_back(((timePoint[0] -
'0') * 10 + (timePoint[1] -
'0')) * 60 + (timePoint[3] -
'0') * 10 + (timePoint[4] -
'0'));
1147 sort(vec.begin(), vec.end());
1148 int minimum = INT_MAX;
1149 for(
int i = 0; i + 1 < vec.size(); i++) {
1150 minimum = min(minimum, vec[i + 1] - vec[i]);
1152 minimum = min(minimum, vec[0] + 24 * 60 - vec[vec.size() - 1]);
1159 auto um = unordered_map<int, vector<int>>();
1160 for(
int i = 0; i < nums.size(); i++) {
1161 if(!um.contains(nums[i])) {
1162 um.insert(pair(nums[i], vector<int>()));
1164 auto pos = lower_bound(um[nums[i]].begin(), um[nums[i]].end(), i);
1165 if(pos != um[nums[i]].end() && abs(*pos - i) <= k || pos != um[nums[i]].begin() && abs(*(pos - 1) - i) <= k) {
1168 um[nums[i]].insert(pos, i);
1171 sort(i.second.begin(), i.second.end());
1179 unsigned int remove = 0;
1180 unsigned int counts[3] = {0, 0, 0};
1181 for(
auto stone: stones) {
1185 if(stones.size() == 1) {
1188 if(counts[1] + counts[2] == 2) {
1189 if(counts[1] == 2 || counts[2] == 2) {
1193 if(counts[1] == 0 && counts[2] == 0) {
1196 if(abs(
static_cast<int>(counts[1]) -
static_cast<int>(counts[2])) <= 2) {
1197 return counts[0] % 2 == 0;
1205 if(arr.size() == 1) {
1208 auto pq = queue<pair<int, int>>();
1209 auto *flag =
new bool[arr.size()];
1210 memset(flag, 0, arr.size() *
sizeof(
bool));
1211 auto um = unordered_map<int, vector<int>>();
1212 for(
int i = 0; i < arr.size(); i++) {
1213 if(!um.contains(arr[i])) {
1214 auto vec = vector<int>();
1216 um.insert(pair(arr[i], vec));
1218 um[arr[i]].push_back(i);
1221 pq.push(pair(0, 0));
1223 while(!pq.empty()) {
1224 auto [current_i, current_count] = pq.front();
1226 if(current_i == arr.size() - 1) {
1227 return current_count;
1229 if(um.contains(arr[current_i])) {
1230 for(
auto i: um[arr[current_i]]) {
1231 if(i != current_i && !flag[i]) {
1232 pq.push(pair(i, current_count + 1));
1237 um.erase(arr[current_i]);
1238 if(current_i - 1 >= 0 && !flag[current_i - 1]) {
1239 pq.push(pair(current_i - 1, current_count + 1));
1240 flag[current_i - 1] =
true;
1242 if(current_i + 1 < arr.size() && !flag[current_i + 1]) {
1243 pq.push(pair(current_i + 1, current_count + 1));
1244 flag[current_i + 1] =
true;
1254 for(
int i = 0, j = s.length() - 1; i < j; i++, j--) {
1265 auto oss = ostringstream();
1266 auto *
const nstr =
new char[sentence.length() + 1];
1268 for(
const auto &root: dictionary) {
1271 strcpy(nstr, sentence.c_str());
1272 char *word = strtok(nstr,
" ");
1273 while(word !=
nullptr) {
1274 oss << tn.get_prefix(
"",
string(word)) <<
" ";
1275 word = strtok(
nullptr,
" ");
1277 const string ans = oss.str();
1279 return ans.substr(0, ans.length() - 1);
1287 if(this->
next[str[0] -
'a'] ==
nullptr) {
1290 this->
next[str[0] -
'a']->insert(str.substr(1));
1294 if(this->
endroot || str.empty()) {
1297 if(this->
next[str[0] -
'a'] ==
nullptr) {
1300 return this->
next[str[0] -
'a']->get_prefix(root + str[0], str.substr(1));
1306 if(cost.size() == 1) {
1309 if(cost.size() == 2) {
1310 return cost[0] + cost[1];
1313 sort(cost.rbegin(), cost.rend());
1314 for(
int i = 0; i < cost.size(); i++) {
1325 long long current = 0;
1326 long long maximum = 0;
1327 long long minimum = 0;
1328 for(
const auto difference: differences) {
1329 current += difference;
1330 maximum = max(maximum, current);
1331 minimum = min(minimum, current);
1333 return max(
static_cast<long long>(0), upper - lower - (maximum - minimum) + 1);
1339 const auto m = grid.size();
1340 const auto n = grid[0].size();
1341 auto ans = vector<vector<int>>();
1342 const auto low = pricing[0];
1343 const auto high = pricing[1];
1344 const auto row = start[0];
1345 const auto col = start[1];
1346 auto pq = priority_queue<item>();
1347 pq.push(
item(0, grid[row][col], row, col));
1349 while(pq.empty() && k != 0) {
1350 auto current = pq.top();
1352 if(current.price != 1 && current.price >= low && current.price <= high) {
1354 auto vec = vector<int>();
1355 vec.push_back(current.row);
1356 vec.push_back(current.col);
1359 pair<int, int> nexts[4] = {pair(current.row + 1, current.col),
1360 pair(current.row - 1, current.col),
1361 pair(current.row, current.col + 1),
1362 pair(current.row, current.col - 1)};
1363 for(
const pair<int, int> next: nexts) {
1364 if(0 <= next.first && next.first < m && 0 <= next.second && next.second < n && grid[next.first][next.second] != 0) {
1365 pq.push(
item(current.distance + 1, grid[next.first][next.second], next.first, next.second));
1366 grid[next.first][next.second] = 0;
1381 return this->
row > i.
row;
1383 return this->
col > i.
col;
1389 unsigned int s_count = 0;
1390 auto p = vector<unsigned int>();
1391 for(
const char ch: corridor) {
1396 if(s_count == 0 || s_count % 2 != 0) {
1402 unsigned int start = 0;
1403 unsigned int end = corridor.length() - 1;
1404 for(; start < end; start++) {
1405 if(corridor[start] ==
'S') {
1409 for(; end > start; end--) {
1410 if(corridor[end] ==
'S') {
1415 unsigned int p_count = 0;
1417 for(
unsigned int i = start + 1; i <= end; i++) {
1418 if(corridor[i] ==
'S') {
1428 }
else if(s_count == 1) {
1430 p.push_back(p_count + 1);
1436 unsigned long long ans = 1;
1437 for(
const auto i: p) {
1447 int maximum = nums[0];
1448 int minimum = nums[0];
1449 for(
auto num: nums) {
1450 maximum = max(maximum, num);
1451 minimum = min(minimum, num);
1453 unsigned int count = 0;
1454 for(
const auto num: nums) {
1455 if(maximum != num && minimum != num) {
1465 const auto size = nums.size();
1466 auto ans = vector<int>();
1467 auto positive = vector<int>();
1468 auto negative = vector<int>();
1469 for(
auto num: nums) {
1471 positive.push_back(num);
1473 negative.push_back(num);
1476 for(
int i = 0; i < size / 2; i++) {
1477 ans.push_back(positive[i]);
1478 ans.push_back(negative[i]);
1486 if(nums.size() == 1) {
1489 sort(nums.begin(), nums.end());
1490 auto ans = vector<int>();
1491 if(nums[1] - nums[0] > 1) {
1492 ans.push_back(nums[0]);
1494 if(nums[nums.size() - 1] - nums[nums.size() - 2] > 1) {
1495 ans.push_back(nums[nums.size() - 1]);
1497 for(
int i = 1; i < nums.size() - 1; i++) {
1498 if(nums[i] - nums[i - 1] > 1 && nums[i + 1] - nums[i] > 1) {
1499 ans.push_back(nums[i]);
1509 auto dup = unordered_map<int, bool>();
1510 for(
int i = 0; i < statements.size(); i++) {
1514 const auto um = unordered_map<int, bool>();
1515 auto que = queue<msg>();
1516 que.push(
msg(i,
true));
1517 auto ans =
dfs(statements, um, que);
1518 maximum = max(maximum, ans.first);
1519 for(
auto it: ans.second) {
1528 pair<int, unordered_map<int, bool>>
Solution::dfs(vector<vector<int>> &statements, unordered_map<int, bool> um, queue<msg> que) {
1530 bool contradict =
false;
1531 while(!que.empty()) {
1532 auto current = que.front();
1534 if(um.contains(current.person)) {
1536 if(um[current.person] != current.good) {
1538 return pair<int, unordered_map<int, bool>>(0, {});
1541 um.insert(pair(current.person, current.good));
1545 for(
int j = 0; j < statements.size(); j++) {
1546 if(statements[current.person][j] != 2 && j != current.person) {
1547 auto nmsg =
msg(j, statements[current.person][j] == 1);
1548 if(um.contains(nmsg.person)) {
1550 if(um[nmsg.person] != nmsg.good) {
1553 return pair<int, unordered_map<int, bool>>(0, {});
1565 auto dup = unordered_map<int, bool>();
1566 for(
int i = 0; i < statements.size(); i++) {
1570 if(!um.contains(i)) {
1572 for(
auto v: statements[i]) {
1578 um.insert(pair(i,
true));
1581 auto nque = queue<msg>();
1582 nque.push(
msg(i,
true));
1583 auto ans =
dfs(statements, um, nque);
1584 maximum = max(maximum, ans.first);
1585 for(
auto it: ans.second) {
1599 maximum = max(maximum, good_count);
1601 return pair(maximum, um);
1607 ms = multiset<int>();
1608 m = map<int, int>();
1612 if(!
m.contains(timestamp)) {
1613 m.insert(pair(timestamp, price));
1615 ms.erase(
ms.find(
m[timestamp]));
1616 m[timestamp] = price;
1630 auto record = unordered_map<int, vector<int>>();
1631 for(
int i = 1; i <= n; i++) {
1632 record.insert(pair(i, vector<int>()));
1634 auto um = unordered_map<int, unordered_set<int>>();
1635 for(
auto edge: edges) {
1636 if(!um.contains(edge[0])) {
1637 auto us = unordered_set<int>();
1639 um.insert(pair(edge[0], us));
1641 um[edge[0]].insert(edge[1]);
1643 if(!um.contains(edge[1])) {
1644 auto us = unordered_set<int>();
1646 um.insert(pair(edge[1], us));
1648 um[edge[1]].insert(edge[0]);
1651 auto pq = priority_queue<status>();
1655 while(!pq.empty()) {
1656 status current = pq.top();
1661 prev = current.
time;
1663 if(current.
time != prev) {
1664 return current.
time;
1676 for(
int next: um[current.
position]) {
1678 if(current.
time / change % 2 == 1) {
1680 next_time = (current.
time / change + 1) * change + time;
1682 next_time = current.
time + time;
1684 auto next_status =
status(next, next_time);
1685 if(record[next_status.position].empty() || record[next_status.position].size() == 1 && next_status.time != *record[next_status.position].rbegin()) {
1687 pq.push(next_status);
1709 if(p.first != point[0] && p.second != point[1] && abs(p.first - point[0]) == abs(p.second - point[1])) {
1710 count +=
ms.count(pair(p.first, point[1])) *
ms.count(pair(point[0], p.second));
1719 auto *str =
new char[sentence.length() + 1];
1720 strcpy(str, sentence.c_str());
1722 for(
const char *token = strtok(str,
" "); token !=
nullptr; token = strtok(
nullptr,
" ")) {
1723 bool is_valid =
true;
1724 bool hyphen =
false;
1725 for(
int i = 0; token[i] !=
'\0'; i++) {
1726 const char ch = token[i];
1735 if(i == 0 || token[i + 1] ==
'\0') {
1740 if(isalpha(token[i - 1]) == 0 || isalpha(token[i + 1]) == 0) {
1745 }
else if(token[i + 1] !=
'\0' && isalpha(ch) == 0) {
1749 }
else if(isdigit(ch) != 0) {
1767 sort(properties.begin(), properties.end(), [](
const vector<int> &a,
const vector<int> &b) { return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0]; });
1771 for(
const auto &p: properties) {
1786 for(
const char ch: pattern) {
1793 if(a_count == 0 || b_count == 0) {
1797 if(value.length() % a_count != 0) {
1800 size = value.length() / a_count;
1803 if(value.length() % b_count != 0) {
1806 size = value.length() / b_count;
1809 const string str = value.substr(0, size);
1810 for(
int i = 0; i < count; i++) {
1811 auto s = value.substr(i * size, size);
1818 for(
int a_size = 0; a_size <= value.length() / a_count; a_size++) {
1821 if((value.length() - a_size * a_count) % b_count == 0) {
1822 const int b_size = (value.length() - a_size * a_count) / b_count;
1823 string value_local = value;
1824 for(
const char ch: pattern) {
1826 string a_local = value_local.substr(0, a_size);
1829 }
else if(a_local != a) {
1832 value_local = value_local.substr(a_size);
1834 string b_local = value_local.substr(0, b_size);
1837 }
else if(b_local != b) {
1840 value_local = value_local.substr(b_size);
1856 const int m = isWater.size();
1857 const int n = isWater[0].size();
1858 auto *occupied =
new bool *[m];
1859 for(
int i = 0; i < m; i++) {
1860 occupied[i] =
new bool[n];
1861 memset(occupied[i], 0, n *
sizeof(
bool));
1863 auto que = queue<pair<int, int>>();
1864 for(
int i = 0; i < m; i++) {
1865 for(
int j = 0; j < n; j++) {
1866 if(isWater[i][j] == 1) {
1867 que.push(pair(i, j));
1869 occupied[i][j] =
true;
1875 while(!que.empty()) {
1876 pair<int, int> current = que.front();
1878 pair<int, int> nexts[4] = {pair(current.first + 1, current.second),
1879 pair(current.first - 1, current.second),
1880 pair(current.first, current.second + 1),
1881 pair(current.first, current.second - 1)};
1882 for(
auto next: nexts) {
1883 if(0 <= next.first && next.first < m && 0 <= next.second && next.second < n && !occupied[next.first][next.second]) {
1884 isWater[next.first][next.second] = isWater[current.first][current.second] + 1;
1885 occupied[next.first][next.second] =
true;
1897 auto ans = vector<string>();
1898 auto um = unordered_map<string, unsigned int>();
1899 auto *
const s1_str =
new char[s1.length() + 1];
1900 auto *
const s2_str =
new char[s2.length() + 1];
1901 strcpy(s1_str, s1.c_str());
1902 strcpy(s2_str, s2.c_str());
1903 for(
char *word = strtok(s1_str,
" "); word !=
nullptr; word = strtok(
nullptr,
" ")) {
1904 auto word_str = string(word);
1905 if(!um.contains(word_str)) {
1906 um.insert(pair(word_str, 1));
1911 for(
char *word = strtok(s2_str,
" "); word !=
nullptr; word = strtok(
nullptr,
" ")) {
1912 auto word_str = string(word);
1913 if(!um.contains(word_str)) {
1914 um.insert(pair(word_str, 1));
1919 for(
const auto &p: um) {
1921 ans.push_back(p.first);
1933 for(
const auto num: nums) {
1934 if(num == original) {
1945 const auto n = nums.size();
1946 auto left_0_count = vector<int>();
1947 auto right_1_count = vector<int>();
1948 left_0_count.push_back(0);
1949 right_1_count.push_back(0);
1951 for(
int i = 0; i < n; i++) {
1955 left_0_count.push_back(count);
1958 for(
int i = n - 1; i >= 0; i--) {
1962 right_1_count.push_back(count);
1964 right_1_count = vector(right_1_count.rbegin(), right_1_count.rend());
1966 for(
int i = 0; i <= n; i++) {
1967 maximum = max(maximum, left_0_count[i] + right_1_count[i]);
1969 auto ans = vector<int>();
1970 for(
int i = 0; i <= n; i++) {
1971 if(maximum == left_0_count[i] + right_1_count[i]) {
1982 auto *
const pn =
new int[k];
1984 for(
int i = 1; i < k; i++) {
1985 pn[i] =
static_cast<unsigned long long>(pn[i - 1]) *
static_cast<unsigned long long>(power) % modulo;
1988 for(
int i = 0; i < s.length(); i++) {
1989 unsigned long long hash = 0;
1990 for(
int j = 0; j < k; j++) {
1991 hash +=
static_cast<unsigned long long>((s[i + j] -
'a' + 1) % modulo) * pn[j];
1994 if(hash == hashValue) {
1995 return s.substr(i, k);
2005 auto ans = vector<int>();
2006 auto nums = vector<unsigned int>();
2007 for(
const auto &word: words) {
2009 nums.push_back(num);
2012 for(
const auto num: nums) {
2013 for(
int i = 0; i < 26; i++) {
2014 auto next = num ^ 1 << i;
2015 if(
parent.contains(next)) {
2018 if((num >> i & 1) == 1) {
2020 for(
int j = 0; j < 26; j++) {
2021 if((num >> j & 1) == 0) {
2023 auto next = num ^ 1 << i | 1 << j;
2024 if(
parent.contains(next)) {
2025 to_union(num, num ^ 1 << i | 1 << j);
2038 unsigned int ans = 0;
2039 for(
const char ch: word) {
2040 ans |= 1 << ch -
'a';
2046 parent.insert(pair(num, num));
2047 rank.insert(pair(num, 0));
2048 if(!
size.contains(num)) {
2049 size.insert(pair(num, 1));
2060 const int f1 =
find(x1);
2061 const int f2 =
find(x2);
2088 if((num & 1) == 0) {
2101 auto [max_start, max_len] =
dfs(s, 0, s.length() - 1);
2105 return s.substr(max_start, max_len);
2116 for(
int i = start; i <= end; i++) {
2117 const char ch = s[i];
2118 if(islower(ch) != 0) {
2119 lower |= 1 << ch -
'a';
2122 upper |= 1 << ch -
'A';
2125 if(lower == upper) {
2127 return {start, end - start + 1};
2130 const int not_nice = lower ^ upper;
2133 if((not_nice >> tolower(s[i]) -
'a' & 1) == 1) {
2139 while(j <= end && (not_nice >> tolower(s[j]) -
'a' & 1) != 1) {
2142 auto [next_start, next_len] =
dfs(s, i, j - 1);
2143 if(max_len < next_len) {
2145 max_start = next_start;
2149 return {max_start, max_len};
2156 for(; i < word.length(); i++) {
2161 if(i == word.length()) {
2164 string prefix = word.substr(0, i + 1);
2165 const string suffix = word.substr(i + 1);
2166 const auto xiferp = string(prefix.rbegin(), prefix.rend());
2167 return xiferp + suffix;
2173 auto fibb = set<int, greater<>>();
2179 const int prev_2 = prev_1;
2181 next = prev_1 + prev_2;
2183 return find_min(fibb, k, fibb.begin());
2187 const auto i = lower_bound(begin, fibb.end(), k, greater<int>());
2191 return 1 +
find_min(fibb, k - *i, i);
2197 auto m = map<int, int>();
2198 for(
auto rectangle: rectangles) {
2199 int k = min(rectangle[0], rectangle[1]);
2202 return (*m.rbegin()).second;
2208 const int m = grid.size();
2209 const int n = grid[0].size();
2211 for(
int i = 0; i < m; i++) {
2212 for(
int j = 0; j < n; j++) {
2213 if(grid[i][j] != 0) {
2214 auto *occupied =
new bool *[m];
2215 for(
int k = 0; k < m; k++) {
2216 occupied[k] =
new bool[n];
2217 memset(occupied[k], 0, n *
sizeof(
bool));
2219 occupied[i][j] =
true;
2220 ans = max(ans,
get_sum(grid[i][j], i, j, m, n, grid, occupied));
2221 for(
int k = 0; k < m; k++) {
2222 delete[] occupied[k];
2231 int Solution::get_sum(
int current,
int x,
int y,
int m,
int n, vector<vector<int>> &grid,
bool **occupied) {
2232 pair<int, int> nexts[] = {make_pair(x + 1, y), make_pair(x - 1, y), make_pair(x, y + 1), make_pair(x, y - 1)};
2233 int maximum = current;
2234 for(
auto [next_x, next_y]: nexts) {
2235 if(0 <= next_x && next_x < m && 0 <= next_y && next_y < n && grid[next_x][next_y] != 0 && !occupied[next_x][next_y]) {
2236 auto *occupied_cpy =
new bool *[m];
2237 for(
int i = 0; i < m; i++) {
2238 occupied_cpy[i] =
new bool[n];
2239 memcpy(occupied_cpy[i], occupied[i], n *
sizeof(
bool));
2241 occupied_cpy[next_x][next_y] =
true;
2242 maximum = max(maximum,
get_sum(current + grid[next_x][next_y], next_x, next_y, m, n, grid, occupied_cpy));
2243 for(
int i = 0; i < m; i++) {
2244 delete[] occupied_cpy[i];
2246 delete[] occupied_cpy;
2255 auto oss = ostringstream();
2257 const string str = oss.str();
2259 for(
int i = 0; i < 4; i++) {
2260 nums[i] = str[i] -
'0';
2262 sort(nums, nums + 4);
2263 return nums[0] * 10 + nums[1] * 10 + nums[2] + nums[3];
2269 auto less = vector<int>();
2270 auto equal = vector<int>();
2271 auto greater = vector<int>();
2272 for(
auto num: nums) {
2274 less.push_back(num);
2275 }
else if(num == pivot) {
2276 equal.push_back(num);
2278 greater.push_back(num);
2281 less.insert(less.end(), equal.begin(), equal.end());
2282 less.insert(less.end(), greater.begin(), greater.end());
2289 int ans = (moveCost + pushCost) * 4;
2290 int minute = targetSeconds / 60;
2291 int second = targetSeconds % 60;
2292 while(minute > 99) {
2296 const int num[4] = {minute / 10, minute % 10, second / 10, second % 10};
2297 ans = min(ans,
get_cost(startAt, moveCost, pushCost, num));
2298 if(second + 60 < 100 && minute - 1 >= 0) {
2301 const int num[4] = {minute / 10, minute % 10, second / 10, second % 10};
2302 ans = min(ans,
get_cost(startAt, moveCost, pushCost, num));
2309 int current = startAt;
2311 for(
int i = 0; i < 4; i++) {
2312 if(num[i] == 0 && flag) {
2316 if(num[i] != current) {
2328 const int n = nums.size() / 3;
2329 auto *left_sum =
new long long[n];
2330 auto *right_sum =
new long long[n];
2331 long long left_min = 0;
2332 long long right_max = 0;
2333 auto left_n = priority_queue<int>();
2334 auto right_n = priority_queue<int, vector<int>, greater<>>();
2335 for(
int i = 0; i < n; i++) {
2336 left_n.push(nums[i]);
2337 left_min += nums[i];
2339 for(
int i = 3 * n - 1; i >= 2 * n; i--) {
2340 right_n.push(nums[i]);
2341 right_max += nums[i];
2343 const long long left_min_preserve = left_min;
2344 const long long right_max_preserve = right_max;
2345 left_sum[0] = left_min;
2346 right_sum[n - 1] = right_max;
2347 for(
int i = n; i < 2 * n; i++) {
2348 if(nums[i] < left_n.top()) {
2349 left_min += nums[i] - left_n.top();
2351 left_n.push(nums[i]);
2353 left_sum[i - n] = left_min;
2355 for(
int i = 2 * n - 1; i >= n; i--) {
2356 if(nums[i] > right_n.top()) {
2357 right_max += nums[i] - right_n.top();
2359 right_n.push(nums[i]);
2361 right_sum[i - n] = right_max;
2363 long long ans = left_min_preserve - right_sum[0];
2364 for(
int i = 0; i < n - 1; i++) {
2365 ans = min(ans, left_sum[i] - right_sum[i + 1]);
2367 ans = min(ans, left_sum[n - 1] - right_max_preserve);
2376 auto um = unordered_map<int, int>();
2377 for(
auto num: nums) {
2381 for(
auto [k, v]: um) {
2395 for(
int i = 0; i < nums.size(); i++) {
2397 even.push_back(nums[i]);
2399 odd.push_back(nums[i]);
2402 sort(even.begin(), even.end());
2403 sort(odd.begin(), odd.end(), greater<int>());
2404 for(
int i = 0; i < odd.size(); i++) {
2405 ans.push_back(even[i]);
2406 ans.push_back(odd[i]);
2408 if(even.size() > odd.size()) {
2409 ans.push_back(even.back());
2417 bool positive = num > 0;
2418 auto oss = ostringstream();
2422 for(
char ch: oss.str()) {
2423 n.push_back(ch -
'0');
2425 sort(n.begin(), n.end());
2435 ans.insert(ans.begin() + 1, i);
2439 for(
int i = n.size() - 1; i >= 0; i--) {
2440 ans.push_back(n[i]);
2443 oss = ostringstream();
2450 auto iss = istringstream(oss.str());
2460 one1 =
new set<unsigned int>();
2461 zero0 =
new set<unsigned int>();
2462 for(
int i = 0; i <
size; i++) {
2478 auto *
const tmp =
one1;
2490 auto oss = ostringstream();
2491 auto c1 =
one1->begin();
2492 auto c0 =
zero0->begin();
2493 for(
int i = 0; i <
size; i++) {
2494 if(c1 !=
one1->end() && *c1 == i) {
2497 }
else if(c0 !=
zero0->end() && *c0 == i) {
2508 auto oss = ostringstream();
2513 while(a != 0 || b != 0 || c != 0) {
2514 if(!(count == 2 && prev == ch[2] && *
get_p(ch[2], &a, &b, &c) > 0)) {
2516 (*
get_p(ch[2], &a, &b, &c))--;
2523 }
else if(!(count == 2 && prev == ch[1]) && *
get_p(ch[1], &a, &b, &c) > 0) {
2525 (*
get_p(ch[1], &a, &b, &c))--;
2532 }
else if(!(count == 2 && prev == ch[0]) && *
get_p(ch[0], &a, &b, &c) > 0) {
2534 (*
get_p(ch[0], &a, &b, &c))--;
2570 ch[1] =
'a' +
'b' +
'c' - ch[0] - ch[2];
2578 default:
return nullptr;
2585 auto ls = unordered_set<pair<int, int>,
pair_hash>();
2586 auto row = unordered_map<int, int>();
2587 auto col = unordered_map<int, int>();
2588 auto diag_down = unordered_map<int, int>();
2589 auto diag_up = unordered_map<int, int>();
2590 for(
auto lamp: lamps) {
2593 auto p = make_pair(x, y);
2594 if(!ls.contains(p)) {
2598 diag_down[n - x + y]++;
2602 auto ans = vector<int>();
2603 for(
auto query: queries) {
2604 int query_x = query[0];
2605 int query_y = query[1];
2606 if(row[query_x] > 0 || col[query_y] > 0 || diag_down[n - query_x + query_y] > 0 || diag_up[query_x + query_y] > 0) {
2611 pair<int, int> adjacents[9] = {make_pair(query_x + 1, query_y + 1), make_pair(query_x + 1, query_y), make_pair(query_x + 1, query_y - 1),
2612 make_pair(query_x, query_y + 1), make_pair(query_x, query_y), make_pair(query_x, query_y - 1),
2613 make_pair(query_x - 1, query_y + 1), make_pair(query_x - 1, query_y), make_pair(query_x - 1, query_y - 1)};
2614 for(
auto adjacent: adjacents) {
2615 if(ls.contains(adjacent)) {
2617 auto [x, y] = adjacent;
2620 diag_down[n - x + y]--;
2628 unsigned long long pair_hash::operator()(
const pair<int, int> &p)
const {
return static_cast<unsigned long long>(p.first) * 1000000000 + p.second; }
2634 for(
int i = 0; i < nums.size(); i++) {
2635 for(
int j = i + 1; j < nums.size(); j++) {
2636 if(abs(nums[i] - nums[j]) == k) {
2647 auto ans = vector<string>();
2648 for(
int denominator = 2; denominator <= n; denominator++) {
2649 for(
int numerator = 1; numerator < denominator; numerator++) {
2650 if(
gcd(denominator, numerator) != 1) {
2653 auto oss = ostringstream();
2654 oss << numerator <<
"/" << denominator;
2655 ans.push_back(oss.str());
2667 sort(nums.begin(), nums.end());
2668 for(
int i = 0; i + k - 1 < nums.size(); i++) {
2669 ans = min(ans, nums[i + k - 1] - nums[i]);
2678 const int m = grid.size();
2679 const int n = grid[0].size();
2680 auto que = queue<pair<int, int>>();
2681 for(
int i = 0; i < m; i++) {
2682 for(
int j = 0; j < n; j++) {
2683 if(grid[i][j] == 1) {
2685 if(i == 0 || i == m - 1 || j == 0 || j == n - 1) {
2686 que.push(make_pair(i, j));
2692 while(!que.empty()) {
2693 auto [x, y] = que.front();
2696 pair<int, int> nexts[4] = {make_pair(x + 1, y), make_pair(x - 1, y), make_pair(x, y + 1), make_pair(x, y - 1)};
2697 for(
auto next: nexts) {
2698 auto [next_x, next_y] = next;
2699 if(0 <= next_x && next_x < m && 0 <= next_y && next_y < n && grid[next_x][next_y] != 0) {
2701 grid[next_x][next_y] = 0;
2716 for(
const char ch: text) {
2748 auto oss_start = ostringstream();
2749 auto oss_end = ostringstream();
2750 auto i_start = vector<int>();
2751 auto i_end = vector<int>();
2752 for(
int i = 0; i < start.size(); i++) {
2754 if(ch ==
'R' || ch ==
'L') {
2756 i_start.push_back(i);
2759 for(
int i = 0; i < end.size(); i++) {
2761 if(ch ==
'R' || ch ==
'L') {
2766 string str_start = oss_start.str();
2767 string str_end = oss_end.str();
2768 if(str_start != str_end) {
2771 for(
int i = 0; i < i_start.size(); i++) {
2772 if(str_start[i] ==
'R') {
2773 if(i_start[i] > i_end[i]) {
2778 if(i_start[i] < i_end[i]) {
2790 while(num1 != 0 && num2 != 0) {
2792 count += num1 / num2;
2795 count += num2 / num1;
2807 auto a = unordered_map<int, int>();
2808 auto b = unordered_map<int, int>();
2809 for(
int i = 0; i < nums.size(); i++) {
2821 for(
const auto i: a) {
2822 if(maximum < i.second) {
2827 ans1 += a_sum - maximum;
2829 for(
const auto i: b) {
2830 if(i.first != max_num && maximum < i.second) {
2834 ans1 += b_sum - maximum;
2839 for(
const auto i: b) {
2840 if(maximum < i.second) {
2845 ans2 += b_sum - maximum;
2847 for(
const auto i: a) {
2848 if(i.first != max_num && maximum < i.second) {
2852 ans2 += a_sum - maximum;
2853 return min(ans1, ans2);
2859 sort(beans.begin(), beans.end());
2861 long long maximum = 0;
2862 for(
int i = 0; i < beans.size(); i++) {
2864 maximum = max(maximum,
static_cast<long long>(beans[i] * (beans.size() - i)));
2866 return sum - maximum;
2873 vector<int> max_and_sum_of_status(1 << numSlots * 2);
2874 for(
unsigned int status = 0; status < max_and_sum_of_status.size(); ++status) {
2876 const int one_count = popcount(status);
2877 if(one_count >= nums.size()) {
2880 for(
int next_slot = 0; next_slot < numSlots * 2; ++next_slot) {
2881 if((status & 1 << next_slot) == 0) {
2883 const int next_status = status | 1 << next_slot;
2884 const auto slot_num = next_slot / 2 + 1;
2885 max_and_sum_of_status[next_status] = max(max_and_sum_of_status[next_status], max_and_sum_of_status[status] + (slot_num & nums[one_count]));
2886 ans = max(ans, max_and_sum_of_status[next_status]);
2897 int r = nums.size() - 1;
2903 if(r == nums.size() - 1) {
2906 if(nums[l - 1] == nums[l]) {
2911 const int m = (l + r) / 2;
2913 if(nums[m + 1] == nums[m]) {
2930 auto ans = vector<int>();
2931 const auto m = matrix.size();
2932 const auto n = matrix[0].size();
2933 auto *minimum =
new int[m];
2934 memset(minimum, 50, m *
sizeof(
int));
2935 auto *maximum =
new int[n];
2936 memset(maximum, 0, n *
sizeof(
int));
2937 for(
int i = 0; i < m; i++) {
2938 for(
int j = 0; j < n; j++) {
2939 minimum[i] = min(minimum[i], matrix[i][j]);
2940 maximum[j] = max(maximum[j], matrix[i][j]);
2943 for(
int i = 0; i < m; i++) {
2944 for(
int j = 0; j < n; j++) {
2945 if(matrix[i][j] == minimum[i] && matrix[i][j] == maximum[j]) {
2946 ans.push_back(matrix[i][j]);
2958 unordered_map<int, unordered_set<int>> adj;
2959 for(
auto &p: pairs) {
2960 adj[p[0]].emplace(p[1]);
2961 adj[p[1]].emplace(p[0]);
2965 for(
auto &[node, neighbours]: adj) {
2966 if(neighbours.size() == adj.size() - 1) {
2976 for(
auto &[node, neighbours]: adj) {
2980 const int currDegree = neighbours.size();
2982 int parentDegree = INT_MAX;
2985 for(
const auto &neighbour: neighbours) {
2986 if(adj[neighbour].size() < parentDegree && adj[neighbour].size() >= currDegree) {
2988 parentDegree = adj[neighbour].size();
2996 for(
const auto &neighbour: neighbours) {
2997 if(neighbour == parent) {
3000 if(
static_cast<unsigned int>(adj[parent].contains(neighbour)) == 0U) {
3004 if(parentDegree == currDegree) {
3014 auto um = unordered_map<int, int>();
3015 for(
auto edge: edges) {
3018 if(um[edge[0]] > 1) {
3021 if(um[edge[1]] > 1) {
3034 const auto s =
status(k, row, column);
3035 if(
um.count(s) == 1) {
3039 pair<int, int> nexts[8] = {make_pair(row - 2, column - 1),
3040 make_pair(row - 2, column + 1),
3041 make_pair(row + 2, column - 1),
3042 make_pair(row + 2, column + 1),
3043 make_pair(row - 1, column - 2),
3044 make_pair(row - 1, column + 2),
3045 make_pair(row + 1, column - 2),
3046 make_pair(row + 1, column + 2)};
3048 for(
auto [next_x, next_y]: nexts) {
3049 if(0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
3053 const double ans = sum / 8;
3065 auto ans = vector<int>();
3066 const int n = arr.size();
3067 auto *current =
new int[n];
3068 auto *sorted =
new int[n];
3069 for(
int i = 0; i < n; i++) {
3070 current[i] = arr[i];
3073 sort(sorted, sorted + n);
3075 for(
int i = n - 1; i >= 0; i--) {
3076 if(current[i] != sorted[i]) {
3077 const int target = sorted[i];
3079 for(
int j = 0; j <= i; j++) {
3080 if(current[j] == target) {
3088 ans.push_back(target_i);
3089 for(
int j = 0; j < target_i / 2; j++) {
3090 swap(current[j], current[target_i - j - 1]);
3104 for(
int i = 0; i + 1 < nums.size(); i++) {
3105 for(
int j = i + 1; j < nums.size(); j++) {
3106 if(nums[i] == nums[j] && i * j % k == 0) {
3118 const long long mid = num / 3;
3119 vector ans = {mid - 1, mid, mid + 1};
3128 if(finalSum % 2 != 0) {
3134 auto ans = vector<long long int>();
3137 for(
long long i = 4; i <= finalSum; i += 2) {
3138 const long long int next = finalSum - i;
3143 ans.push_back(finalSum);
3153 const int n = nums1.size();
3155 unordered_map<int, int> pos;
3156 for(
int i = 0; i < n; ++i) {
3157 pos[nums2[i]] = i + 1;
3160 for(
int i = 0; i < n; ++i) {
3161 const int idx = pos[nums1[i]];
3162 const int left = occur.
query(idx);
3163 const int right = n - idx - (occur.
query(n) - occur.
query(idx));
3164 ans += 1LL * left * right;
3175 for(
int i = 1; i <= num; i++) {
3193 while(head !=
nullptr && head->
val == 0) {
3197 while(head !=
nullptr && head->
next !=
nullptr) {
3213 for(
const char c: s) {
3216 auto oss = ostringstream();
3217 for(
int i = 25; i >= 0; i--) {
3220 oss << static_cast<char>(i +
'a');
3223 if(repeat == repeatLimit && ch[i] != 0) {
3224 for(
int j = i - 1; j >= 0; j--) {
3226 oss << static_cast<char>(j +
'a');
3246 auto count = unordered_map<int, int>();
3247 for(
const auto num: nums) {
3250 const int maximum = *max_element(nums.begin(), nums.end());
3252 for(
int i = 1; i <= maximum; i++) {
3253 for(
int j = i * 2; j <= maximum; j += i) {
3254 count[i] += count[j];
3257 for(
const auto num: nums) {
3259 ans += count[k / gcd(k, num)];
3260 if(
static_cast<long long>(num) * num % k == 0) {
3271 for(
int i = 0; i < bits.size();) {
3278 if(next >= bits.size()) {
3279 return i == bits.size() - 1;
3289 if(arr.size() < 3) {
3292 auto up_down = vector<int>(arr.size() - 1);
3293 for(
int i = 0; i + 1 < arr.size(); i++) {
3294 if(arr[i] < arr[i + 1]) {
3296 }
else if(arr[i] > arr[i + 1]) {
3302 auto sector_size = vector<pair<int, int>>();
3303 int prev = up_down[0];
3305 for(
int i = 1; i < up_down.size(); i++) {
3306 if(up_down[i] != prev) {
3307 sector_size.emplace_back(prev, count);
3314 sector_size.emplace_back(prev, count);
3315 if(sector_size.size() < 2) {
3319 for(
int i = 0; i + 1 < sector_size.size(); i++) {
3320 if(sector_size[i].first == 1 && sector_size[i + 1].first == 0) {
3321 maximum = max(maximum, sector_size[i].second + sector_size[i + 1].second + 1);
3330 const int n = dominoes.length();
3331 auto *left_to_r =
new int[n];
3332 auto *right_to_l =
new int[n];
3333 auto *left_is =
new char[n];
3334 auto *right_is =
new char[n];
3338 for(
int i = 0; i < n; i++) {
3339 if(dominoes[i] !=
'.') {
3345 for(
int i = n - 1; i >= 0; i--) {
3346 if(dominoes[i] !=
'.') {
3351 for(
int i = 0; i < n; i++) {
3352 if(dominoes[i] ==
'R') {
3359 for(
int i = n - 1; i >= 0; i--) {
3360 if(dominoes[i] ==
'L') {
3365 right_to_l[i] = r2l;
3367 for(
int i = 0; i < n; i++) {
3368 if(dominoes[i] ==
'.') {
3369 if(left_is[i] ==
'R' && right_is[i] ==
'L') {
3370 if(right_to_l[i] > left_to_r[i]) {
3372 }
else if(left_to_r[i] > right_to_l[i]) {
3375 }
else if(right_is[i] ==
'L') {
3377 }
else if(left_is[i] ==
'R') {
3383 delete[] right_to_l;
3392 vector<int> freq(
num_max + 1);
3393 for(
const int num: nums) {
3399 for(
int i = 0; i < freq[1]; ++i) {
3400 f[0] = f[0] * 2 %
mod;
3403 for(
int i = 2; i <=
num_max; ++i) {
3412 for(
int j = 0; j <
primes.size(); j++) {
3413 const int prime =
primes[j];
3414 if(x % (prime * prime) == 0) {
3418 if(x % prime == 0) {
3427 for(
int mask =
mask_max - 1; mask > 0; mask--) {
3428 if((mask & subset) == subset) {
3429 f[mask] = (f[mask] +
static_cast<long long>(f[mask ^ subset]) * freq[i]) %
mod;
3434 for(
int mask = 1; mask <
mask_max; mask++) {
3435 ans = (ans + f[mask]) %
mod;
3443 for(
int i = 0, j = s.length() - 1; i < j && i < s.length() && j >= 0;) {
3444 if(isalpha(s[i]) != 0 && isalpha(s[j]) != 0) {
3445 const char temp = s[i];
3451 while(i < s.length() && isalpha(s[i]) == 0) {
3454 while(j >= 0 && isalpha(s[j]) == 0) {
3465 const int m = grid.size();
3466 const int n = grid[0].size();
3468 for(
int i = 0; i < n; i++) {
3473 if(current_x == m) {
3477 if(current_x < 0 || current_y < 0 || current_y >= n) {
3483 if(grid[current_x][current_y] == 1) {
3488 }
else if(dir == 1) {
3490 if(grid[current_x][current_y] == 1) {
3497 if(grid[current_x][current_y] == 1) {
3507 }
else if(dir == 1) {
3522 auto ss = stringstream();
3535 const int r = r1 * r2 - i1 * i2;
3536 const int i = r1 * i2 + r2 * i1;
3537 ss = stringstream();
3538 ss << r <<
'+' << i <<
'i';
3547 for(
int i = 1; i < nums.size(); i++) {
3548 if(nums[i] > minn) {
3549 max_diff = max(max_diff, nums[i] - minn);
3551 minn = min(minn, nums[i]);
3559 auto oss = ostringstream();
3560 if(nums.size() == 1) {
3562 }
else if(nums.size() == 2) {
3563 oss << nums[0] <<
'/' << nums[1];
3565 oss << nums[0] <<
"/(";
3566 for(
int i = 1; i < nums.size() - 1; i++) {
3567 oss << nums[i] <<
'/';
3569 oss << nums[nums.size() - 1] <<
')';
3578 for(
auto word: words) {
3580 for(
int i = 0; i < pref.length(); i++) {
3581 if(pref[i] != word[i]) {
3599 for(
const char ch: s) {
3602 for(
const char ch: t) {
3605 for(
int i = 0; i < 26; i++) {
3606 ans += abs(s_num[i] - t_num[i]);
3617 max_t = max(max_t, t);
3618 min_t = min(min_t, t);
3620 long long l =
static_cast<long long>(totalTrips) / max_t / time.size();
3621 long long r =
static_cast<long long>(totalTrips) * max_t;
3623 const long long m = (l + r) / 2;
3625 for(
const auto t: time) {
3628 if(l == r || l + 1 == r) {
3631 if(sum >= totalTrips) {
3633 }
else if(sum < totalTrips) {
3644 vector<long long> min_times(20, 1e9);
3645 for(
auto &v: tires) {
3646 const long long f = v[0];
3647 const long long r = v[1];
3648 const long long cost = f + changeTime;
3649 long long current = f;
3650 long long sum = cost;
3651 for(
int i = 1; i <= 19; i++) {
3652 min_times[i] = min(min_times[i], sum);
3654 if(current > cost) {
3663 vector<long long> dp(numLaps + 1, 1e9);
3665 for(
int i = 1; i <= numLaps; i++) {
3666 for(
int j = 1; j <= min(19, i); j++) {
3667 dp[i] = min(dp[i], dp[i - j] + min_times[j]);
3671 return dp[numLaps] - changeTime;
3678 for(
unsigned int i = 0; i < 1 << requests.size(); i++) {
3679 auto *in =
new int[n];
3680 auto *out =
new int[n];
3681 memset(in, 0, n *
sizeof(
int));
3682 memset(out, 0, n *
sizeof(
int));
3683 for(
unsigned int j = 0; j < requests.size(); j++) {
3684 if((i & 1 << j) != 0) {
3685 out[requests[j][0]]++;
3686 in[requests[j][1]]++;
3690 for(
int j = 0; j < n; j++) {
3691 if(out[j] != in[j]) {
3697 ans = max(ans, popcount(i));
3711 auto oss = ostringstream();
3712 auto *m =
new char *[numRows];
3713 for(
int i = 0; i < numRows; i++) {
3714 m[i] =
new char[s.length()];
3715 memset(m[i],
' ', s.length() *
sizeof(
char));
3720 for(
const char ch: s) {
3721 m[current_x][current_y] = ch;
3722 if(dir && current_x == numRows - 1 || !dir && current_x == 0) {
3732 for(
int i = 0; i < numRows; i++) {
3733 for(
int j = 0; j <= min(current_y, static_cast<int>(s.length() - 1)); j++) {
3734 if(m[i][j] !=
' ') {
3739 for(
int i = 0; i < numRows; i++) {
3749 const long long num = stoll(n);
3750 if(num == 10 || num == 11) {
3754 return to_string(num - 1);
3756 int len = n.length();
3757 const bool even = n.length() % 2 == 0;
3758 string prefix = n.substr(0, n.length() / 2 + (even ? 0 : 1));
3759 string option_str[3];
3760 auto rev = string(prefix.rbegin() + (even ? 0 : 1), prefix.rend());
3761 option_str[2] = prefix + rev;
3762 const long long prefix_int[2] = {stoll(prefix) - 1, stoll(prefix) + 1};
3763 string prefix_str[2] = {to_string(prefix_int[0]), to_string(prefix_int[1])};
3764 for(
int i = 0; i < 2; i++) {
3765 if(prefix_str[i].length() == prefix.length()) {
3766 rev = string(prefix_str[i].rbegin() + (even ? 0 : 1), prefix_str[i].rend());
3767 option_str[i] = prefix_str[i] + rev;
3768 }
else if(prefix_str[i].length() > prefix.length()) {
3769 rev = string(prefix_str[i].rbegin() + (even ? 1 : 2), prefix_str[i].rend());
3770 option_str[i] = prefix_str[i] + rev;
3771 }
else if(prefix_str[i].length() < prefix.length()) {
3772 rev = string(prefix_str[i].rbegin(), prefix_str[i].rend());
3773 option_str[i] = prefix_str[i] + (even ?
"9" :
"") + rev;
3776 long long option_int[3] = {stoll(option_str[0]), stoll(option_str[1]), stoll(option_str[2])};
3777 sort(option_int, option_int + 3);
3778 long long minimum = option_int[0];
3779 for(
int i = 1; i < 3; i++) {
3780 if(abs(option_int[i] - num) < abs(minimum - num) && option_int[i] != num) {
3781 minimum = option_int[i];
3784 return to_string(minimum);
3795 for(
int i = 0; i + 1 < nums.size(); i++) {
3796 int minimum = nums[i];
3797 int maximum = nums[i];
3798 for(
int j = i + 1; j < nums.size(); j++) {
3799 minimum = min(minimum, nums[j]);
3800 maximum = max(maximum, nums[j]);
3801 ans += maximum - minimum;
3810 if(a.length() != b.length() || b.find(a) == string::npos && a.find(b) == string::npos) {
3811 return max(a.length(), b.length());
3819 unordered_map<int, int> um;
3820 for(
int i = 0; i + 1 < nums.size(); i++) {
3821 if(nums[i] == key) {
3827 for(
auto [k, v]: um) {
3839 vector<tuple<int, int, int>> vec;
3840 for(
int i = 0; i < nums.size(); i++) {
3841 string str = to_string(nums[i]);
3843 for(
const char ch: str) {
3844 oss << mapping[ch -
'0'];
3846 vec.emplace_back(i, nums[i], stoi(oss.str()));
3848 sort(vec.begin(), vec.end(),
cmp());
3850 ans.reserve(vec.size());
3851 for(
auto [i, num, rev]: vec) {
3860 for(
int i = 0; i < n; i++) {
3861 nexts[i] = unordered_set<int>();
3864 for(
auto edge: edges) {
3865 nexts[edge[0]].insert(edge[1]);
3867 for(
int i = 0; i < n; i++) {
3868 for(
const auto next:
nexts[i]) {
3869 auto *dfsd =
new bool[n];
3870 memset(dfsd, 0, n *
sizeof(
bool));
3875 vector<vector<int>> ans;
3876 for(
int i = 0; i < n; i++) {
3889 for(
const auto next:
nexts[i]) {
3900 for(
int left = 0, right = s.size() - 1; left < right; left++) {
3902 for(
int i = right; left != i; i--) {
3903 if(s[left] == s[i]) {
3906 for(; i < right; i++) {
3907 swap(s[i], s[i + 1]);
3916 ans += s.size() / 2 - left;
3926 istringstream ss(s);
3934 for(
char col = col1; col <= col2; col++) {
3935 for(
int row = row1; row <= row2; row++) {
3938 ans.push_back(oss.str());
3949 for(
auto num: nums) {
3952 long long limit = k;
3953 for(
auto i = s.begin(); i != s.end() && *i <= limit; ++i) {
3956 ans += limit + limit * (limit - 1) / 2;
3957 for(
auto i = s.begin(); i != s.end() && *i < limit; ++i) {
3966 unordered_map<int, TreeNode *> um;
3967 unordered_set<int> nodes;
3968 unordered_set<int> childs;
3969 for(
auto description: descriptions) {
3970 nodes.insert(description[0]);
3971 nodes.insert(description[1]);
3972 childs.insert(description[1]);
3974 for(
auto node: nodes) {
3977 for(
auto description: descriptions) {
3978 if(description[2] == 1) {
3980 um[description[0]]->left = um[description[1]];
3983 um[description[0]]->right = um[description[1]];
3986 for(
auto node: nodes) {
3987 if(!childs.contains(node)) {
3998 for(
int i = 0; i < nums.size(); i++) {
4000 while(!ans.empty() && gcd(num, ans.back()) > 1) {
4001 num = num / gcd(num, ans.back()) * ans.back();
4012 if(security.size() < 2 * time + 1) {
4017 for(
int i = 0; i < security.size(); i++) {
4022 vector non_increasing(security.size(), 0);
4023 vector non_decreasing(security.size(), 0);
4024 for(
int i = 1; i < security.size(); i++) {
4025 if(security[i] >= security[i - 1]) {
4026 non_decreasing[i] = non_decreasing[i - 1] + 1;
4028 non_decreasing[i] = 0;
4030 if(security[i] <= security[i - 1]) {
4031 non_increasing[i] = non_increasing[i - 1] + 1;
4033 non_increasing[i] = 0;
4036 for(
int i = time; i + time < security.size(); i++) {
4037 if(non_decreasing[i + time] >= time && non_increasing[i] >= time) {
4057 deq.push_front(num % 7);
4064 for(
const int n: deq) {
4074 vector<int> plate_count(s.length());
4075 vector<int> candle_pos;
4080 candle_pos.push_back(0);
4082 for(
int i = 1; i < s.length(); i++) {
4083 plate_count[i] = plate_count[i - 1];
4087 candle_pos.push_back(i);
4090 for(
auto query: queries) {
4091 int left = query[0];
4092 int right = query[1];
4093 auto li = lower_bound(candle_pos.begin(), candle_pos.end(), left);
4094 if(li == candle_pos.end() || *li > right) {
4098 auto ri = lower_bound(candle_pos.rbegin(), candle_pos.rend(), right, greater<int>());
4099 if(ri == candle_pos.rend() || *ri < left) {
4103 ans.push_back(plate_count[*ri] - plate_count[*li]);
4111 const int n = nums.size();
4112 vector k_score_diff(n + 1, 0);
4113 for(
int i = 0; i < n; i++) {
4114 const int low = (i + 1) % n;
4115 const int high = (i - nums[i] + n) % n;
4116 k_score_diff[low]++;
4117 k_score_diff[high + 1]--;
4126 for(
int i = 0; i < n; i++) {
4127 score += k_score_diff[i];
4128 if(score > max_score) {
4139 if(root ==
nullptr) {
4143 ans.push_back(root->val);
4144 for(
auto *child: root->children) {
4145 auto preorder_child =
preorder(child);
4146 ans.insert(ans.end(), preorder_child.begin(), preorder_child.end());
4155 auto nodes = vector<TreeNode *>(parents.size(),
nullptr);
4156 auto edges = vector(parents.size(), vector<int>());
4157 auto scores = vector<unsigned long long>(parents.size(), 0);
4158 for(
int i = 0; i < parents.size(); i++) {
4160 if(parents[i] != -1) {
4161 edges[i].push_back(parents[i]);
4162 edges[parents[i]].push_back(i);
4166 for(
int i = 0; i < parents.size(); i++) {
4167 if(parents[i] != -1) {
4168 nodes[parents[i]]->add_child(nodes[i]);
4174 unsigned long long max_score = 0;
4175 for(
int i = 0; i < parents.size(); i++) {
4176 unsigned long long score = 1;
4177 const auto *node = nodes[i];
4178 for(
const auto *child: node->get_children()) {
4179 score *= child->get_count();
4181 if(node->get_parent() !=
nullptr) {
4182 score *= root->get_count() - node->get_count();
4184 max_score = max(max_score, score);
4187 return count(scores.begin(), scores.end(), max_score);
4198 ans += child->dfs();
4213 if(root ==
nullptr) {
4217 for(
auto *child: root->children) {
4219 ans.insert(ans.end(), res.begin(), res.end());
4221 ans.push_back(root->val);
4228 const int m = grid.size();
4229 const int n = grid[0].size();
4232 for(
int i = 0; i < m; i++) {
4233 for(
int j = 0; j < n; j++) {
4234 if(grid[i][j] == 1) {
4235 const pair<int, int> p = make_pair(i, j);
4236 ans = max(ans, uf.get_size(p));
4237 pair<int, int> siblings[4] = {
4238 make_pair(i + 1, j),
4239 make_pair(i - 1, j),
4240 make_pair(i, j + 1),
4241 make_pair(i, j - 1),
4243 for(
const auto sibling: siblings) {
4244 if(uf.contains(sibling) && grid[sibling.first][sibling.second] == 1 && !uf.same(p, sibling)) {
4245 uf.merge(p, sibling);
4246 ans = max(ans, uf.get_size(p));
4257 parent = unordered_map<pair<int, int>,
4259 function<
unsigned int(
const pair<int, int> &)>>(
4261 [](
const pair<int, int> &p) {
return static_cast<unsigned int>(p.first * 50 + p.second); });
4262 size = unordered_map<pair<int, int>,
4264 function<
unsigned int(
const pair<int, int> &)>>(
4266 [](
const pair<int, int> &p) {
return static_cast<unsigned int>(p.first * 50 + p.second); });
4267 rank = unordered_map<pair<int, int>,
4269 function<
unsigned int(
const pair<int, int> &)>>(
4271 [](
const pair<int, int> &p) {
return static_cast<unsigned int>(p.first * 50 + p.second); });
4272 for(
int i = 0; i <
m; i++) {
4273 for(
int j = 0; j <
n; j++) {
4274 pair<int, int> p = make_pair(i, j);
4290 const auto pa =
find(a);
4291 const auto pb =
find(b);
4293 const int sum =
size[pa] +
size[pb];
4318 for(
int i = 0; i < nums.size(); i++) {
4319 if(nums[i] == key) {
4323 for(
const auto ks: key_set) {
4324 for(
int i = ks - k; i <= ks + k; i++) {
4325 if(0 <= i && i < nums.size()) {
4330 return vector(ans_set.begin(), ans_set.end());
4336 auto *grid =
new bool *[n];
4337 for(
int i = 0; i < n; i++) {
4338 grid[i] =
new bool[n];
4339 memset(grid[i], 0, n *
sizeof(
bool));
4342 grid[i[0]][i[1]] =
true;
4345 for(
auto artifact: artifacts) {
4347 for(
int i = artifact[0]; i <= artifact[2]; i++) {
4348 for(
int j = artifact[1]; j <= artifact[3]; j++) {
4362 for(
int i = 0; i < n; i++) {
4372 if(nums.size() == 1 && k % 2 == 1) {
4375 if(k > nums.size()) {
4377 for(
auto num: nums) {
4378 ans = max(ans, num);
4382 unordered_map<int, int> element_count;
4383 set<int> poped_elements;
4384 for(
auto num: nums) {
4385 element_count[num]++;
4387 for(
int i = 0; i < nums.size() && i < k - 1; i++) {
4388 poped_elements.insert(nums[i]);
4389 element_count[nums[i]]--;
4392 if(k < nums.size()) {
4396 for(
const auto i = poped_elements.rbegin(); i != poped_elements.rend();) {
4400 return max(ans, maximum);
4406 auto *graph =
new vector<pair<int, int>>[n];
4407 auto *graph_rev =
new vector<pair<int, int>>[n];
4408 for(
int i = 0; i < n; i++) {
4409 graph[i] = vector<pair<int, int>>();
4410 graph_rev[i] = vector<pair<int, int>>();
4412 for(
auto &edge: edges) {
4413 auto from = edge[0];
4415 auto weight = edge[2];
4416 graph[from].emplace_back(to, weight);
4417 graph_rev[to].emplace_back(from, weight);
4420 long long a = LLONG_MAX;
4421 vector dist_src1(n, LLONG_MAX);
4422 vector dist_src2(n, LLONG_MAX);
4423 vector dist_dest(n, LLONG_MAX);
4429 long long ans = LLONG_MAX;
4431 for(
int i = 0; i < n; ++i) {
4432 if(dist_src1[i] != LLONG_MAX && dist_src2[i] != LLONG_MAX && dist_dest[i] != LLONG_MAX) {
4433 ans = min(ans, dist_src1[i] + dist_src2[i] + dist_dest[i]);
4436 if(ans == LLONG_MAX) {
4445 priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
4448 while(!pq.empty()) {
4449 auto [weight, node] = pq.top();
4451 if(weight > dist[node]) {
4454 for(
auto [next_node, next_weight]: graph[node]) {
4455 if(weight + next_weight < dist[next_node]) {
4456 dist[next_node] = weight + next_weight;
4457 pq.emplace(weight + next_weight, next_node);
4467 for(
const auto num: data) {
4471 }
else if(num >> 3 == 30) {
4474 }
else if(num >> 4 == 14) {
4477 }
else if(num >> 5 == 6) {
4480 }
else if(num >> 6 == 2) {
4488 for(
int i = 0; i < len.size(); i++) {
4507 unordered_map<string, int> restaurants;
4508 unordered_map<string, int> index1;
4509 unordered_map<string, int> index2;
4510 for(
int i = 0; i < list1.size(); i++) {
4511 restaurants[list1[i]]++;
4512 index1[list1[i]] = i;
4514 for(
int i = 0; i < list2.size(); i++) {
4515 restaurants[list2[i]]++;
4516 index2[list2[i]] = i;
4518 unordered_set<string> optional_restaurants;
4519 for(
auto [restaurant, count]: restaurants) {
4521 optional_restaurants.insert(restaurant);
4524 int min_index_sum = INT_MAX;
4525 for(
const auto &optional_restaurant: optional_restaurants) {
4526 int index_sum = index1[optional_restaurant] + index2[optional_restaurant];
4527 min_index_sum = min(min_index_sum, index_sum);
4530 for(
const auto &optional_restaurant: optional_restaurants) {
4531 int index_sum = index1[optional_restaurant] + index2[optional_restaurant];
4532 if(index_sum == min_index_sum) {
4533 ans.push_back(optional_restaurant);
4543 for(
const auto num: nums) {
4546 return dfs(0, max, nums);
4550 if((current | target) == current) {
4551 return 1 << nums.size();
4554 vector nums_cpy = nums;
4555 for(
int i = 0; i < nums.size(); i++) {
4556 nums_cpy.erase(nums_cpy.begin());
4557 sum +=
dfs(current | nums[i], target, nums_cpy);
4565 str_count = unordered_map<string, int>();
4566 count_str = map<int, unordered_set<string>>();
4624 for(
const auto &word: words) {
4627 return dfs(
"", &root);
4632 for(
auto *next: node->
nexts) {
4633 if(next !=
nullptr && next->end_of_word) {
4634 string ret =
dfs(str + next->ch, next);
4635 if(ans.length() < ret.length()) {
4646 accounts = unordered_map<int, long long>(balance.size());
4647 for(
int i = 0; i < balance.size(); i++) {
4688 if(root->left !=
nullptr) {
4689 oss <<
'(' <<
tree2str(root->left) <<
')';
4690 }
else if(root->right !=
nullptr) {
4693 if(root->right !=
nullptr) {
4694 oss <<
'(' <<
tree2str(root->right) <<
')';
4703 long long count = 0;
4704 vector<long long> p1count(text.length());
4705 long long p0count = 0;
4707 p1count[text.length() - 1] = 0;
4708 for(
int i = text.length() - 1; i >= 0; i--) {
4709 if(text[i] == pattern[1]) {
4711 }
else if(text[i] == pattern[0]) {
4715 p1count[i - 1] = count;
4718 for(
int i = 0; i < text.length(); i++) {
4719 if(text[i] == pattern[0]) {
4723 ans += max(p0count, count);
4730 long double sum = 0;
4732 priority_queue<long double> pq;
4733 for(
const auto num: nums) {
4737 const long double target = sum / 2;
4738 while(sum > target) {
4739 auto num = pq.top();
4752 const int n = floor.length();
4753 vector f(numCarpets + 1, vector<int>(n));
4754 f[0][0] = floor[0] % 2;
4755 for(
int i = 1; i < n; ++i) {
4756 f[0][i] = f[0][i - 1] + floor[i] % 2;
4758 for(
int i = 1; i <= numCarpets; ++i) {
4760 for(
int j = carpetLen; j < n; ++j) {
4761 f[i][j] = min(f[i][j - 1] + floor[j] % 2, f[i - 1][j - carpetLen]);
4764 return f[numCarpets][n - 1];
4771 const auto u = unique(nums.begin(), nums.end());
4772 nums.erase(u, nums.end());
4773 for(
int i = 1; i + 1 < nums.size(); i++) {
4774 if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1] || nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) {
4785 vector<char> status;
4788 for(
char ch: directions) {
4789 if(status.empty()) {
4790 status.push_back(ch);
4793 if(status.back() == ch) {
4796 status.push_back(ch);
4797 count.push_back(current);
4802 count.push_back(current);
4803 for(
int i = 0; i + 1 < status.size(); i++) {
4804 if(status[i] ==
'R' && status[i + 1] ==
'L') {
4805 ans += count[i] + count[i + 1];
4806 }
else if(status[i] ==
'R' && status[i + 1] ==
'S') {
4808 }
else if(status[i] ==
'S' && status[i + 1] ==
'L') {
4809 ans += count[i + 1];
4820 for(
unsigned int n = 1; n < 1 << 11; n++) {
4821 int rest = numArrows;
4823 for(
int i = 0; i <= 10; i++) {
4824 if((n & 1 << i) != 0) {
4826 rest -= aliceArrows[11 - i] + 1;
4832 if(maximum < score) {
4838 vector ans(aliceArrows.size(), 0);
4839 for(
int i = 0; i <= 10; i++) {
4840 if((max_n & 1 << i) != 0) {
4841 numArrows -= aliceArrows[11 - i] + 1;
4842 ans[11 - i] = aliceArrows[11 - i] + 1;
4845 ans[0] += numArrows;
4852 unordered_map<int, Node *> um;
4853 unordered_set<int> nodes;
4854 for(
int i = 0; i < patience.size(); i++) {
4855 um[i] =
new Node(i, patience[i]);
4858 for(
auto edge: edges) {
4859 um[edge[0]]->linked.insert(edge[1]);
4860 um[edge[1]]->linked.insert(edge[0]);
4862 auto comp = [](
const pair<int, int> &s1,
const pair<int, int> &s2) ->
bool {
return s1.second > s2.second; };
4863 priority_queue<pair<int, int>, vector<pair<int, int>>,
decltype(comp)> pq;
4864 pq.push(make_pair(0, 0));
4865 while(!nodes.empty()) {
4866 auto [num, len] = pq.top();
4868 if(nodes.contains(num)) {
4870 Node *node = um[num];
4872 for(
auto next: node->
linked) {
4873 if(nodes.contains(next)) {
4874 pq.push(make_pair(next, len + 1));
4880 for(
auto [num, node]: um) {
4882 int resent_num = node->time * 2 / node->patience;
4883 if(node->time * 2 % node->patience == 0) {
4886 ans = max(ans, resent_num * node->patience + 2 * node->time + 1);
4896 unordered_map<int, int> count;
4897 queue<TreeNode *> que;
4899 while(!que.empty()) {
4900 const auto *node = que.front();
4902 s.insert(node->val);
4904 if(node->left !=
nullptr) {
4905 que.push(node->left);
4907 if(node->right !=
nullptr) {
4908 que.push(node->right);
4912 for(
auto it = s.begin(); it != s.end(); ++it) {
4913 int other = k - *it;
4915 if(count[other] > 1) {
4919 }
else if(s.contains(other)) {
4932 vector vec(colors.length(),
true);
4934 vec[colors.length() - 1] =
false;
4935 for(
int i = 0; i + 1 < colors.length(); i++) {
4936 if(colors[i] != colors[i + 1]) {
4941 for(
int i = 0; i + 1 < colors.length(); i++) {
4943 if(colors[i] ==
'A') {
4950 return a_count > b_count;
4959 const int steps =
getSteps(curr, n);
4976 steps += min(last, n) - first + 1;
4978 last = last * 10 + 9;
4986 const int m = img.size();
4987 const int n = img[0].size();
4988 auto ans = vector(m, vector<int>(n));
4989 for(
int i = 0; i < m; i++) {
4990 for(
int j = 0; j < n; j++) {
4991 pair<int, int> cells[9] = {make_pair(i - 1, j - 1), make_pair(i - 1, j), make_pair(i - 1, j + 1),
4992 make_pair(i, j - 1), make_pair(i, j), make_pair(i, j + 1),
4993 make_pair(i + 1, j - 1), make_pair(i + 1, j), make_pair(i + 1, j + 1)};
4996 for(
int k = 0; k < 9; k++) {
4997 auto [x, y] = cells[k];
4998 if(0 <= x && x < m && 0 <= y && y < n) {
5003 ans[i][j] = sum / count;
5012 unsigned int pow5 = 5;
5013 unsigned int pow2 = 2;
5014 unsigned int count5 = 0;
5015 unsigned int count2 = 0;
5016 while(n / pow5 != 0) {
5020 while(n / pow2 != 0) {
5024 return min(count2, count5);
5031 for(
const string &op: ops) {
5033 const int score1 = stk.back();
5034 const int score2 = *(stk.rbegin() + 1);
5035 stk.push_back(score1 + score2);
5036 }
else if(op ==
"D") {
5037 stk.push_back(2 * stk.back());
5038 }
else if(op ==
"C") {
5045 stk.push_back(score);
5049 for(
const auto score: stk) {
5058 vector<int> indexes;
5059 for(
int i = 0; i + 1 < nums.size(); i++) {
5060 if(nums[i] == nums[i + 1]) {
5061 indexes.push_back(i);
5066 for(
const auto index: indexes) {
5067 if(even && index % 2 == 0 || !even && index % 2 != 0) {
5072 if((nums.size() - ans) % 2 != 0) {
5080 unsigned long long qmi(
unsigned long long m,
unsigned long long k) {
5081 unsigned long long res = 1;
5082 unsigned long long t = m;
5094 vector<long long> ans;
5095 if(intLength == 1) {
5096 for(
auto query: queries) {
5098 ans.push_back(query);
5105 if(intLength == 2) {
5106 for(
auto query: queries) {
5108 ans.push_back(query * 10 + query);
5115 int n = (intLength + 1) / 2;
5116 vector<unsigned long long> q10(n + 1);
5117 for(
int i = 1; i <= n; i++) {
5118 q10[i] =
qmi(10, n - i);
5120 for(
auto query: queries) {
5121 vector<unsigned long long> num;
5122 int n1 = query / q10[1] + 1;
5123 if(n1 == 10 && query % q10[1] == 0) {
5125 for(
int i = 0; i < intLength; i++) {
5137 if(n1 < 10 && query % q10[1] == 0) {
5139 query = (query - 1) % q10[1] + 1;
5144 for(
int i = 2; i <= n; i++) {
5145 int digit = query / q10[i];
5148 }
else if(query != q10[i] && query % q10[i] == 0) {
5150 }
else if(query == q10[i]) {
5154 num.push_back((digit + 10) % 10);
5157 for(
int digit: num) {
5160 int i = num.size() - 1;
5161 if(intLength % 2 != 0) {
5178 const int m = rolls.size();
5179 int sum = (m + n) * mean;
5180 for(
const auto roll: rolls) {
5183 if(sum < n || sum > 6 * n) {
5186 vector ans(n, sum / n);
5188 for(
int i = 0; i < sum; i++) {
5204 for(
int i = 0; i + 1 < str.length(); i++) {
5205 if(str[i] == str[i + 1]) {
5215 if(answerKey.length() == 1) {
5218 vector<int> t_count(answerKey.length());
5219 vector<int> f_count(answerKey.length());
5222 for(
int i = 0; i < t_count.size(); i++) {
5223 if(answerKey[i] ==
'T') {
5228 t_count[i] = t_current;
5229 f_count[i] = f_current;
5232 int r = answerKey.size();
5233 auto check = [&answerKey, &t_count, &f_count, &k](
int len) ->
bool {
5234 for(
int i = 0; i + len <= answerKey.length(); i++) {
5235 int tc = t_count[i + len - 1] - (i - 1 >= 0 ? t_count[i - 1] : 0);
5236 int fc = f_count[i + len - 1] - (i - 1 >= 0 ? f_count[i - 1] : 0);
5237 if(min(tc, fc) <= k) {
5250 const int mid = (l + r) / 2;
5266 for(
int i = 0; i < k; i++) {
5267 available.insert(i);
5269 priority_queue<event> events;
5270 for(
int i = 0; i < arrival.size(); i++) {
5271 event e = {arrival[i],
true, i};
5274 while(!events.empty()) {
5275 event e = events.top();
5278 if(!available.empty()) {
5279 auto it = available.lower_bound(e.index % k);
5280 if(it == available.end()) {
5281 it = available.begin();
5283 event next = {e.time + load[e.index],
false, e.index, *it};
5285 available.erase(it);
5289 available.insert(e.server_index);
5290 count[e.server_index]++;
5293 const int maximum = *max_element(count.begin(), count.end());
5294 for(
int i = 0; i < k; i++) {
5295 if(count[i] == maximum) {
5313 for(
int i = left; i <= right; ++i) {
5319 const int num = ch -
'0';
5339 multiset<int> positive;
5340 multiset<int, greater<>> negative;
5341 for(
auto num: arr) {
5343 positive.insert(num);
5345 negative.insert(num);
5348 while(!positive.empty()) {
5349 const int num = *positive.begin();
5350 positive.erase(positive.begin());
5351 auto it = positive.find(num * 2);
5352 if(it == positive.end()) {
5357 while(!negative.empty()) {
5358 const int num = *negative.begin();
5359 negative.erase(negative.begin());
5360 auto it = negative.find(num * 2);
5361 if(it == negative.end()) {
5374 const int n = password.length();
5375 bool has_lower =
false;
5376 bool has_upper =
false;
5377 bool has_digit =
false;
5378 for(
const char ch: password) {
5379 if(islower(ch) != 0) {
5381 }
else if(isupper(ch) != 0) {
5383 }
else if(isdigit(ch) != 0) {
5387 const int categories =
static_cast<int>(has_lower) +
static_cast<int>(has_upper) +
static_cast<int>(has_digit);
5390 return max(6 - n, 3 - categories);
5397 for(
const char ch: password) {
5401 replace += count / 3;
5406 replace += count / 3;
5407 return max(replace, 3 - categories);
5411 int remove = n - 20;
5417 for(
const char ch: password) {
5421 if(remove > 0 && count >= 3) {
5422 if(count % 3 == 0) {
5426 }
else if(count % 3 == 1) {
5432 replace += count / 3;
5437 if(remove > 0 && count >= 3) {
5438 if(count % 3 == 0) {
5441 }
else if(count % 3 == 1) {
5445 replace += count / 3;
5448 const int use2 = min({replace, rm2, remove / 2});
5452 const int use3 = min(replace, remove / 3);
5455 return n - 20 + max(replace, 3 - categories);
5461 const unsigned int n = s.length();
5462 vector<unsigned int> prev0(n, 0);
5463 vector<unsigned int> prev1(n, 0);
5464 vector<unsigned int> post0(n, 0);
5465 vector<unsigned int> post1(n, 0);
5466 unsigned current0 = 0;
5467 unsigned current1 = 0;
5468 for(
int i = 0; i < n; i++) {
5469 prev0[i] = current0;
5470 prev1[i] = current1;
5479 for(
int i = n - 1; i >= 0; i--) {
5480 post0[i] = current0;
5481 post1[i] = current1;
5489 for(
unsigned i = 0; i < n; i++) {
5491 ans +=
static_cast<long long>(prev1[i]) * post1[i];
5493 ans +=
static_cast<long long>(prev0[i]) * post0[i];
5502 const int n = s.length();
5507 for(
int i = 1; i < n; ++i) {
5508 if(i <= r && z[i - l] < r - i + 1) {
5511 z[i] = max(0, r - i + 1);
5512 while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
5516 if(i + z[i] - 1 > r) {
5531 const int current_h = (current[0] -
'0') * 10 + (current[1] -
'0');
5532 const int current_m = (current[3] -
'0') * 10 + (current[4] -
'0');
5533 const int correct_h = (correct[0] -
'0') * 10 + (correct[1] -
'0');
5534 const int correct_m = (correct[3] -
'0') * 10 + (correct[4] -
'0');
5535 int diff = correct_h * 60 + correct_m - (current_h * 60 + current_m);
5556 map<unsigned, unsigned> lose;
5557 for(
auto match: matches) {
5558 lose[match[0]] += 0;
5559 lose[match[1]] += 1;
5561 vector<vector<int>> ans(2);
5564 for(
auto [player, count]: lose) {
5566 ans1.push_back(player);
5567 }
else if(count == 1) {
5568 ans2.push_back(player);
5582 sort(candies.begin(), candies.end());
5584 for(
const auto candy: candies) {
5594 unsigned long long count = 0;
5595 for(
auto it = candies.rbegin(); it != candies.rend() && *it >= r; ++it) {
5606 const int m = (l + r) / 2;
5607 unsigned long long count = 0;
5608 for(
auto it = candies.rbegin(); it != candies.rend() && *it >= m; ++it) {
5616 }
else if(count < k) {
5626 for(
int i = 0; i < keys.size(); ++i) {
5627 mp[keys[i] -
'a'] = values[i];
5629 for(
const auto &s: dictionary) {
5636 for(
const char ch: word1) {
5637 const auto &s =
mp[ch -
'a'];
5647 if(
count.contains(word2)) {
5649 return count[word2];
5659 const int n =
nums.size();
5662 for(
int i = 0; i < n; i++) {
5673 const int b1 = left /
size;
5674 const int i1 = left %
size;
5675 const int b2 = right /
size;
5676 const int i2 = right %
size;
5679 return accumulate(
nums.begin() + b1 *
size + i1,
nums.begin() + b1 *
size + i2 + 1, 0);
5681 const int sum1 = accumulate(
nums.begin() + b1 *
size + i1,
nums.begin() + b1 *
size +
size, 0);
5682 const int sum2 = accumulate(
nums.begin() + b2 *
size,
nums.begin() + b2 *
size + i2 + 1, 0);
5683 const int sum3 = accumulate(
sum.begin() + b1 + 1,
sum.begin() + b2, 0);
5684 return sum1 + sum2 + sum3;
5691 vector<bool> ans(requests.size());
5692 auto check = [&uf, &restrictions](
int x,
int y) ->
bool {
5698 for(
auto &restriction: restrictions) {
5699 int i = uf.
find(restriction[0]);
5700 int j = uf.
find(restriction[1]);
5704 if(i == x && j == y) {
5710 for(
int i = 0; i < requests.size(); i++) {
5711 if(check(requests[i][0], requests[i][1])) {
5712 uf.
unite(requests[i][0], requests[i][1]);
5725 const unordered_set primes{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};
5726 for(
unsigned i = left; i <= right; i++) {
5727 if(primes.contains(popcount(i))) {
5740 vector<vector<int>> adj(n);
5741 for(
auto &edge: edges) {
5742 adj[edge[0]].emplace_back(edge[1]);
5743 adj[edge[1]].emplace_back(edge[0]);
5746 vector parent(n, -1);
5755 path.emplace_back(y);
5758 const int m = path.size();
5760 return {path[m / 2 - 1], path[m / 2]};
5762 return {path[m / 2]};
5766 const int n = adj.size();
5768 vector<bool> visit(n);
5773 while(!qu.empty()) {
5774 const int curr = qu.front();
5777 for(
auto &v: adj[curr]) {
5791 if(s.length() != goal.length()) {
5795 return s.find(goal) != string::npos;
5801 queue<pair<int, Node *>> q;
5802 vector<vector<int>> ans;
5803 if(root ==
nullptr) {
5806 q.push(make_pair(0, root));
5808 auto [level, node] = q.front();
5809 if(ans.size() == level) {
5812 ans[level].push_back(node->val);
5814 for(
auto *next: node->children) {
5815 q.push(make_pair(level + 1, next));
5824 while(tx > sx && ty > sy && tx != ty) {
5831 if(tx == sx && ty == sy) {
5835 return ty > sy && (ty - sy) % tx == 0;
5838 return tx > sx && (tx - sx) % ty == 0;
5846 priority_queue<int, vector<int>, greater<int>> pq;
5847 for(
auto num: nums) {
5851 const int num = pq.top();
5856 while(!pq.empty()) {
5857 const int num = pq.top();
5868 const int n = flowers.size();
5869 sort(flowers.begin(), flowers.end());
5870 for(
int i = 0; i < n; i++) {
5871 flowers[i] = min(flowers[i], target);
5874 vector<long long> sum(n + 1, 0);
5875 for(
int i = 0; i < n; i++) {
5876 sum[i + 1] = sum[i] + flowers[i];
5878 for(
int i = 0, j = 0; i <= n; i++) {
5879 const long long rest = newFlowers - (
static_cast<long long>(target) * (n - i) - (sum[n] - sum[i]));
5881 while(j < i && rest >=
static_cast<long long>(flowers[j]) * j - sum[j]) {
5885 ans = max(ans,
static_cast<long long>(full) * (n - i) + (j == 0 ? 0 :
static_cast<long long>(partial) * min(
static_cast<long long>(target - 1), (rest + sum[j]) / j)));
5887 if(i < n && flowers[i] == target) {
5900 vector<int> dp(n + 1);
5902 for(
int i = 2; i <= n; ++i) {
5903 dp[i] = dp[i - 1] * (10 - (i - 1));
5906 for(
int i = 1; i <= n; ++i) {
5917 for(
int i = 0; i < s.length(); i++) {
5918 if(current + widths[s[i] -
'a'] > 100) {
5922 current += widths[s[i] -
'a'];
5924 return {lines, current};
5930 if(s1.length() > s2.length()) {
5933 unordered_map<char, int> um1;
5934 unordered_map<char, int> um2;
5938 for(
int i = 0; i < s1.length(); i++) {
5944 for(
int i = 0; i + s1.length() < s2.length(); i++) {
5946 um2[s2[i + s1.length()]]++;
5947 if(um2[s2[i]] == 0) {
5960 generator = default_random_engine(time(
nullptr));
5965 if(
static_cast<unsigned int>(
map.contains(val)) != 0U) {
5968 nums.push_back(val);
5974 if(
static_cast<unsigned int>(
map.contains(val)) == 0U) {
5977 const int index =
map[val];
5978 const int last =
nums.back();
5991 const int n = grid.size();
5995 auto grid_xz = vector(51, vector(51, 0));
5996 auto grid_yz = vector(51, vector(51, 0));
5997 for(
int i = 0; i < n; i++) {
5998 for(
int j = 0; j < n; j++) {
5999 if(grid[i][j] != 0) {
6002 for(
int k = 0; k < grid[i][j]; k++) {
6008 for(
int i = 0; i < 51; i++) {
6009 for(
int j = 0; j < 51; j++) {
6010 if(grid_xz[i][j] != 0) {
6013 if(grid_yz[i][j] != 0) {
6018 return xy + yz + xz;
6049 default:
return false;
6056 pref_sum = vector<int>(nums.size());
6058 for(
int i = 1; i < nums.size(); i++) {
6068 if(nums.size() == 1) {
6071 vector<int> dp(nums.size());
6073 dp[1] = max(nums[0], nums[1]);
6074 for(
int i = 2; i < nums.size(); i++) {
6075 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
6077 return dp[nums.size() - 1];
6084 for(
int i = 1; i <
triangle.size(); i++) {
6085 for(
int j = 0; j <
triangle[i].size(); j++) {
6087 dp[i][j] = dp[i - 1][j] +
triangle[i][j];
6088 }
else if(j ==
triangle[i].size() - 1) {
6089 dp[i][j] = dp[i - 1][j - 1] +
triangle[i][j];
6091 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) +
triangle[i][j];
6095 int ans = dp.back()[0];
6096 for(
int i = 0; i < dp.back().size(); i++) {
6097 ans = min(ans, dp.back()[i]);
6105 auto *
const tnp =
new TreeNodeP(root->val);
6110 while(current !=
nullptr) {
6112 current = current->
parent;
6115 while(current !=
nullptr) {
6119 current = current->
parent;
6126 if(tn->
val == low) {
6128 }
else if(tn->
val == high) {
6131 if(tn->
left !=
nullptr) {
6136 if(tn->
right !=
nullptr) {
6149 vector<int> cpy =
nums;
6150 while(!cpy.empty()) {
6151 const int idx = rand() % cpy.size();
6152 ans.emplace_back(cpy[idx]);
6153 cpy.erase(cpy.begin() + idx);
6159 :
nums(
nums) { srand(time(
nullptr)); }
6165 unordered_map<char, int> um_p;
6169 unordered_map<char, int> um_s;
6170 for(
int i = 0; i < p.length(); i++) {
6174 ans.emplace_back(0);
6176 for(
int i = p.length(); i < s.length(); i++) {
6178 um_s[s[i - p.length()]]--;
6179 if(um_s[s[i - p.length()]] == 0) {
6180 um_s.erase(s[i - p.length()]);
6183 ans.emplace_back(i - p.length() + 1);
6195 for(
int j = 0; j < nums.size(); j++) {
6197 while(i <= j && prod >= k) {
6209 int r = nums.size() - 1;
6213 while(l >= 0 && l <= r) {
6214 if(nums[l] >= target) {
6217 while(l - 1 >= 0 && sum + nums[l - 1] < target) {
6226 ans = min(ans, r - l + 1);
6234 ans = min(ans, r - l + 1);
6236 }
while(sum >= target && r >= l);
6244 if(root ==
nullptr) {
6248 Node *prev_node = root;
6249 queue<pair<int, Node *>> q;
6250 if(root->left !=
nullptr) {
6251 q.emplace(1, root->left);
6253 if(root->right !=
nullptr) {
6254 q.emplace(1, root->right);
6257 auto [level, node] = q.front();
6259 if(level == prev_level) {
6260 prev_node->
next = node;
6264 if(node->left !=
nullptr) {
6265 q.emplace(level + 1, node->left);
6267 if(node->right !=
nullptr) {
6268 q.emplace(level + 1, node->right);
6277 if(root ==
nullptr) {
6280 queue<TreeNode *> q;
6283 auto *
const node = q.front();
6285 if(
equal(node, subRoot)) {
6288 if(node->left !=
nullptr) {
6291 if(node->right !=
nullptr) {
6292 q.push(node->right);
6299 if(
static_cast<int>(tn1 ==
nullptr) +
static_cast<int>(tn2 ==
nullptr) == 1) {
6302 if(tn1 ==
nullptr && tn2 ==
nullptr) {
6305 if(tn1->
val != tn2->
val) {
6308 if(
static_cast<int>(tn1->
left ==
nullptr) +
static_cast<int>(tn2->
left ==
nullptr) == 1) {
6311 if(
static_cast<int>(tn1->
right ==
nullptr) +
static_cast<int>(tn2->
right ==
nullptr) == 1) {
6320 int n = grid.size();
6321 auto levels = vector(n, vector(n, -1));
6322 auto cmp = [&n](
const tuple<int, int, int> &t1,
const tuple<int, int, int> &t2) {
6323 const auto &[level1, x1, y1] = t1;
6324 const auto &[level2, x2, y2] = t2;
6325 const int dx1 = abs(n - 1 - x1);
6326 const int dy1 = abs(n - 1 - y1);
6327 const int dx2 = abs(n - 1 - x2);
6328 const int dy2 = abs(n - 1 - y2);
6329 return level1 + dx1 + dy1 - min(dx1, dy1) > level2 + dx2 + dy2 - min(dx2, dy2);
6331 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
decltype(cmp)> pq(cmp);
6332 if(grid[0][0] == 0 && grid[n - 1][n - 1] == 0) {
6333 pq.push(make_tuple(1, 0, 0));
6337 while(!pq.empty()) {
6338 auto [level, x, y] = pq.top();
6339 if(x == n - 1 && y == n - 1) {
6343 if(levels[x][y] == -1 || levels[x][y] > level) {
6344 levels[x][y] = level;
6348 pair<int, int> nexts[8] = {make_pair(x - 1, y - 1), make_pair(x - 1, y), make_pair(x - 1, y + 1),
6349 make_pair(x, y - 1), make_pair(x, y + 1),
6350 make_pair(x + 1, y - 1), make_pair(x + 1, y), make_pair(x + 1, y + 1)};
6351 for(
auto [next_x, next_y]: nexts) {
6352 if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < n && grid[next_x][next_y] == 0 && (levels[next_x][next_y] == -1 || levels[next_x][next_y] > level + 1)) {
6353 pq.push(make_tuple(level + 1, next_x, next_y));
6363 const int m = board.size();
6364 const int n = board[0].size();
6365 for(
int i = 0; i < n; i++) {
6366 if(board[0][i] ==
'O') {
6369 if(board[m - 1][i] ==
'O') {
6370 dfs(board, m - 1, i);
6373 for(
int j = 0; j < m; j++) {
6374 if(board[j][0] ==
'O') {
6377 if(board[j][n - 1] ==
'O') {
6378 dfs(board, j, n - 1);
6381 for(
int i = 0; i < m; i++) {
6382 for(
int j = 0; j < n; j++) {
6383 if(board[i][j] ==
'O') {
6386 if(board[i][j] ==
'D') {
6395 const int m = board.size();
6396 const int n = board[0].size();
6397 pair<int, int> nexts[4] = {{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}};
6398 for(
auto [next_x, next_y]: nexts) {
6399 if(next_x >= 0 && next_x < m && next_y >= 0 && next_y < n && board[next_x][next_y] ==
'O') {
6400 dfs(board, next_x, next_y);
6408 vector<vector<int>> ans;
6410 for(
auto &path: ans) {
6412 path = vector(path.rbegin(), path.rend());
6417 int Solution::dfs(vector<vector<int>> &graph, vector<vector<int>> &ans,
int cur) {
6419 if(cur == graph.size() - 1) {
6420 ans.emplace_back(vector(1, cur));
6423 for(
const auto next: graph[cur]) {
6424 const int n =
dfs(graph, ans, next);
6426 for(
int i = ans.size() - 1, j = 0; j < n; i--, j++) {
6427 ans[i].emplace_back(cur);
6436 vector<vector<int>> ans;
6438 dfs(s, vector<int>(), nums);
6439 ans.reserve(s.size());
6440 for(
const auto &vec: s) {
6441 ans.emplace_back(vec);
6446 void Solution::dfs(set<vector<int>> &s,
const vector<int> ¤t, vector<int> rest) {
6451 for(
auto it = rest.begin(); it != rest.end(); ++it) {
6452 vector<int> next_current = current;
6453 vector<int> next_rest = rest;
6454 next_current.push_back(*it);
6455 next_rest.erase(next_rest.begin() + (it - rest.begin()));
6456 dfs(s, next_current, next_rest);
6463 sort(candidates.begin(), candidates.end());
6464 return recurse(candidates, target, 0);
6468 vector<vector<int>> ans;
6469 for(
int i = index; i < candidates.size(); i++) {
6470 auto &candidate = candidates[i];
6471 if(candidate == target) {
6472 ans.emplace_back(vector(1, candidate));
6473 }
else if(target - candidate >= 1) {
6474 auto res =
recurse(candidates, target - candidate, i);
6475 for(
auto &vec: res) {
6476 vec.push_back(candidate);
6487 sort(candidates.begin(), candidates.end());
6488 const auto ret =
recurse(candidates, target, -10);
6489 vector<vector<int>> ans(ret.size());
6490 for(
int i = 0; i < ret.size(); i++) {
6491 ans[i] = vector<int>(ret[i].size());
6492 for(
int j = 0; j < ret[i].size(); j++) {
6493 ans[i][j] = candidates[ret[i][j]];
6500 vector<vector<int>> ans;
6501 for(
int i = max(0, index + 1); i < candidates.size(); i++) {
6502 if(!(i > 0 && candidates[i] == candidates[i - 1] && index != i - 1)) {
6503 const auto &candidate = candidates[i];
6504 if(candidate == target) {
6505 ans.emplace_back(vector(1, i));
6506 }
else if(target - candidate >= 1) {
6507 auto res =
recurse(candidates, target - candidate, i);
6508 for(
auto &vec: res) {
6521 if(nums.size() == 1) {
6524 auto vec1 = vector(nums.begin(), nums.end() - 1);
6525 auto vec2 = vector(nums.begin() + 1, nums.end());
6532 vector can(nums.size(),
false);
6535 for(
int i = 0; i < nums.size(); i++) {
6536 if(can[i] && min(i + nums[i],
static_cast<int>(nums.size() - 1)) > last) {
6537 for(
int j = last + 1; j <= i + nums[i] && j < nums.size(); j++) {
6540 last = min(i + nums[i],
static_cast<int>(nums.size() - 1));
6549 const int n = nums.size();
6553 for(
int i = 0; i < n; i++) {
6554 if(i + nums[i] >= last) {
6567 vector dp(m, vector(n, 0));
6568 dp[m - 1][n - 1] = 1;
6569 for(
int i = m - 1; i >= 0; i--) {
6570 for(
int j = n - 1; j >= 0; j--) {
6572 dp[i][j] += dp[i + 1][j];
6575 dp[i][j] += dp[i][j + 1];
6585 const int n = s.size();
6593 vector dp(n, vector<int>(n));
6595 for(
int i = 0; i < n; i++) {
6600 for(
int L = 2; L <= n; L++) {
6602 for(
int i = 0; i < n; i++) {
6604 const int j = L + i - 1;
6616 dp[i][j] = dp[i + 1][j - 1];
6621 if(dp[i][j] != 0 && j - i + 1 > maxLen) {
6627 return s.substr(begin, maxLen);
6633 const int n = nums.size();
6634 vector<int> diff(n - 1);
6635 for(
int i = 0; i < n - 1; i++) {
6636 diff[i] = nums[i + 1] - nums[i];
6638 vector<int> consecutive;
6641 for(
int i = 0; i < n - 1; i++) {
6642 if(diff[i] == diff[prev]) {
6645 consecutive.emplace_back(cnt);
6650 consecutive.emplace_back(cnt);
6652 for(
const auto num: consecutive) {
6654 ans += (num - 1) * num / 2;
6663 vector dp(s.length(), 0);
6664 for(
int i = 0; i < dp.size(); i++) {
6666 if(
'1' <= s[i] && s[i] <=
'9') {
6667 dp[i] += i - 1 >= 0 ? dp[i - 1] : 1;
6670 if(i - 1 >= 0 && (s[i - 1] ==
'1' &&
'0' <= s[i] && s[i] <=
'9' || s[i - 1] ==
'2' &&
'0' <= s[i] && s[i] <=
'6')) {
6671 dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
6684 vector end(s.length(),
false);
6686 for(
const auto &word: wordDict) {
6690 for(
int i = 1; i < s.length(); i++) {
6703 for(; i < s.length(); i++) {
6704 node = node->
nexts[s[i] -
'a'];
6705 if(node ==
nullptr) {
6717 const int n = nums.size();
6720 for(
int i = 0; i < n; i++) {
6721 for(
int j = i + 1; j < n; j++) {
6722 if(nums[j] > nums[i]) {
6723 dp[j] = max(dp[j], dp[i] + 1);
6726 ans = max(ans, dp[i]);
6734 const int n = nums.size();
6735 vector dp(n, map<unsigned, unsigned>());
6736 for(
int i = 0; i < n; i++) {
6739 unsigned max_len = 1;
6740 for(
int i = 0; i < n; i++) {
6741 for(
int j = i + 1; j < n; j++) {
6742 auto &[len, cnt] = *dp[i].rbegin();
6743 if(nums[j] > nums[i]) {
6744 dp[j][len + 1] += cnt;
6745 max_len = max(max_len, len + 1);
6750 for(
int i = 0; i < n; i++) {
6751 ans += dp[i][max_len];
6759 vector dp(text1.length(), vector(text2.length(), 0));
6760 for(
int i = 0; i < text1.length(); i++) {
6761 for(
int j = 0; j < text2.length(); j++) {
6762 if(text1[i] == text2[j]) {
6763 dp[i][j] = (i - 1 < 0 || j - 1 < 0 ? 0 : dp[i - 1][j - 1]) + 1;
6765 dp[i][j] = max(i - 1 >= 0 ? dp[i - 1][j] : 0, j - 1 >= 0 ? dp[i][j - 1] : 0);
6769 return dp.back().back();
6776 return word1.length() + word2.length() - 2 * lcs;
6783 vector dp(word1.length() + 1, vector<int>(word2.length() + 1));
6785 for(
int j = 0; j <= word2.length(); j++) {
6788 for(
int i = 0; i <= word1.length(); i++) {
6791 for(
int i = 1; i <= word1.length(); i++) {
6792 for(
int j = 1; j <= word2.length(); j++) {
6793 if(word1[i - 1] == word2[j - 1]) {
6794 dp[i][j] = dp[i - 1][j - 1];
6796 dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
6800 return dp.back().back();
6806 vector dp(amount + 1, -1);
6808 for(
const auto &coin: coins) {
6809 if(coin <= amount) {
6813 for(
unsigned i = 0; i <= amount; i++) {
6815 for(
const auto &coin: coins) {
6816 if(i + coin <=
static_cast<unsigned>(amount)) {
6817 if(dp[i + coin] == -1) {
6818 dp[i + coin] = dp[i] + 1;
6820 dp[i + coin] = min(dp[i + coin], dp[i] + 1);
6833 vector<int> dp(n + 1);
6837 for(
int i = 3; i <= n; i++) {
6838 for(
int j = 1; j < i; j++) {
6839 dp[i] = max(dp[i], dp[j] * dp[i - j]);
6840 dp[i] = max(dp[i], j * dp[i - j]);
6841 dp[i] = max(dp[i], dp[j] * (i - j));
6842 dp[i] = max(dp[i], j * (i - j));
6852 for(
auto &p1: points) {
6853 unordered_map<long double, int> us;
6855 for(
auto &p2: points) {
6856 if(p2[0] != p1[0]) {
6857 us[
static_cast<long double>(p2[1] - p1[1]) /
static_cast<long double>(p2[0] - p1[0])]++;
6862 for(
auto &[k, v]: us) {
6863 cnt = max(cnt, v + 1);
6865 ans = max(ans, cnt);
6873 vector<string> strs_sorted = strs;
6874 unordered_map<string, vector<string>> um;
6875 for(
auto &str: strs_sorted) {
6876 sort(str.begin(), str.end());
6877 if(!um.contains(str)) {
6878 um[str] = vector<string>();
6881 for(
int i = 0; i < strs.size(); i++) {
6882 um[strs_sorted[i]].emplace_back(strs[i]);
6884 vector<vector<string>> ans;
6885 ans.reserve(um.size());
6886 for(
auto &[k, v]: um) {
6887 ans.emplace_back(v);
6902 const int pivot = nums[(l + r) / 2];
6904 while(nums[++lp] < pivot) {}
6905 while(nums[--rp] > pivot) {}
6907 swap(nums[lp], nums[rp]);
6911 qsort(nums, rp + 1, r);
6917 unordered_map<int, int> um;
6918 for(
auto num: nums) {
6921 vector<int> vec(um.size());
6923 for(
auto &[_, v]: um) {
6926 sort(vec.rbegin(), vec.rend());
6927 unordered_set<int> us;
6928 for(i = 0; i < k; i++) {
6932 for(
auto [num, v]: um) {
6933 if(us.contains(v)) {
6934 ans.emplace_back(num);
6943 sort(nums.rbegin(), nums.rend());
6950 vector<vector<int>> ans;
6951 auto comp = [](
const vector<int> &a,
const vector<int> &b) {
return a[0] < b[0]; };
6952 sort(intervals.begin(), intervals.end(), comp);
6953 int start = intervals[0][0];
6954 int end = intervals[0][1];
6955 for(
int i = 1; i < intervals.size(); i++) {
6956 if(intervals[i][0] <= end) {
6957 end = max(end, intervals[i][1]);
6959 ans.emplace_back(vector{start, end});
6960 start = intervals[i][0];
6961 end = intervals[i][1];
6964 ans.emplace_back(vector{start, end});
6972 bool Solution::search(
const vector<vector<int>> &matrix,
int target,
int x_start,
int x_end,
int y_start,
int y_end) {
6973 const int minimum = min(x_end - x_start, y_end - y_start);
6974 vector<int> diag1(minimum + 1);
6975 for(
int i = 0; i <= minimum; i++) {
6976 diag1[i] = matrix[x_start + i][y_start + i];
6978 const auto it = lower_bound(diag1.begin(), diag1.end(), target);
6979 const int x = x_start + it - diag1.begin();
6980 const int y = y_start + it - diag1.begin();
6981 if(it != diag1.end()) {
6985 if(it == diag1.begin()) {
6988 if(
search(matrix, target, x_start, x - 1, y, y_end)) {
6991 if(
search(matrix, target, x, x_end, y_start, y - 1)) {
6994 if(
search(matrix, target, x, x_end, y, y_end)) {
6998 if(x > x_end && y > y_end) {
7001 if(x > x_end &&
search(matrix, target, x_start, x_end, y, y_end)) {
7004 if(y > y_end &&
search(matrix, target, x, x_end, y_start, y_end)) {
7014 if(root ==
nullptr) {
7020 queue<TreeNode *> q;
7025 if(node ==
nullptr) {
7026 vec.emplace_back(
"null");
7029 vec.emplace_back(to_string(node->
val));
7031 q.push(node->
right);
7033 int end = vec.size() - 1;
7034 while(vec[end] ==
"null" && end > 0) {
7038 for(
int i = 1; i <= end; i++) {
7039 oss <<
',' << vec[i];
7050 data = data.substr(1, data.size() - 2);
7051 auto *
const str =
static_cast<char *
>(malloc((data.length() + 1) *
sizeof(
char)));
7052 memcpy(str, data.c_str(), (data.length() + 1) *
sizeof(
char));
7053 for(
const char *item = strtok(str,
","); item !=
nullptr; item = strtok(
nullptr,
",")) {
7054 vec.emplace_back(
string(item));
7056 queue<TreeNode **> q;
7057 auto *root =
new TreeNode(stoi(vec[0]));
7059 for(
const auto &str: vec) {
7060 auto *
const node = q.front();
7066 q.push(&(*node)->left);
7067 q.push(&(*node)->right);
7077 return tasks.size();
7081 unordered_map<char, int> task_cnt;
7082 unordered_map<char, int> processing;
7083 for(
char task: tasks) {
7087 bool finished =
true;
7089 for(
const auto &[task, cnt]: task_cnt) {
7093 if(processing[task] <= 0) {
7094 maximum = max(maximum, cnt);
7100 for(
auto &[task, rest]: processing) {
7103 for(
auto &[task, cnt]: task_cnt) {
7104 if(maximum == cnt && processing[task] <= 0) {
7106 processing[task] = n;
7117 arr = array<list<pair<int, int>>,
SZ>();
7118 for(
unsigned i = 0; i <
SZ; i++) {
7119 arr[i] = list<pair<int, int>>();
7124 const unsigned slot =
static_cast<unsigned>(key) %
SZ;
7125 for(
auto &[k, v]:
arr[slot]) {
7131 arr[slot].emplace_back(key, value);
7135 const unsigned slot =
static_cast<unsigned>(key) %
SZ;
7136 for(
auto &[k, v]:
arr[slot]) {
7145 const unsigned slot =
static_cast<unsigned>(key) %
SZ;
7146 for(
auto it =
arr[slot].begin(); it !=
arr[slot].end(); ++it) {
7147 if(it->first == key) {
7148 arr[slot].erase(it);
7157 vector ans(n, vector(n, 0));
7162 for(
int i = 0; i < n * n; i++) {
7182 if(flag && (nx < 0 || nx >= n || ny < 0 || ny >= n || ans[nx][ny] != 0)) {
7197 if(intervals.empty()) {
7201 sort(intervals.begin(), intervals.end(), [](
const auto &u,
const auto &v) { return u[1] < v[1]; });
7203 const int n = intervals.size();
7204 int right = intervals[0][1];
7206 for(
int i = 1; i < n; ++i) {
7207 if(intervals[i][0] >= right) {
7209 right = intervals[i][1];
7218 vector<int> left(nums.size());
7219 vector<int> right(nums.size());
7221 for(
int i = 0; i < left.size(); i++) {
7226 for(
int i = left.size() - 1; i >= 0; i--) {
7230 vector<int> ans(nums.size());
7231 for(
int i = 0; i < nums.size(); i++) {
7232 ans[i] = left[i] * right[i];
7240 unordered_map<int, int> um;
7244 for(
const auto &num: nums) {
7246 count += um[ps - k];
7255 unordered_map<char, unsigned> last;
7257 for(
int i = 0; i < s.length(); i++) {
7260 for(
int i = 0; i < s.length();) {
7261 unsigned last_pos = i;
7263 for(
int j = i; j <= last_pos; j++) {
7264 last_pos = max(last_pos, last[s[j]]);
7266 ans.emplace_back(last_pos - i + 1);
7275 vector<unsigned short> vec(s.length());
7276 for(
int i = 0; i < s.length(); i++) {
7293 if(s.length() < 10) {
7296 unordered_map<unsigned, string> um;
7297 unordered_map<unsigned, unsigned> cnt;
7298 for(
int i = 0; i < 10; i++) {
7302 um[hsv] = s.substr(0, 10);
7304 const unsigned f = 262144;
7305 for(
int i = 10; i < s.length(); i++) {
7306 hsv -= vec[i - 10] * f;
7309 um[hsv] = s.substr(i - 9, 10);
7313 for(
auto &[k, v]: um) {
7315 ans.emplace_back(v);
7334 for(
int i = 0; i < index && current !=
nullptr; i++) {
7335 current = current->
next;
7337 return current ==
nullptr ? -1 : current->
val;
7341 auto *
const node =
new ListNode(val);
7342 node->next =
head->next;
7350 auto *
const node =
new ListNode(val);
7360 auto *
const node =
new ListNode(val);
7362 for(
int i = 0; i < index - 1 && current !=
nullptr; i++) {
7363 current = current->
next;
7365 if(current ==
nullptr) {
7369 node->next = current->
next;
7370 current->
next = node;
7371 if(current ==
tail) {
7382 for(
int i = 0; i < index - 1 && current !=
nullptr; i++) {
7383 current = current->
next;
7385 if(current ==
nullptr) {
7388 const auto *
const p = current->
next;
7402 while(current->
right !=
nullptr) {
7404 current = current->
right;
7411 while(current->
left !=
nullptr) {
7413 current = current->
left;
7419 if(node->
right !=
nullptr) {
7422 node->
val = rmin->val;
7426 if(node->
left !=
nullptr) {
7429 node->
val = lmax->val;
7433 if(
prev !=
nullptr) {
7434 if(
prev->left !=
nullptr &&
prev->left->val == node->
val) {
7435 prev->left =
nullptr;
7436 }
else if(
prev->right !=
nullptr &&
prev->right->val == node->
val) {
7437 prev->right =
nullptr;
7446 if(root ==
nullptr) {
7450 while(current !=
nullptr && current->
val != key) {
7451 if(current->
val == key) {
7455 if(current->
val < key) {
7456 current = current->
right;
7458 current = current->
left;
7461 if(current ==
nullptr) {
7464 if(root->left ==
nullptr && root->right ==
nullptr) {
7474 unordered_set<int> us;
7475 for(
auto num: nums) {
7478 if(
missing(nums, nums.size() - 1) < k) {
7479 return nums[0] + k + nums.size() - 1;
7482 int r = nums.size() - 1;
7485 return nums[l] + k -
missing(nums, l);
7487 const int m = (l + r) / 2;
7490 }
else if(
missing(nums, m) >= k) {
7502 const int mid = (l + r) / 2;
7506 for(
int i = 0; i < mat.size(); i++) {
7507 for(
int j = mid - 1; j <= mid + 1; j++) {
7508 if(maximum <
get(mat, i, j)) {
7509 maximum =
get(mat, i, j);
7515 if(max_col == mid || l + 1 == r) {
7516 return {max_row, max_col};
7518 if(max_col == mid + 1) {
7527 if(i >= 0 && i < mat.size() && j >= 0 && j < mat[0].size()) {
7536 int l = sweetness[0];
7538 for(
auto s: sweetness) {
7544 return count(sweetness, r) == k + 1 ? r : l;
7546 const int m = (l + r) / 2;
7547 const int c =
count(sweetness, m);
7560 for(
const auto s: sweetness) {
7574 unordered_map<int, vector<int>> um;
7575 for(
int i = 0; i < colors.size(); i++) {
7576 um[colors[i]].emplace_back(i);
7578 for(
auto &[k, vec]: um) {
7579 sort(vec.begin(), vec.end());
7581 for(
auto &query: queries) {
7584 vector<int> &vec = um[c];
7585 auto g = lower_bound(vec.begin(), vec.end(), i, less());
7586 auto l = lower_bound(vec.rbegin(), vec.rend(), i, greater());
7587 if(g == vec.end() && l == vec.rend()) {
7588 ans.emplace_back(-1);
7589 }
else if(g == vec.end()) {
7590 ans.emplace_back(abs(*l - i));
7591 }
else if(l == vec.rend()) {
7592 ans.emplace_back(abs(*g - i));
7594 ans.emplace_back(min(abs(*l - i), abs(*g - i)));
7604 auto cmp = [](
const vector<int> &vec1,
const vector<int> &vec2) ->
bool {
7605 if(vec1[1] != vec2[1]) {
7606 return vec1[1] < vec2[1];
7608 return vec1[0] < vec2[0];
7610 sort(slots1.begin(), slots1.end(), cmp);
7611 sort(slots2.begin(), slots2.end(), cmp);
7612 for(
auto it1 = slots1.begin(), it2 = slots2.begin(); it1 != slots1.end() && it2 != slots2.end();) {
7613 pair<int, int> p =
merge(*it1, *it2);
7614 if(p.second - p.first >= duration) {
7615 return {p.first, p.first + duration};
7617 if(cmp(*it1, *it2)) {
7626 pair<int, int>
Solution::merge(
const vector<int> &vec1,
const vector<int> &vec2) {
return {max(vec1[0], vec2[0]), min(vec1[1], vec2[1])}; }
7631 int maximum = nums[0];
7632 int minimum = nums[0];
7633 for(
const auto &num: nums) {
7634 maximum = max(maximum, num);
7635 minimum = min(minimum, num);
7640 const int m = (l + r) / 2;
7642 if(c == m - l + 1) {
7644 }
else if(c > m - l + 1) {
7655 for(
const auto &num: nums) {
7656 if(l <= num && num <= r) {
7666 vector lmax(height.size(), 0);
7667 vector rmax(height.size(), 0);
7668 int maximum = height[0];
7669 for(
int i = 0; i < height.size(); i++) {
7670 maximum = max(maximum, height[i]);
7673 maximum = height.back();
7674 for(
int i = height.size() - 1; i >= 0; i--) {
7675 maximum = max(maximum, height[i]);
7679 for(
int i = 0; i < height.size(); i++) {
7680 ans += min(lmax[i], rmax[i]) - height[i];
7688 vector<vector<int>> ans;
7691 for(
int i1 = 0, i2 = 0; i1 < encoded1.size() && i2 < encoded2.size();) {
7692 const int len = min(encoded1[i1][1] - p1, encoded2[i2][1] - p2);
7693 const int v = encoded1[i1][0] * encoded2[i2][0];
7694 if(!ans.empty() && ans.back()[0] == v) {
7695 ans.back()[1] += len;
7697 vector vec = {v, len};
7698 ans.emplace_back(vec);
7702 if(p1 >= encoded1[i1][1]) {
7706 if(p2 >= encoded2[i2][1]) {
7717 unordered_map<char, int> um;
7718 for(
int i = 0; i < len; i++) {
7721 size_t ans = um.size();
7722 for(
int i = 0, j = len; j < s.length(); i++, j++) {
7728 ans = min(ans, um.size());
7737 const int mid = (l + r) / 2 + 1;
7757 const int mid = (l + r) / 2 + 1;
7772 int r = nums.size();
7774 const int mid = (l + r) / 2 + 1;
7790 for(
int i = 0; i < len; i++) {
7796 for(
int i = 0, j = len; j < nums.size(); i++, j++) {
7803 ans = min(ans, current);
7812 for(
int i = 0; i < k; i++) {
7816 for(
int i = 0, j = k; j < nums.size(); i++, j++) {
7817 ans.emplace_back(*ms.rbegin());
7818 ms.erase(ms.lower_bound(nums[i]));
7821 ans.emplace_back(*ms.rbegin());
7831 unordered_map<char, int> umt;
7832 unordered_map<char, int> ums;
7838 while(l <= r && r < s.length() && l < s.length()) {
7839 while(!
valid(ums, umt) && r + 1 < s.length()) {
7842 while(
valid(ums, umt) && l < s.length()) {
7844 if(r - l + 1 < ans.length()) {
7845 ans = s.substr(l, r - l + 1);
7852 if(r == s.length() - 1) {
7859 bool Solution::valid(unordered_map<char, int> &ums,
const unordered_map<char, int> &umt) {
7860 for(
const auto &[k, v]: umt) {
7861 if(!ums.contains(k) || ums[k] < v) {
7871 const int m = rooms.size();
7872 const int n = rooms[0].size();
7873 queue<tuple<int, int, int>> q;
7874 for(
int i = 0; i < m; i++) {
7875 for(
int j = 0; j < n; j++) {
7876 if(rooms[i][j] == 0) {
7882 auto [d, x, y] = q.front();
7884 pair<int, int> nexts[4] = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
7885 for(
auto &[next_x, next_y]: nexts) {
7886 if(next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && rooms[next_x][next_y] != -1 && rooms[next_x][next_y] != 0 && (rooms[next_x][next_y] == INT_MAX || rooms[next_x][next_y] > d + 1)) {
7887 rooms[next_x][next_y] = d + 1;
7888 q.push({d + 1, next_x, next_y});
7897 const int m = heights.size();
7898 const int n = heights[0].size();
7899 unordered_set<pair<int, int>,
myhash,
myeq> pacific;
7900 unordered_set<pair<int, int>,
myhash,
myeq> atlantic;
7901 queue<pair<int, int>> q;
7902 vector<vector<int>> ans;
7904 for(
int i = 0; i < m; i++) {
7906 pacific.insert({i, 0});
7908 for(
int i = 1; i < n; i++) {
7910 pacific.insert({0, i});
7913 auto [x, y] = q.front();
7915 pair<int, int> nexts[4] = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
7916 for(
auto &[next_x, next_y]: nexts) {
7917 if(next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && heights[next_x][next_y] >= heights[x][y] && !pacific.contains({next_x, next_y})) {
7918 pacific.insert({next_x, next_y});
7919 q.push({next_x, next_y});
7924 for(
int i = 0; i < m; i++) {
7926 atlantic.insert({i, n - 1});
7928 for(
int i = 0; i < n - 1; i++) {
7930 atlantic.insert({m - 1, i});
7933 auto [x, y] = q.front();
7935 pair<int, int> nexts[4] = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
7936 for(
auto &[next_x, next_y]: nexts) {
7937 if(next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && heights[next_x][next_y] >= heights[x][y] && !atlantic.contains({next_x, next_y})) {
7938 atlantic.insert({next_x, next_y});
7939 q.push({next_x, next_y});
7944 for(
const auto &p: atlantic) {
7945 if(pacific.contains(p)) {
7946 vector vec = {p.first, p.second};
7947 ans.emplace_back(vec);
7950 sort(ans.begin(), ans.end());
7954 bool myeq::operator()(
const pair<int, int> &p1,
const pair<int, int> &p2)
const {
return p1 == p2; }
7962 queue<TreeNode *> q;
7967 if(node->
left ==
nullptr && node->
right !=
nullptr) {
7968 ans.emplace_back(node->
right->
val);
7969 }
else if(node->
right ==
nullptr && node->
left !=
nullptr) {
7970 ans.emplace_back(node->
left->
val);
7972 if(node->
left !=
nullptr) {
7975 if(node->
right !=
nullptr) {
7976 q.push(node->
right);
7985 unordered_map<int, Node *> um;
7986 for(
const auto &v: pid) {
7987 um[v] =
new Node(v);
7989 for(
int i = 0; i < pid.size(); i++) {
7991 um[ppid[i]]->children.insert(um[pid[i]]);
7998 Node *node = q.front();
8000 ans.emplace_back(node->
val);
8012 return {target->
val};
8014 unordered_map<TreeNode *, Node *> um;
8016 queue<TreeNode *> q1;
8018 um[root] =
new Node(root->val);
8019 while(!q1.empty()) {
8022 if(tn->
left !=
nullptr) {
8025 um[tn->
left]->siblings.insert(um[tn]);
8026 um[tn]->siblings.insert(um[tn->left]);
8028 if(tn->
right !=
nullptr) {
8031 um[tn->
right]->siblings.insert(um[tn]);
8032 um[tn]->siblings.insert(um[tn->right]);
8035 Node *node = um[target];
8036 unordered_set<Node *> vis;
8037 queue<pair<int, Node *>> q2;
8039 while(!q2.empty()) {
8040 auto [d, nd] = q2.front();
8043 for(
auto *sibling: nd->siblings) {
8044 if(!vis.contains(sibling)) {
8045 vis.insert(sibling);
8047 ans.emplace_back(sibling->val);
8049 q2.push({d + 1, sibling});
8060 unordered_set<string> deads;
8061 unordered_set<string> vis;
8062 for(
auto &deadend: deadends) {
8063 deads.insert(deadend);
8065 auto get_nexts = [](
const string &code) {
8066 vector ans(8, code);
8067 ans[0][0] = (ans[0][0] -
'0' + 10 + 1) % 10 +
'0';
8068 ans[1][0] = (ans[1][0] -
'0' + 10 - 1) % 10 +
'0';
8069 ans[2][1] = (ans[2][1] -
'0' + 10 + 1) % 10 +
'0';
8070 ans[3][1] = (ans[3][1] -
'0' + 10 - 1) % 10 +
'0';
8071 ans[4][2] = (ans[4][2] -
'0' + 10 + 1) % 10 +
'0';
8072 ans[5][2] = (ans[5][2] -
'0' + 10 - 1) % 10 +
'0';
8073 ans[6][3] = (ans[6][3] -
'0' + 10 + 1) % 10 +
'0';
8074 ans[7][3] = (ans[7][3] -
'0' + 10 - 1) % 10 +
'0';
8077 queue<pair<int, string>> q;
8078 q.push({0,
"0000"});
8080 auto [step, code] = q.front();
8081 if(code == target) {
8086 if(deads.contains(code)) {
8089 auto nexts = get_nexts(code);
8090 for(
auto &next: nexts) {
8091 if(!vis.contains(next)) {
8093 if(next == target) {
8096 q.push({step + 1, next});
8106 vector<unordered_set<int>> g(n);
8107 for(
auto &connection: connections) {
8108 g[connection[0]].insert(connection[1]);
8109 g[connection[1]].insert(connection[0]);
8112 int free_edges_cnt = 0;
8113 unordered_set<int> vis;
8114 for(
int i = 0; i < n; i++) {
8115 if(!vis.contains(i)) {
8118 dfs(edge_cnt, node_cnt, vis, i, g);
8120 free_edges_cnt += edge_cnt / 2 - node_cnt + 1;
8123 if(free_edges_cnt < group_cnt - 1) {
8126 return group_cnt - 1;
8129 void Solution::dfs(
int &edge_cnt,
int &node_cnt, unordered_set<int> &vis,
int node, vector<unordered_set<int>> &g) {
8131 edge_cnt += g[node].size();
8133 for(
auto next: g[node]) {
8134 if(!vis.contains(next)) {
8135 dfs(edge_cnt, node_cnt, vis, next, g);
8143 const int m = grid.size();
8144 const int n = grid[0].size();
8145 vector g(m, vector<Node *>(n,
nullptr));
8146 for(
int i = 0; i < m; i++) {
8147 for(
int j = 0; j < n; j++) {
8148 g[i][j] =
new Node(i, j);
8151 for(
int i = 0; i < m; i++) {
8152 for(
int j = 0; j < n; j++) {
8153 pair<int, int> nexts[4] = {{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}};
8154 for(
auto [x, y]: nexts) {
8155 if(x >= 0 && x < m && y >= 0 && y < n) {
8156 g[i][j]->siblings.insert(make_pair(g[x][y], 1));
8161 switch(grid[i][j]) {
8175 if(x >= 0 && x < m && y >= 0 && y < n) {
8176 g[i][j]->siblings[g[x][y]] = 0;
8180 priority_queue<pair<int, Node *>, vector<pair<int, Node *>>,
mycmp> pq;
8181 unordered_set<Node *> vis;
8182 pq.push({0, g[0][0]});
8183 while(!pq.empty()) {
8184 auto [cost, node] = pq.top();
8186 if(vis.contains(node)) {
8190 if(node->x == m - 1 && node->y == n - 1) {
8193 for(
auto [sibling, c]: node->siblings) {
8194 if(!vis.contains(sibling)) {
8195 pq.push({cost + c, sibling});
8203 if(p1.first != p2.first) {
8204 return p1.first > p2.first;
8206 return p1.second->x + p1.second->y < p2.second->x + p2.second->y;
8212 vector<unordered_set<int>> g(n);
8213 for(
auto &conn: connections) {
8214 g[conn[0]].insert(conn[1]);
8215 g[conn[1]].insert(conn[0]);
8217 vector<vector<int>> ans;
8220 unordered_set<int> vis;
8222 for(
int i = 0; i < n; i++) {
8225 tarjan(-1, step, dfn, i, g, low, ans);
8231 void Solution::tarjan(
int prev,
int &step, vector<int> &dfn,
int node, vector<unordered_set<int>> &g, vector<int> &low, vector<vector<int>> &ans) {
8234 for(
const auto &next: g[node]) {
8235 if(dfn[next] == -1) {
8236 tarjan(node, ++step, dfn, next, g, low, ans);
8239 low[node] = min(low[node], low[next]);
8241 if(dfn[node] < low[next]) {
8242 ans.push_back({node, next});
8250 vector<vector<int>> ans;
8251 for(
int i = minimum; i <= sqrt(n); i++) {
8253 ans.push_back({i, n / i});
8255 for(
auto &vec: res) {
8257 ans.back().insert(ans.back().end(), vec.begin(), vec.end());
8271 vector<string> strs;
8272 while(i < s.length()) {
8273 if(isalpha(s[i]) != 0) {
8274 cnt.emplace_back(1);
8275 strs.emplace_back(
string(1, s[i]));
8277 }
else if(isdigit(s[i]) != 0) {
8279 while(j < s.length() && isdigit(s[j]) != 0) {
8282 cnt.emplace_back(stoi(s.substr(i, j - i)));
8289 }
else if(s[j] ==
']') {
8293 strs.emplace_back(
decodeString(s.substr(i + 1, j - i - 1)));
8298 for(i = 0; i < cnt.size(); i++) {
8299 for(
int j = 0; j < cnt[i]; j++) {
8309 vector<vector<string>> ans;
8310 const vector board(n, vector(n,
false));
8311 dfs(board, 0, n, ans);
8315 void Solution::dfs(
const vector<vector<bool>> &board,
int line,
int n, vector<vector<string>> &ans) {
8320 for(
int i = 0; i < n; i++) {
8321 if(
valid(board, n, line, i)) {
8322 vector<vector<bool>> next = board;
8323 next[line][i] =
true;
8324 dfs(next, line + 1, n, ans);
8330 for(
int i = 0; i < x; i++) {
8335 for(
int i = x, j = y; i >= 0 && i < n && j >= 0 && j < n; i--, j--) {
8340 for(
int i = x, j = y; i >= 0 && i < n && j >= 0 && j < n; i--, j++) {
8349 vector<string> ans(board.size());
8350 for(
int i = 0; i < board.size(); i++) {
8352 for(
int j = 0; j < board[i].size(); j++) {
8353 oss << (board[i][j] ?
'Q' :
'.');
8364 bool Solution::dfs(
const vector<vector<char>> &board, vector<vector<char>> &ans) {
8365 for(
int i = 0; i < 9; i++) {
8366 for(
int j = 0; j < 9; j++) {
8367 if(board[i][j] ==
'.') {
8368 for(
char c =
'1'; c <=
'9'; c++) {
8369 if(
valid(board, i, j, c)) {
8370 bool haveValid =
true;
8371 vector<vector<char>> next = board;
8373 if(
dfs(next, ans)) {
8387 for(
int i = 0; i < 9; i++) {
8388 if(board[i][y] == num) {
8392 for(
int j = 0; j < 9; j++) {
8393 if(board[x][j] == num) {
8397 for(
int i = 0; i < 3; i++) {
8398 for(
int j = 0; j < 3; j++) {
8399 if(board[x / 3 * 3 + i][y / 3 * 3 + j] == num) {
8412 if(pi == p.length() && si == s.length()) {
8415 if(pi == p.length()) {
8418 const char c = p[pi++];
8419 bool multiple =
false;
8420 if(pi < p.length() && p[pi] ==
'*') {
8425 if(si == s.length()) {
8428 if(c ==
'.' || s[si] == c) {
8429 return dfs(s, p, si + 1, pi);
8434 for(
int i = si; i <= s.length(); i++) {
8435 if(
dfs(s, p, i, pi)) {
8443 if(
dfs(s, p, ++i, pi)) {
8447 return dfs(s, p, si, pi);
8454 bool allDigit =
true;
8455 for(
int i = start; i <= end; i++) {
8456 if(!isdigit(expr[i])) {
8458 vector left =
eval(expr, start, i - 1);
8459 vector right =
eval(expr, i + 1, end);
8460 for(
const auto &l: left) {
8461 for(
const auto &r: right) {
8464 ans.emplace_back(l + r);
8467 ans.emplace_back(l - r);
8470 ans.emplace_back(l * r);
8479 for(
int i = start; i <= end; i++) {
8481 val += expr[i] -
'0';
8483 ans.emplace_back(val);
8489 vector ans =
eval(expression, 0, expression.length() - 1);
8490 sort(ans.begin(), ans.end());
8498 unordered_set<string> currSet;
8502 for(
auto &str: currSet) {
8504 ans.emplace_back(str);
8507 sort(ans.begin(), ans.end());
8510 unordered_set<string> nextSet;
8511 for(
auto &str: currSet) {
8512 for(
int i = 0; i < str.size(); i++) {
8513 if(i > 0 && str[i] == str[i - 1]) {
8516 if(str[i] ==
'(' || str[i] ==
')') {
8517 nextSet.insert(str.substr(0, i) + str.substr(i + 1, str.size()));
8528 for(
const char c: str) {
8531 }
else if(c ==
')') {
8545 if(nums1.size() > nums2.size()) {
8549 const int m = nums1.size();
8550 const int n = nums2.size();
8551 int left = 0, right = m;
8554 int median1 = 0, median2 = 0;
8556 while(left <= right) {
8559 const int i = (left + right) / 2;
8560 const int j = (m + n + 1) / 2 - i;
8563 int nums_im1 = i == 0 ? INT_MIN : nums1[i - 1];
8564 int nums_i = i == m ? INT_MAX : nums1[i];
8565 int nums_jm1 = j == 0 ? INT_MIN : nums2[j - 1];
8566 int nums_j = j == n ? INT_MAX : nums2[j];
8568 if(nums_im1 <= nums_j) {
8569 median1 = max(nums_im1, nums_jm1);
8570 median2 = min(nums_i, nums_j);
8577 return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
8583 vector<int> resultList;
8587 Init(nums.size() + 5);
8589 for(
int i =
static_cast<int>(nums.size()) - 1; i >= 0; --i) {
8590 const int id =
getId(nums[i]);
8591 resultList.push_back(
Query(
id - 1));
8595 reverse(resultList.begin(), resultList.end());
8605 while(pos <
c.size()) {
8623 a.assign(nums.begin(), nums.end());
8624 sort(
a.begin(),
a.end());
8625 a.erase(unique(
a.begin(),
a.end()),
a.end());
8633 if(prices.empty()) {
8637 const int n = prices.size();
8638 int f0 = -prices[0];
8641 for(
int i = 1; i < n; ++i) {
8642 tie(f0, f1, f2) = make_tuple(max(f0, f2 - prices[i]), f0 + prices[i], max(f1, f2));
8651 const int n = prices.size();
8652 vector<int> holding(n);
8653 vector<int> not_holding(n);
8655 holding[0] = -prices[0];
8656 for(
int i = 1; i < n; i++) {
8657 not_holding[i] = max(not_holding[i - 1], holding[i - 1] + prices[i] - fee);
8658 holding[i] = max(holding[i - 1], not_holding[i - 1] - prices[i]);
8660 return max(not_holding.back(), holding.back());
8668 for(
auto num: nums) {
8673 const int mid = (l + r) / 2;
8674 const int cnt =
get_m(nums, mid);
8677 }
else if(cnt > m) {
8679 }
else if(cnt < m) {
8689 for(
const auto num: nums) {
8690 if(c + num > msum) {
8706 return max(
dfs(
true, root),
dfs(
false, root));
8710 if(
um.contains({node, steal})) {
8711 return um[{node, steal}];
8713 int ans = steal ? node->
val : 0;
8714 if(node->
left !=
nullptr) {
8715 const int ns =
dfs(!steal, node->
left);
8716 const int s = !steal ?
dfs(steal, node->
left) : 0;
8719 if(node->
right !=
nullptr) {
8720 const int ns =
dfs(!steal, node->
right);
8721 const int s = !steal ?
dfs(steal, node->
right) : 0;
8724 um[{node, steal}] = ans;
8728 size_t myhash::operator()(
const pair<TreeNode *, bool> &p)
const {
return (uint64_t) p.first * 2 + (p.second ? 1 : 0); }
8730 bool myeq::operator()(
const pair<TreeNode *, bool> &p1,
const pair<TreeNode *, bool> &p2)
const {
return p1.first == p2.first && p1.second == p2.second; }
8735 const int m = matrix.size();
8736 const int n = matrix[0].size();
8737 vector horizontal_next_1s(m, vector(n, 0));
8738 vector vertical_next_1s(m, vector(n, 0));
8739 vector dp(m + 1, vector(n + 1, 0));
8740 for(
int i = 0; i < m; i++) {
8742 for(
int j = n - 1; j >= 0; j--) {
8743 if(matrix[i][j] ==
'1') {
8748 horizontal_next_1s[i][j] = cnt;
8751 for(
int j = 0; j < n; j++) {
8753 for(
int i = m - 1; i >= 0; i--) {
8754 if(matrix[i][j] ==
'1') {
8759 vertical_next_1s[i][j] = cnt;
8763 for(
int i = m - 1; i >= 0; i--) {
8764 for(
int j = n - 1; j >= 0; j--) {
8765 if(matrix[i][j] ==
'1') {
8766 dp[i][j] = min(min(vertical_next_1s[i][j], horizontal_next_1s[i][j]), 1 + dp[i + 1][j + 1]);
8767 ans = max(ans, dp[i][j]);
8777 const int m = matrix.size();
8781 const int n = matrix[0].size();
8782 vector left(m, vector(n, 0));
8784 for(
int i = 0; i < m; i++) {
8785 for(
int j = 0; j < n; j++) {
8786 if(matrix[i][j] ==
'1') {
8787 left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
8793 for(
int j = 0; j < n; j++) {
8795 vector<int> up(m, 0), down(m, 0);
8798 for(
int i = 0; i < m; i++) {
8799 while(!stk.empty() && left[stk.top()][j] >= left[i][j]) {
8802 up[i] = stk.empty() ? -1 : stk.top();
8806 for(
int i = m - 1; i >= 0; i--) {
8807 while(!stk.empty() && left[stk.top()][j] >= left[i][j]) {
8810 down[i] = stk.empty() ? m : stk.top();
8814 for(
int i = 0; i < m; i++) {
8815 const int height = down[i] - up[i] - 1;
8816 int area = height * left[i][j];
8817 ret = max(ret, area);
8826 const int length = nums.size();
8827 auto dp = vector<int>(length);
8828 for(
int i = 0; i < length; i++) {
8831 for(
int i = length - 2; i >= 0; i--) {
8832 for(
int j = i + 1; j < length; j++) {
8833 dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
8836 return dp[length - 1] >= 0;
8843 const vector<string> vec;
8844 vector<vector<string>> ans;
8845 dfs(vec, s, ans, 0, 0);
8850 for(
int i = start, j = end; i < j; i++, j--) {
8858 void Solution::dfs(
const vector<string> ¤t,
const string &s, vector<vector<string>> &ans,
int start,
int cursor) {
8859 if(cursor == s.length() - 1 &&
is_palindromic(s, start, cursor)) {
8860 ans.emplace_back(current);
8861 ans.back().emplace_back(s.substr(start, cursor - start + 1));
8864 if(cursor >= s.length() - 1 || start >= s.length()) {
8868 vector next = current;
8869 next.emplace_back(s.substr(start, cursor - start + 1));
8870 dfs(next, s, ans, cursor + 1, cursor + 1);
8872 dfs(current, s, ans, start, cursor + 1);
8878 vector is_palindromic(s.length(), vector(s.length(),
false));
8879 for(
int i = 0; i < s.length(); i++) {
8880 for(
int j = 0; i - j >= 0 && i + j < s.length() && s[i - j] == s[i + j]; j++) {
8881 is_palindromic[i - j][i + j] =
true;
8884 for(
int i = 0; i < s.length() - 1; i++) {
8885 if(s[i] == s[i + 1]) {
8886 for(
int j = 0; i - j >= 0 && i + 1 + j < s.length() && s[i - j] == s[i + 1 + j]; j++) {
8887 is_palindromic[i - j][i + 1 + j] =
true;
8891 vector dp(s.length(), 2000);
8893 for(
int j = 1; j < dp.size(); j++) {
8894 if(is_palindromic[0][j]) {
8898 for(
int i = j; i >= 0; i--) {
8899 if(is_palindromic[i][j]) {
8900 dp[j] = min(dp[j], dp[i - 1] + 1);
8910 const int n = nums.size();
8914 const int sum = accumulate(nums.begin(), nums.end(), 0);
8915 const int maxNum = *max_element(nums.begin(), nums.end());
8919 const int target = sum / 2;
8920 if(maxNum > target) {
8923 vector dp(n, vector(target + 1, 0));
8924 for(
int i = 0; i < n; i++) {
8927 dp[0][nums[0]] =
true;
8928 for(
int i = 1; i < n; i++) {
8929 const int num = nums[i];
8930 for(
int j = 1; j <= target; j++) {
8932 dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
8934 dp[i][j] = dp[i - 1][j];
8938 return dp[n - 1][target];
8944 unordered_set<int> us;
8946 for(
const auto &day: days) {
8948 end = max(end, day);
8950 vector dp(end + 1, 0);
8951 for(
int i = 1; i <= end; i++) {
8952 dp[i] = i - 1 >= 0 ? dp[i - 1] : 0;
8953 if(us.contains(i)) {
8955 dp[i] = min(dp[i], (i - 7 >= 0 ? dp[i - 7] : 0) + costs[1]);
8956 dp[i] = min(dp[i], (i - 30 >= 0 ? dp[i - 30] : 0) + costs[2]);
8965 vector dp(5, vector<long>(prices.size(), -10000000000));
8972 dp[1][0] = -prices[0];
8973 for(
int i = 1; i < prices.size(); i++) {
8974 dp[0][i] = dp[0][i - 1];
8975 dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] - prices[i]);
8976 dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + prices[i]);
8977 dp[3][i] = max(dp[3][i - 1], dp[2][i - 1] - prices[i]);
8978 dp[4][i] = max(dp[4][i - 1], dp[3][i - 1] + prices[i]);
8980 long ans = dp[0].back();
8981 for(
int i = 1; i <= 4; i++) {
8982 ans = max(ans, dp[i].back());
8990 const int n = dungeon.size(), m = dungeon[0].size();
8991 vector dp(n + 1, vector(m + 1, INT_MAX));
8992 dp[n][m - 1] = dp[n - 1][m] = 1;
8993 for(
int i = n - 1; i >= 0; --i) {
8994 for(
int j = m - 1; j >= 0; --j) {
8995 const int minn = min(dp[i + 1][j], dp[i][j + 1]);
8996 dp[i][j] = max(minn - dungeon[i][j], 1);
9005 vector<int> in(numCourses);
9006 vector<unordered_set<int>> out(numCourses);
9007 unordered_set<int> learned;
9008 for(
auto &prerequisite: prerequisites) {
9009 in[prerequisite[1]]++;
9010 out[prerequisite[0]].insert(prerequisite[1]);
9012 bool hasChange =
true;
9015 for(
int i = 0; i < numCourses; i++) {
9016 if(in[i] == 0 && !learned.contains(i)) {
9019 for(
auto &next: out[i]) {
9025 for(
int i = 0; i < numCourses; i++) {
9037 vector<int> in(numCourses);
9038 vector<unordered_set<int>> out(numCourses);
9039 unordered_set<int> learned;
9040 for(
auto &prerequisite: prerequisites) {
9041 in[prerequisite[0]]++;
9042 out[prerequisite[1]].insert(prerequisite[0]);
9044 bool hasChange =
true;
9047 for(
int i = 0; i < numCourses; i++) {
9048 if(in[i] == 0 && !learned.contains(i)) {
9051 ans.emplace_back(i);
9052 for(
auto &next: out[i]) {
9058 if(ans.size() == numCourses) {
9067 if(matrix.empty() || matrix[0].empty()) {
9070 rows = matrix.size();
9072 auto outdegrees = vector(
rows, vector<int>(
columns));
9073 for(
int i = 0; i <
rows; ++i) {
9074 for(
int j = 0; j <
columns; ++j) {
9075 for(
int k = 0; k < 4; ++k) {
9076 const int newRow = i +
dirs[k][0], newColumn = j +
dirs[k][1];
9077 if(newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn <
columns && matrix[newRow][newColumn] > matrix[i][j]) {
9083 queue<pair<int, int>> q;
9084 for(
int i = 0; i <
rows; ++i) {
9085 for(
int j = 0; j <
columns; ++j) {
9086 if(outdegrees[i][j] == 0) {
9094 const int size = q.size();
9095 for(
int i = 0; i < size; ++i) {
9096 const auto cell = q.front();
9098 const int row = cell.first, column = cell.second;
9099 for(
int k = 0; k < 4; ++k) {
9100 int newRow = row +
dirs[k][0], newColumn = column +
dirs[k][1];
9101 if(newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn <
columns && matrix[newRow][newColumn] < matrix[row][column]) {
9102 --outdegrees[newRow][newColumn];
9103 if(outdegrees[newRow][newColumn] == 0) {
9104 q.push({newRow, newColumn});
9116 vector<node *> nodes(n);
9117 for(
int i = 1; i <= n; i++) {
9118 nodes[i - 1] =
new node(i, 0);
9120 for(
const auto &relation: relations) {
9121 nodes[relation[1] - 1]->pred.insert(nodes[relation[0] - 1]);
9122 nodes[relation[0] - 1]->out++;
9125 unordered_set<int> vis;
9128 for(
int i = 0; i < n; i++) {
9129 if(nodes[i]->out == 0) {
9130 if(vis.contains(i)) {
9135 for(
node *next: nodes[i]->pred) {
9137 next->len = max(next->len, nodes[i]->len + 1);
9143 for(
int i = 0; i < n; i++) {
9144 if(nodes[i]->out != 0) {
9147 ans = max(ans, nodes[i]->len);
9155 unordered_map<char, unordered_set<char>> g;
9156 unordered_map<char, int> in;
9158 unordered_set<char> charset;
9159 for(
const auto &word: words) {
9160 for(
const auto &ch: word) {
9164 for(
const auto &ch: charset) {
9165 g[ch] = unordered_set<char>();
9169 for(
const auto &word: words) {
9170 max_len = max(max_len,
static_cast<int>(word.length()));
9172 for(
int i = 0; i < max_len; i++) {
9173 unordered_map<string, vector<string>> um;
9174 for(
const auto &word: words) {
9175 if(word.length() >= i) {
9176 um[i > 0 ? word.substr(0, i) :
""].emplace_back(word);
9179 for(
const auto &[pred, section]: um) {
9180 for(
int j = 0, k = 1; k < section.size(); j++, k++) {
9181 if(i < section[j].length() && i < section[k].length()) {
9182 if(section[j][i] != section[k][i]) {
9183 g[section[j][i]].insert(section[k][i]);
9185 }
else if(i < section[j].length()) {
9191 for(
const auto &[k, section]: g) {
9192 for(
const auto &n: section) {
9197 unordered_set<char> vis;
9200 for(
const auto &[ch, n]: in) {
9201 if(n == 0 && !vis.contains(ch)) {
9205 for(
const auto &nc: g[ch]) {
9211 for(
const auto &[ch, n]: in) {
9223 for(
const int num: nums) {
9227 const int lsb = xorsum == INT_MIN ? xorsum : xorsum & -xorsum;
9228 int type1 = 0, type2 = 0;
9229 for(
const int num: nums) {
9236 return {type1, type2};
9242 priority_queue<frame> pq;
9243 int m = grid.size();
9244 int n = grid[0].size();
9248 unordered_map<unsigned, vector<vector<int>>> min_step;
9249 for(
int i = 0; i < m; i++) {
9250 for(
int j = 0; j < n; j++) {
9251 if(grid[i][j] ==
START) {
9254 }
else if(isupper(grid[i][j])) {
9259 frame start(start_x, start_y, lock_cnt);
9261 while(!pq.empty()) {
9264 if(f.
keys.size() == lock_cnt) {
9267 if(!min_step.contains(f.
get_mask())) {
9268 min_step[f.
get_mask()] = vector(m, vector(n, INT_MAX));
9274 const pair<int, int> nexts[4] = {{f.
x + 1, f.
y}, {f.
x - 1, f.
y}, {f.
x, f.
y + 1}, {f.
x, f.
y - 1}};
9275 for(
const auto &[n_x, n_y]: nexts) {
9276 if(n_x >= 0 && n_x < m && n_y >= 0 && n_y < n && grid[n_x][n_y] !=
WALL) {
9277 if(islower(grid[n_x][n_y])) {
9282 next.
keys.insert(grid[n_x][n_y]);
9283 if(!min_step.contains(next.
get_mask())) {
9284 min_step[next.
get_mask()] = vector(m, vector(n, INT_MAX));
9289 }
else if(isupper(grid[n_x][n_y])) {
9290 if(f.
keys.contains(
static_cast<char>(tolower(grid[n_x][n_y])))) {
9295 if(!min_step.contains(next.
get_mask())) {
9296 min_step[next.
get_mask()] = vector(m, vector(n, INT_MAX));
9307 if(!min_step.contains(next.
get_mask())) {
9308 min_step[next.
get_mask()] = vector(m, vector(n, INT_MAX));
9324 return keys.size() < f.
keys.size();
9329 for(
const auto &key:
keys) {
9330 mask |= 1 << key -
'a';
9338 const int n = nums.size();
9339 int ans = 0, revCnt = 0;
9340 for(
int i = 0; i < n; ++i) {
9341 if(i >= k && nums[i - k] > 1) {
9345 if(nums[i] == revCnt) {
9364 for(
const auto t:
um[startStation][endStation]) {
9367 return static_cast<double>(total) /
um[startStation][endStation].size();
9376 if(
um.contains(key)) {
9377 if(key !=
keys.back()) {
9379 keys.emplace_back(key);
9388 if(
um.contains(key)) {
9390 if(key !=
keys.back()) {
9392 keys.emplace_back(key);
9398 keys.emplace_back(key);
9401 if(
um.contains(key)) {
9403 if(key !=
keys.back()) {
9405 keys.emplace_back(key);
9409 keys.emplace_back(key);
9417 void TimeMap::set(
const string &key,
string value,
int timestamp) {
um[key][timestamp] = std::move(value); }
9420 const auto it =
um[key].lower_bound(timestamp);
9421 return it ==
um[key].end() ?
"" : it->second;
9439 if(
um.contains(key)) {
9443 const auto it = find(
tnc[
cnt[key] - 1].begin(),
tnc[
cnt[key] - 1].end(), key);
9444 if(it !=
tnc[
cnt[key] - 1].end()) {
9445 tnc[
cnt[key] - 1].erase(it);
9446 if(
tnc[
cnt[key] - 1].empty()) {
9450 tnc[
cnt[key]].emplace_back(key);
9462 if(
um.contains(key)) {
9464 tnc[
cnt[key] - 1].erase(find(
tnc[
cnt[key] - 1].begin(),
tnc[
cnt[key] - 1].end(), key));
9465 if(
tnc[
cnt[key] - 1].empty()) {
9470 while(
tnc.begin()->second.empty()) {
9473 const auto evicted =
tnc.begin()->second.begin();
9474 const int val = *evicted;
9475 tnc.begin()->second.erase(evicted);
9481 if(
um.contains(key)) {
9483 tnc[
cnt[key] - 1].erase(find(
tnc[
cnt[key] - 1].begin(),
tnc[
cnt[key] - 1].end(), key));
9484 if(
tnc[
cnt[key] - 1].empty()) {
9491 tnc[
cnt[key]].emplace_back(key);
9498 if(
mem[i].contains(sum)) {
9501 if(i ==
vec.size() - 1) {
9505 for(
const auto &[k, v]:
vec[i]) {
9506 ans += v *
sumCount(sum - k, i + 1);
9513 mem = vector<unordered_map<int, int>>(4);
9514 vec = vector<unordered_map<int, int>>(4);
9515 for(
const auto &num: nums1) {
9518 for(
const auto &num: nums2) {
9521 for(
const auto &num: nums3) {
9524 for(
const auto &num: nums4) {
9533 auto pref_sum = vector(nums.size(), 0);
9534 pref_sum[0] = nums[0];
9535 unordered_map<int, set<int>> um;
9537 um[nums[0]].insert(0);
9538 for(
int i = 1; i < nums.size(); i++) {
9539 pref_sum[i] += nums[i] + pref_sum[i - 1];
9540 um[pref_sum[i]].insert(i);
9543 for(
int i = nums.size() - 1; i >= 0; i--) {
9544 const int r = pref_sum[i];
9546 if(!um[l].empty()) {
9547 ans = max(ans, i - *um[l].begin());
9556 auto one_count = vector(data.size(), 0);
9558 for(
int i = 0; i < one_count.size(); i++) {
9559 one_count[i] = cnt1 + data[i];
9560 cnt1 = one_count[i];
9565 int ans = cnt1 - one_count[cnt1 - 1];
9566 for(
int i = 0; i + cnt1 < one_count.size(); i++) {
9567 ans = min(ans, cnt1 - (one_count[i + cnt1] - one_count[i]));
LeetCode 5976. 检查是否每一行每一列都包含全部整数
LeetCode 5977. 最少交换次数来组合所有的 1 II
LeetCode 5978. 统计追加字母可以获得的单词数
LeetCode 1629. 按键持续时间最长的键
LeetCode 747. 至少是其他数字两倍的最大数
LeetCode 5980. 将字符串拆分为若干长度为 k 的组
LeetCode 5194. 得到目标值的最少行动次数
LeetCode 5983. 同时运行 N 台电脑的最长时间
LeetCode 1220. 统计元音字母序列的数目
LeetCode 5971. 打折购买糖果的最小开销
LeetCode 5973. 价格范围内最高排名的 K 样物品
LeetCode 5990. 找出数组中的所有孤独数字
LeetCode 5992. 基于陈述统计最多好人数
LeetCode 2045. 到达目的地的第二短时间
LeetCode 5981. 分组得分最高的所有下标
LeetCode 5994. 查找给定哈希值的子串
LeetCode 1342. 将数字变成 0 的操作次数
LeetCode 1414. 和为 K 的最少斐波那契数字数目
LeetCode 1725. 可以形成最大正方形的矩形数目
LeetCode 1219. Path with Maximum Gold
LeetCode 5984. 拆分数位后四位数字的最小和
LeetCode 5985. 根据给定数字划分数组
LeetCode 5987. 删除元素后和的最小差值
LeetCode 1405. Longest Happy String
LeetCode 1001. Grid Illumination
LeetCode 2006. Count Number of Pairs With Absolute Difference K
LeetCode 1447. Simplified Fractions
LeetCode 1984. Minimum Difference Between Highest and Lowest of K Scores
LeetCode 1020. Number of Enclaves
LeetCode 1189. “气球” 的最大数量
LeetCode 777. 在LR字符串中交换相邻字符
LeetCode 6005. 使数组变成交替数组的最少操作数
LeetCode 6006. 拿出最少数目的魔法豆
LeetCode 540. Single Element in a Sorted Array
LeetCode 1380. Lucky Numbers in a Matrix
LeetCode 1719. Number Of Ways To Reconstruct A Tree
LeetCode 1791. Find Center of Star Graph
LeetCode 688. Knight Probability in Chessboard
LeetCode 969. Pancake Sorting
LeetCode 5996. 统计数组中相等且可以被整除的数对
LeetCode 5997. 找到和为给定整数的三个连续整数
LeetCode 5998. 拆分成最多数目的偶整数之和
LeetCode 5999. 统计数组中好三元组数目
LeetCode 6012. 统计各位数字之和为偶数的整数个数
LeetCode 6014. 构造限制重复的字符串
LeetCode 6015. 统计可以被 K 整除的下标对数目
LeetCode 917. Reverse Only Letters
LeetCode 1706. Where Will the Ball Fall
LeetCode 537. Complex Number Multiplication
LeetCode 2016. Maximum Difference Between Increasing Elements
LeetCode 553. Optimal Division
LeetCode 6008. 统计包含给定前缀的字符串
LeetCode 6009. 使两字符串互为字母异位词的最少步骤数
LeetCode 1601. Maximum Number of Achievable Transfer Requests
LeetCode 6. ZigZag Conversion
LeetCode 564. Find the Closest Palindrome
LeetCode 2104. Sum of Subarray Ranges
LeetCode 521. Longest Uncommon Subsequence I
LeetCode 6024. 数组中紧跟 key 之后出现最频繁的数字
LeetCode 5217. 将杂乱无章的数字排序
LeetCode 5300. 有向无环图中一个节点的所有祖先
LeetCode 5237. 得到回文串的最少操作次数
LeetCode 6016. Excel 表中某个范围内的单元格
LeetCode 6017. 向数组中追加 K 个整数
LeetCode 6019. 替换数组中的非互质数
LeetCode 2100. Find Good Days to Rob the Bank
LeetCode 2055. Plates Between Candles
LeetCode 798. Smallest Rotation with Highest Score
LeetCode 589. N-ary Tree Preorder Traversal
LeetCode 2049. Count Nodes With the Highest Score
LeetCode 590. N-ary Tree Postorder Traversal
LeetCode 695. Max Area of Island
LeetCode 6031. 找出数组中的所有 K 近邻下标
LeetCode 5227. K 次操作后最大化顶端元素
LeetCode 6032. 得到要求路径的最小带权子图
LeetCode 393. UTF-8 Validation
LeetCode 599. Minimum Index Sum of Two Lists
LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets
LeetCode 432. All O`one Data Structure
LeetCode 720. Longest Word in Dictionary
LeetCode 2043. Simple Bank System
LeetCode 606. Construct String from Binary Tree
LeetCode 6021. Maximize Number of Subsequences in a String
LeetCode 6022. Minimum Operations to Halve Array Sum
LeetCode 6023. Minimum White Tiles After Covering With Carpets
LeetCode 6027. Count Hills and Valleys in an Array
LeetCode 6028. Count Collisions on a Road
LeetCode 6029. Maximum Points in an Archery Competition
LeetCode 2039. The Time When the Network Becomes Idle
LeetCode 653. Two Sum IV - Input is a BST
Remove Colored Pieces if Both Neighbors are the Same Color
K-th Smallest in Lexicographical Order
Factorial Trailing Zeroes
unsigned long long qmi(unsigned long long m, unsigned long long k)
Find Missing Observations
Binary Number with Alternating Bits
Maximize the Confusion of an Exam
Find Servers That Handled Most Number of Requests
Minimum Number of Operations to Convert Time
Find Players With Zero or One Losses
Maximum Candies Allocated to K Children
Range Sum Query - Mutable
Process Restricted Friend Requests
Prime Number of Set Bits in Binary Representation
N-ary Tree Level Order Traversal
Count Numbers with Unique Digits
Number of Lines To Write String
Insert Delete GetRandom O(1)
Projection Area of 3D Shapes
Range Sum Query - Immutable
Lowest Common Ancestor of a Binary Search Tree
Find All Anagrams in a String
Subarray Product Less Than K
Minimum Size Subarray Sum
Populating Next Right Pointers in Each Node II
Shortest Path in Binary Matrix
All Paths From Source to Target
Longest Palindromic Substring
Longest Increasing Subsequence
Number of Longest Increasing Subsequence
Longest Common Subsequence
Delete Operation for Two Strings
Kth Largest Element in an Array
Serialize and Deserialize Binary Tree
Non-overlapping Intervals
Product of Array Except Self
bool operator==(const TreeNode &) const
bool operator!=(const TreeNode &) const
static vector< string > findAllConcatenatedWordsInADict(vector< string > &)
bool dfs(TrieNode *, const string &, int, bool) const
void insert(const string &str)
static int titleToNumber(const string &columnTitle)
static string convertToTitle(int columnNumber)
int majorityElement(vector< int > &nums)
static int countQuadruplets(vector< int > &)
static bool isNStraightHand(vector< int > &hand, int groupSize)
static bool checkPerfectNumber(int num)
static void get_sum(FriendTreeNode *)
static TreeNode * convertBST(TreeNode *root)
static void convert(FriendTreeNode *)
static FriendTreeNode * copy(TreeNode *)
static vector< vector< int > > construct2DArray(vector< int > &original, int m, int n)
static int lastRemaining(int)
static bool checkString(const string &)
static int numberOfBeams(vector< string > &)
static int deviceCount(const string &)
static bool asteroidsDestroyed(int mass, vector< int > &asteroids)
static string dayOfTheWeek(int day, int month, int year)
int getResult(int mouse, int cat, int turns)
int dp[MAXN][MAXN][MAXN *2]
int catMouseGame(vector< vector< int > > &graph)
void getNextResult(int mouse, int cat, int turns)
vector< vector< int > > graph
static string modifyString(string s)
static string simplifyPath(const string &path)
static int maxDepth(const string &s)
static vector< int > grayCode(int n)
static bool checkValid(vector< vector< int > > &matrix)
static int minSwaps(vector< int > &nums)
static unsigned int str2bin(const string &)
static int wordCount(vector< string > &startWords, vector< string > &targetWords)
static char slowestKey(vector< int > &releaseTimes, string keysPressed)
static bool dfs(unsigned long long n1, unsigned long long n2, const char *, unsigned short length, unsigned short current)
static bool isAdditiveNumber(string num)
static unsigned long long str2ui(const char *, unsigned short start, unsigned short length)
将字符串的一个子串转换为整数
static bool equal(string, const char *, unsigned short start, unsigned short length)
判断一个字符串与另一个字符串的子串是否相等
static string decodeCiphertext(string encodedText, int rows)
static string rtrim(string &s)
去除字符串右边的空白符 https://blog.csdn.net/tiandyoin/article/details/81508445
bool operator==(const point &p) const
bool operator<(const point &p) const
size_t operator()(const point &p) const
static bool isEscapePossible(vector< vector< int > > &blocked, vector< int > &source, vector< int > &target)
static unsigned int search(unordered_set< point, point_hash > &block_set, point *source, point *target, unsigned int limit)
在迷宫中以source为起点搜索
static bool increasingTriplet(vector< int > &nums)
static int dominantIndex(vector< int > &nums)
bool operator<(const pair &) const
static vector< vector< int > > kSmallestPairs(vector< int > &nums1, vector< int > &nums2, int k)
static vector< vector< int > > permute(vector< int > &nums)
static int totalMoney(int n)
static vector< string > divideString(const string &s, int k, char fill)
static int minMoves(int target, int maxDoubles)
static long long mostPoints(vector< vector< int > > &questions)
static long long maxRunTime(int n, vector< int > &batteries)
static int countVowelPermutation(int n)
static int findMinDifference(vector< string > &timePoints)
static bool containsNearbyDuplicate(vector< int > &nums, int k)
static bool stoneGameIX(vector< int > &stones)
static int minJumps(vector< int > &arr)
static int removePalindromeSub(string s)
void insert(const string &str)
string get_prefix(string root, const string &str) const
static string replaceWords(vector< string > &dictionary, const string &sentence)
static int minimumCost(vector< int > &cost)
static int numberOfArrays(vector< int > &differences, int lower, int upper)
item(int distance, int price, int row, int col)
bool operator<(const item &) const
static vector< vector< int > > highestRankedKItems(vector< vector< int > > &grid, vector< int > &pricing, vector< int > &start, int k)
static int numberOfWays(string corridor)
static int countElements(vector< int > &nums)
static vector< int > rearrangeArray(vector< int > &nums)
static vector< int > findLonely(vector< int > &nums)
static int maximumGood(vector< vector< int > > &statements)
static pair< int, unordered_map< int, bool > > dfs(vector< vector< int > > &statements, unordered_map< int, bool > um, queue< msg > que)
void update(int timestamp, int price)
status(int position, int time)
bool operator<(const status &s) const
static int secondMinimum(int n, vector< vector< int > > &edges, int time, int change)
static int numberOfMatches(int n)
multiset< pair< int, int > > ms
void add(vector< int > point)
int count(vector< int > point) const
static int countValidWords(const string &sentence)
static int numberOfWeakCharacters(vector< vector< int > > &properties)
static bool patternMatching(const string &pattern, const string &value)
static vector< vector< int > > highestPeak(vector< vector< int > > &isWater)
static vector< string > uncommonFromSentences(const string &s1, const string &s2)
static int findFinalValue(vector< int > &nums, int original)
static vector< int > maxScoreIndices(vector< int > &nums)
static string subStrHash(string s, int power, int modulo, int k, int hashValue)
unordered_map< unsigned int, unsigned int > rank
unordered_map< unsigned int, unsigned int > size
unordered_map< unsigned int, unsigned int > parent
static unsigned int compress(const string &word)
void insert(unsigned int num)
vector< int > groupStrings(vector< string > &words)
void to_union(unsigned int x1, unsigned int x2)
unsigned int find(unsigned int x)
static int numberOfSteps(int num)
static string longestNiceSubstring(const string &s)
static pair< int, int > dfs(string s, int start, int end)
static string reversePrefix(string word, char ch)
static int findMinFibonacciNumbers(int k)
static int find_min(set< int, greater<> > &fibb, int k, set< int, greater<> >::iterator begin)
static int countGoodRectangles(vector< vector< int > > &rectangles)
static int get_sum(int current, int x, int y, int m, int n, vector< vector< int > > &grid, bool **occupied)
static int getMaximumGold(vector< vector< int > > &grid)
static int minimumSum(int num)
static vector< int > pivotArray(vector< int > &nums, int pivot)
static int get_cost(int startAt, int moveCost, int pushCost, const int num[4])
static int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds)
static long long minimumDifference(vector< int > &nums)
static int sumOfUnique(vector< int > &nums)
static vector< int > sortEvenOdd(vector< int > &nums)
static long long smallestNumber(long long num)
set< unsigned int > * zero0
Bitset(int size)
用 size 个位初始化 Bitset ,所有位都是 0 。
string toString() const
返回 Bitset 的当前组成情况。注意,在结果字符串中,第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。
bool one() const
检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件,返回 true ;否则,返回 false 。
void fix(int idx) const
将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ,则不会发生任何改变。
bool all() const
检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件,返回 true ;否则,返回 false 。
void flip()
翻转 Bitset 中每一位上的值。换句话说,所有值为 0 的位将会变成 1 ,反之亦然。
set< unsigned int > * one1
int count() const
返回 Bitset 中值为 1 的位的 总数 。
void unfix(int idx) const
将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ,则不会发生任何改变。
static int * get_p(char ch, int *a, int *b, int *c)
static void sort(char ch[3], int a, int b, int c)
static string longestDiverseString(int a, int b, int c)
unsigned long long operator()(const pair< int, int > &) const
static vector< int > gridIllumination(int n, vector< vector< int > > &lamps, vector< vector< int > > &queries)
static int countKDifference(vector< int > &nums, int k)
static vector< string > simplifiedFractions(int n)
static int gcd(int m, int n)
static int minimumDifference(vector< int > &nums, int k)
static int numEnclaves(vector< vector< int > > &grid)
static int maxNumberOfBalloons(const string &text)
static bool canTransform(const string &start, const string &end)
static int countOperations(int num1, int num2)
static int minimumOperations(vector< int > &nums)
static long long minimumRemoval(vector< int > &beans)
static int maximumANDSum(vector< int > &nums, int numSlots)
static int singleNonDuplicate(vector< int > &nums)
static vector< int > luckyNumbers(vector< vector< int > > &matrix)
static int checkWays(vector< vector< int > > &pairs)
static int findCenter(vector< vector< int > > &edges)
unsigned int operator()(const status &) const
bool operator()(const status &, const status &) const
unordered_map< status, double, status_hash, status_equal > um
double knightProbability(int n, int k, int row, int column)
static vector< int > pancakeSort(vector< int > &arr)
static int countPairs(vector< int > &nums, int k)
static vector< long long > sumOfThree(long long num)
static vector< long long > maximumEvenSplit(long long finalSum)
void update(int idx, T delta)
static long long goodTriplets(vector< int > &nums1, vector< int > &nums2)
static int countEven(int num)
static ListNode * mergeNodes(ListNode *head)
static string repeatLimitedString(const string &s, int repeatLimit)
static long long coutPairs(vector< int > &nums, int k)
static bool isOneBitCharacter(vector< int > &bits)
static int longestMountain(vector< int > &arr)
static string pushDominoes(string dominoes)
static int numberOfGoodSubsets(vector< int > &nums)
static constexpr int mask_max
static constexpr int num_max
static constexpr array< int, 10 > primes
static string reverseOnlyLetters(string s)
static vector< int > findBall(vector< vector< int > > &grid)
static string complexNumberMultiply(const string &num1, const string &num2)
static int maximumDifference(vector< int > &nums)
static string optimalDivision(vector< int > &nums)
static int prefixCount(vector< string > &words, string pref)
static int minSteps(const string &s, const string &t)
static long long minimumTime(vector< int > &time, int totalTrips)
static int minimumFinishTime(vector< vector< int > > &tires, int changeTime, int numLaps)
static int maximumRequests(int n, vector< vector< int > > &requests)
static string convert(string s, int numRows)
static string nearestPalindromic(const string &n)
static int addDigits(int num)
static long long subArrayRanges(vector< int > &nums)
static int findLUSlength(const string &a, const string &b)
static int mostFrequent(vector< int > &nums, int key)
static vector< int > sortJumbled(vector< int > &mapping, vector< int > &nums)
unordered_map< int, unordered_set< int > > nexts
void dfs(bool *dfsd, int v, int i)
vector< vector< int > > getAncestors(int n, vector< vector< int > > &edges)
unordered_map< int, set< int > > ancestors
static int minMovesToMakePalindrome(string s)
static vector< string > cellsInRange(const string &s)
static long long minimalKSum(vector< int > &nums, int k)
static TreeNode * createBinaryTree(vector< vector< int > > &descriptions)
static vector< int > replaceNonCoprimes(vector< int > &nums)
static vector< int > goodDaysToRobBank(vector< int > &security, int time)
static string convertToBase7(int num)
static vector< int > platesBetweenCandles(string s, vector< vector< int > > &queries)
static int bestRotation(vector< int > &nums)
static vector< int > preorder(Node *root)
TreeNode * get_parent() const
void add_child(TreeNode *node)
const vector< TreeNode * > & get_children() const
vector< TreeNode * > children
static int countHighestScoreNodes(vector< int > &parents)
static vector< int > postorder(Node *root)
unordered_map< pair< int, int >, int, function< unsigned int(const pair< int, int > &)> > size
unordered_map< pair< int, int >, int, function< unsigned int(const pair< int, int > &)> > rank
bool same(pair< int, int > a, pair< int, int > b)
int get_size(pair< int, int > p)
void merge(pair< int, int > a, pair< int, int > b)
bool contains(pair< int, int > p) const
unordered_map< pair< int, int >, pair< int, int >, function< unsigned int(const pair< int, int > &)> > parent
pair< int, int > find(pair< int, int > val)
static int maxAreaOfIsland(vector< vector< int > > &grid)
static vector< int > findKDistantIndices(vector< int > &nums, int key, int k)
static int digArtifacts(int n, vector< vector< int > > &artifacts, vector< vector< int > > &dig)
static int maximumTop(vector< int > &nums, int k)
static void calc_dist(int s, vector< pair< int, int > > *graph, vector< long long int > &dist)
static long long minimumWeight(int n, vector< vector< int > > &edges, int src1, int src2, int dest)
static bool validUtf8(vector< int > &data)
static vector< string > findRestaurant(vector< string > &list1, vector< string > &list2)
static int countMaxOrSubsets(vector< int > &nums)
static int dfs(int current, int target, vector< int > nums)
AllOne()
Initializes the object of the data structure.
string getMaxKey()
Returns one of the keys with the maximal count.
string getMinKey()
Returns one of the keys with the minimum count.
map< int, unordered_set< string > > count_str
void dec(const string &key)
Decrements the count of the string key by 1. If the count of key is 0 after the decrement,...
unordered_map< string, int > str_count
void inc(const string &key)
Increments the count of the string key by 1. If key does not exist in the data structure,...
static string longestWord(vector< string > &words)
static string dfs(const string &str, TrieNode *node)
bool transfer(int account1, int account2, long long money)
Transfers money dollars from the account numbered account1 to the account numbered account2.
bool withdraw(int account, long long money)
Withdraw money dollars from the account numbered account.
bool deposit(int account, long long money)
Deposit money dollars into the account numbered account.
Bank(vector< long long > &balance)
Initializes the object with the 0-indexed integer array balance.
unordered_map< int, long long > accounts
static string tree2str(TreeNode *root)
static long long maximumSubsequenceCount(string text, string pattern)
static int halveArray(vector< int > &nums)
static int minimumWhiteTiles(string floor, int numCarpets, int carpetLen)
static int countHillValley(vector< int > &nums)
static int countCollisions(const string &directions)
static vector< int > maximumBobPoints(int numArrows, vector< int > &aliceArrows)
unordered_set< int > linked
static int networkBecomesIdle(vector< vector< int > > &edges, vector< int > &patience)
static bool findTarget(TreeNode *root, int k)
static bool winnerOfGame(string colors)
static int findKthNumber(int n, int k)
static int getSteps(int curr, long n)
static vector< vector< int > > imageSmoother(vector< vector< int > > &img)
static int trailingZeroes(int n)
static int calPoints(vector< string > &ops)
static int minDeletion(vector< int > &nums)
static vector< long long > kthPalindrome(vector< int > &queries, int intLength)
static vector< int > missingRolls(vector< int > &rolls, int mean, int n)
static bool hasAlternatingBits(int n)
static int maxConsecutiveAnswers(string answerKey, int k)
bool operator<(const event &e) const
static vector< int > busiestServers(int k, vector< int > &arrival, vector< int > &load)
static vector< int > selfDividingNumbers(int left, int right)
static bool canReorderDoubled(vector< int > &arr)
static int strongPasswordChecker(const string &password)
static long long numberOfWays(string s)
static long long sumScores(string s)
static int convertTime(string current, string correct)
static vector< vector< int > > findWinners(vector< vector< int > > &matches)
static int maximumCandies(vector< int > &candies, long long k)
Encrypter(vector< char > &keys, vector< string > &values, vector< string > &dictionary)
用 keys、values 和 dictionary 初始化 Encrypter 类。
int decrypt(const string &word2)
统计可以由 word2 解密得到且出现在 dictionary 中的字符串数目
string encrypt(const string &word1) const
按上述加密过程完成对 word1 的加密
unordered_map< string, int > count
NumArray(vector< int > &nums)
Initializes the object with the integer array nums.
void update(int index, int val)
Updates the value of nums[index] to be val.
int sumRange(int left, int right) const
Returns the sum of the elements of nums between indices left and right inclusive (i....
static vector< bool > friendRequests(int n, vector< vector< int > > &restrictions, vector< vector< int > > &requests)
static int countPrimeSetBits(int left, int right)
static vector< int > findMinHeightTrees(int n, vector< vector< int > > &edges)
static int findLongestNode(int u, vector< int > &parent, vector< vector< int > > &adj)
static bool rotateString(string s, const string &goal)
static vector< vector< int > > levelOrder(Node *root)
static bool reachingPoints(int sx, int sy, int tx, int ty)
static int maximumProduct(vector< int > &nums, int k)
static long long maximumBeauty(vector< int > &flowers, long long newFlowers, int target, int full, int partial)
static int countNumbersWithUniqueDigits(int n)
static vector< int > numberOfLines(vector< int > &widths, string s)
static bool checkInclusion(const string &s1, string s2)
int getRandom()
Returns a random element from the current set of elements (it's guaranteed that at least one element ...
bool insert(int val)
Inserts an item val into the set if not present.
unordered_map< int, int > map
RandomizedSet()
Initializes the RandomizedSet object.
bool remove(int val)
Removes an item val from the set if present.
uniform_int_distribution< int > distribution
default_random_engine generator
static int projectionArea(vector< vector< int > > &grid)
int medium
The number of slots for medium parking space
ParkingSystem(int big, int medium, int small)
Initializes object of the ParkingSystem class.
int big
The number of slots for big parking space
bool addCar(int carType)
Checks whether there is a parking space of carType for the car that wants to get into the parking lot...
int small
The number of slots for small parking space
NumArray(vector< int > &nums)
Initializes the object with the integer array nums.
int sumRange(int left, int right) const
Returns the sum of the elements of nums between indices left and right inclusive (i....
static int rob(vector< int > &nums)
static int minimumTotal(vector< vector< int > > &triangle)
static TreeNode * lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
static void copy(TreeNode *tn, TreeNodeP *tnp, int low, int high, TreeNodeP **p, TreeNodeP **q)
vector< int > shuffle() const
Returns a random shuffling of the array.
Solution(vector< int > &nums)
Initializes the object with the integer array nums.
vector< int > reset()
Resets the array to its original configuration and returns it.
static vector< int > findAnagrams(string s, const string &p)
static int numSubarrayProductLessThanK(vector< int > &nums, int k)
static int minSubArrayLen(int target, vector< int > &nums)
static Node * connect(Node *root)
static bool isSubtree(TreeNode *root, TreeNode *subRoot)
static bool equal(TreeNode *tn1, TreeNode *tn2)
static int shortestPathBinaryMatrix(vector< vector< int > > &grid)
static void solve(vector< vector< char > > &board)
static void dfs(vector< vector< char > > &board, int x, int y)
static int dfs(vector< vector< int > > &graph, vector< vector< int > > &ans, int cur)
static vector< vector< int > > allPathsSourceTarget(vector< vector< int > > &graph)
static vector< vector< int > > permuteUnique(vector< int > &nums)
static void dfs(set< vector< int > > &s, const vector< int > ¤t, vector< int > rest)
static vector< vector< int > > combinationSum(vector< int > &candidates, int target)
static vector< vector< int > > recurse(vector< int > &candidates, int target, int index)
static vector< vector< int > > combinationSum2(vector< int > &candidates, int target)
static vector< vector< int > > recurse(vector< int > &candidates, int target, int index)
static int rob(vector< int > &nums)
static bool canJump(vector< int > &nums)
static int jump(vector< int > &nums)
static int uniquePaths(int m, int n)
static string longestPalindrome(string s)
static int numberOfArithmeticSlices(vector< int > &nums)
static int numDecodings(string s)
static void search(const TrieNode *tn, const string &s, int i, vector< bool > &end)
static bool wordBreak(const string &s, vector< string > &wordDict)
static int lengthOfLIS(vector< int > &nums)
static int findNumberOfLIS(vector< int > &nums)
static int longestCommonSubsequence(string text1, string text2)
static int minDistance(const string &word1, const string &word2)
static int minDistance(string word1, string word2)
static int coinChange(vector< int > &coins, int amount)
static int integerBreak(int n)
static int maxPoints(vector< vector< int > > &points)
static vector< vector< string > > groupAnagrams(vector< string > &strs)
static void qsort(vector< int > &nums, int l, int r)
static void sortColors(vector< int > &nums)
static vector< int > topKFrequent(vector< int > &nums, int k)
static int findKthLargest(vector< int > &nums, int k)
static vector< vector< int > > merge(vector< vector< int > > &intervals)
static bool searchMatrix(vector< vector< int > > &matrix, int target)
static bool search(const vector< vector< int > > &matrix, int target, int x_start, int x_end, int y_start, int y_end)
static TreeNode * deserialize(string data)
Decodes your encoded data to tree.
static string serialize(TreeNode *root)
Encodes a tree to a single string.
static int leastInterval(vector< char > &tasks, int n)
MyHashMap()
initializes the object with an empty map.
void put(int key, int value)
inserts a (key, value) pair into the HashMap. If the key already exists in the map,...
void remove(int key)
removes the key and its corresponding value if the map contains the mapping for the key.
array< list< pair< int, int > >, SZ > arr
static vector< vector< int > > generateMatrix(int n)
static int eraseOverlapIntervals(vector< vector< int > > &intervals)
static vector< int > productExceptSelf(vector< int > &nums)
static int subarraySum(vector< int > &nums, int k)
static vector< int > partitionLabels(string s)
static vector< string > findRepeatedDnaSequences(string s)
int get(int index) const
Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void deleteAtIndex(int index)
Delete the indexth node in the linked list, if the index is valid.
void addAtHead(int val)
Add a node of value val before the first element of the linked list. After the insertion,...
void addAtTail(int val)
Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val)
Add a node of value val before the indexth node in the linked list. If index equals the length of the...
MyLinkedList()
Initializes the MyLinkedList object.
TreeNode * deleteNode(TreeNode *root, int key)
TreeNode * findMinimum(TreeNode *node)
TreeNode * findMaximum(TreeNode *node)
void remove(TreeNode *node)
static unsigned missing(vector< int > &nums, int i)
static int missingElement(vector< int > &nums, int k)
static vector< int > findPeakGridLR(vector< vector< int > > &mat, int l, int r)
static int get(vector< vector< int > > &mat, int i, int j)
static vector< int > findPeakGrid(vector< vector< int > > &mat)
static int count(vector< int > &sweetness, int x)
static int maximizeSweetness(vector< int > &sweetness, int k)
static vector< int > shortestDistanceColor(vector< int > &colors, vector< vector< int > > &queries)
static vector< int > minAvailableDuration(vector< vector< int > > &slots1, vector< vector< int > > &slots2, int duration)
static pair< int, int > merge(const vector< int > &vec1, const vector< int > &vec2)
static int countInRange(vector< int > &nums, int l, int r)
static int findDuplicate(vector< int > &nums)
static int trap(vector< int > &height)
static vector< vector< int > > findRLEArray(vector< vector< int > > &encoded1, vector< vector< int > > &encoded2)
static int getMinUniqueCharCnt(const string &s, int len)
static int lengthOfLongestSubstringTwoDistinct(const string &s)
static int lengthOfLongestSubstringKDistinct(const string &s, int k)
static int cntMinFlip(vector< int > &nums, int len)
static int longestOnes(vector< int > &nums, int k)
static vector< int > maxSlidingWindow(vector< int > &nums, int k)
static string minWindow(string s, const string &t)
static bool valid(unordered_map< char, int > &ums, const unordered_map< char, int > &umt)
static void wallsAndGates(vector< vector< int > > &rooms)
size_t operator()(const pair< int, int > &p) const
bool operator()(const pair< int, int > &p1, const pair< int, int > &p2) const
static vector< vector< int > > pacificAtlantic(vector< vector< int > > &heights)
static vector< int > getLonelyNodes(TreeNode *root)
unordered_set< Node * > children
static vector< int > killProcess(vector< int > &pid, vector< int > &ppid, int kill)
static vector< int > distanceK(TreeNode *root, TreeNode *target, int k)
static int openLock(vector< string > &deadends, const string &target)
static int makeConnected(int n, vector< vector< int > > &connections)
static void dfs(int &edge_cnt, int &node_cnt, unordered_set< int > &vis, int node, vector< unordered_set< int > > &g)
bool operator()(const pair< int, Node * > &p1, const pair< int, Node * > &p2) const
static int minCost(vector< vector< int > > &grid)
static void tarjan(int prev, int &step, vector< int > &dfn, int node, vector< unordered_set< int > > &g, vector< int > &low, vector< vector< int > > &ans)
static vector< vector< int > > criticalConnections(int n, vector< vector< int > > &connections)
static vector< vector< int > > getFactorsWithMin(int n, int minimum)
static vector< vector< int > > getFactors(int n)
static string decodeString(string s)
static bool valid(const vector< vector< bool > > &board, int n, int x, int y)
static vector< string > toStringVec(const vector< vector< bool > > &board)
static void dfs(const vector< vector< bool > > &board, int line, int n, vector< vector< string > > &ans)
static vector< vector< string > > solveNQueens(int n)
static bool valid(const vector< vector< char > > &board, int x, int y, char num)
static bool dfs(const vector< vector< char > > &board, vector< vector< char > > &ans)
static void solveSudoku(vector< vector< char > > &board)
static bool isMatch(const string &s, const string &p)
static bool dfs(const string &s, const string &p, int si, int pi)
static vector< int > diffWaysToCompute(const string &expression)
static vector< int > eval(const string &expr, int start, int end)
static bool isValid(const string &str)
static vector< string > removeInvalidParentheses(const string &s)
static double findMedianSortedArrays(vector< int > &nums1, vector< int > &nums2)
vector< int > countSmaller(vector< int > &nums)
void Discretization(vector< int > &nums)
static int maxProfit(vector< int > &prices)
static int maxProfit(vector< int > &prices, int fee)
static int get_m(const vector< int > &nums, int msum)
static int splitArray(vector< int > &nums, int m)
size_t operator()(const pair< TreeNode *, bool > &p) const
bool operator()(const pair< TreeNode *, bool > &p1, const pair< TreeNode *, bool > &p2) const
int dfs(bool steal, TreeNode *node)
unordered_map< pair< TreeNode *, bool >, int, myhash, myeq > um
static int maximalSquare(vector< vector< char > > &matrix)
static int maximalRectangle(vector< vector< char > > &matrix)
static bool PredictTheWinner(vector< int > &nums)
static vector< vector< string > > partition(const string &s)
static void dfs(const vector< string > ¤t, const string &s, vector< vector< string > > &ans, int start, int cursor)
static bool is_palindromic(const string &s, int start, int end)
static int minCut(string s)
static bool canPartition(vector< int > &nums)
static int mincostTickets(vector< int > &days, vector< int > &costs)
static int maxProfit(vector< int > &prices)
static int calculateMinimumHP(vector< vector< int > > &dungeon)
static bool canFinish(int numCourses, vector< vector< int > > &prerequisites)
static vector< int > findOrder(int numCourses, vector< vector< int > > &prerequisites)
int longestIncreasingPath(vector< vector< int > > &matrix)
static constexpr int dirs[4][2]
static int minimumSemesters(int n, vector< vector< int > > &relations)
static string alienOrder(vector< string > &words)
static vector< int > singleNumber(vector< int > &nums)
unsigned get_mask() const
frame(int x, int y, int lock_left)
unordered_set< char > keys
bool operator<(const frame &f) const
static int shortestPathAllKeys(vector< string > &grid)
static int minKBitFlips(vector< int > &nums, int k)
unordered_map< string, unordered_map< string, vector< int > > > um
unordered_map< int, pair< string, int > > records
void checkOut(int id, const string &stationName, int t)
通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站离开
double getAverageTime(const string &startStation, const string &endStation)
平均时间会根据截至目前所有从 startStation 站 直接 到达 endStation 站的行程进行计算,也就是从 startStation 站进入并从 endStation 离开的行程 从 st...
void checkIn(int id, const string &stationName, int t)
通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站进入 乘客一次只能从一个站进入
void put(int key, int value)
如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
LRUCache(int capacity)
以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key)
如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
unordered_map< int, int > um
string get(const string &key, int timestamp)
返回先前调用 set(key, value, timestamp_prev) 所存储的值,其中 timestamp_prev <= timestamp 。
unordered_map< string, map< int, string, greater< int > > > um
void set(const string &key, string value, int timestamp)
存储键 key、值 value,以及给定的时间戳 timestamp。
void removeRange(int left, int right)
停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
void addRange(int left, int right)
添加 半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
bool queryRange(int left, int right)
只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true ,否则返回 false 。
int get(int key)
如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。
unordered_map< int, int > um
map< int, list< int > > tnc
unordered_map< int, int > cnt
void put(int key, int value)
如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity 时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频...
int sumCount(int sum, int i)
vector< unordered_map< int, int > > mem
int fourSumCount(vector< int > &nums1, vector< int > &nums2, vector< int > &nums3, vector< int > &nums4)
vector< unordered_map< int, int > > vec
static int maxSubArrayLen(vector< int > &nums, int k)
static int minSwaps(vector< int > &data)
array< TrieNode *, 26 > nexts
void insert(const string &str)