- Choose the invariant that makes a window valid or useful.
- Advance the right boundary and add the new element.
- Move the left boundary only as needed while maintaining the invariant and updating the answer.
Code notes
- 71 lines of C++ from the credited upstream file abc237_d.cpp.
- The implementation keeps its working state in language-native values and containers.
- 2 loop blocks detected.
Complexity
Confirm that neither pointer moves backwards; if so, the scan is usually linear apart from the window’s data-structure operations.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <iostream>2#include <stack>3 4using namespace std;5using ui = unsigned int;6 7struct Node {8 ui x;9 Node* left;10 Node* right;11};12 13int main() {14 Node a = {0, NULL, NULL};15 Node* root = &a;16 17 ui n;18 cin >> n;19 20 bool root_comp = false;21 22 stack<Node*> ns;23 ns.push(root);24 25 for (ui i = 1; i <= n; i++) {26 char si;27 cin >> si;28 Node* nn = new Node({i, NULL, NULL});29 Node* prev = ns.top();30 ns.pop();31 32 if (si == 'R') {33 root_comp = true;34 nn->left = prev;35 if (prev->right != NULL) {36 prev->right->left = nn;37 nn->right = prev->right;38 }39 prev->right = nn;40 } else if (si == 'L') {41 nn->right = prev;42 if (prev->left != NULL) {43 nn->left = prev->left;44 prev->left->right = nn;45 }46 prev->left = nn;47 if (!root_comp) {48 root = nn;49 }50 } else {51 52 }53 54 ns.push(nn);55 }56 57 Node* node = root;58 cout << node->x;59 60 node = node->right;61 while (true) {62 cout << " " << node->x;63 if (node->right == NULL) {64 break;65 }66 node = node->right;67 }68 cout << endl;69 70 return 0;71}