Advertisement
999ms

Untitled

Apr 23rd, 2021
1,000
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) begin(x),end(x)
  3.  
  4. using namespace std;
  5.  
  6. void solveA() {
  7.   string s;
  8.   cin >> s;
  9.   cout << s << '\n';
  10. }
  11.  
  12. void solveB() {
  13.   int n, q;
  14.   cin >> n >> q;
  15.   vector<int> start(n, -1);
  16.   int maxTime = 0;
  17.   int answer = 0;
  18.   for (int i = 0; i < q; i++) {
  19.     int index;
  20.     int type;
  21.     cin >> type >> index;
  22.     if (type == 1) {
  23.       start[index - 1] = i;
  24.     } else {
  25.       int currentTime = i - start[index - 1];
  26.       if (currentTime >= maxTime) {
  27.         maxTime = currentTime;
  28.         answer = index;
  29.       }
  30.     }
  31.   }
  32.   cout << answer << ' ' << maxTime << '\n';
  33. }
  34.  
  35. void solveC() {
  36.   int n, m;
  37.   cin >> n >> m;
  38.   vector<string> arr(n);
  39.   int mnx = n, mny = m, mxx = -1, mxy = -1;
  40.   for (int i = 0; i < n; i++) {
  41.     cin >> arr[i];
  42.     for (int j = 0; j < m; j++) {
  43.       if (arr[i][j] == '0') {
  44.         mnx = min(mnx, i);
  45.         mxx = max(mxx, i);
  46.         mny = min(mny, j);
  47.         mxy = max(mxy, j);
  48.       }
  49.     }
  50.   }
  51.  
  52.   bool good = mnx <= mxx && mny <= mxy;
  53.   for (int x = mnx; x <= mxx && good; x++) {
  54.     good &= arr[x][mny] == arr[x][mxy] && arr[x][mny] == '0';
  55.   }
  56.   for (int y = mny; y <= mxy && good; y++) {
  57.     good &= arr[mnx][y] == arr[mxx][y] && arr[mnx][y] == '0';
  58.   }
  59.  
  60.   cout << (good ? "YES\n" : "NO\n");
  61. }
  62.  
  63. void solveD() {
  64.   int t;
  65.   cin >> t;
  66.   while (t--) {
  67.     string s;
  68.     cin >> s;
  69.     bool good = false;
  70.     vector<int> indexes(6);
  71.     iota(all(indexes), 0);
  72.    
  73.     do {
  74.       bool cur = true;
  75.      
  76.       for (int i = 0; i < 6; i++) {
  77.         if (s[indexes[i] * 6 + i] == '0') {
  78.           cur = false;
  79.         }
  80.       }
  81.      
  82.       good |= cur;
  83.     } while (next_permutation(all(indexes)));
  84.    
  85.     cout << (good ? "YES\n" : "NO\n");
  86.   }
  87. }
  88.  
  89.  
  90. void solveE() {
  91.   int n;
  92.   cin >> n;
  93.   vector<int> arr(n);
  94.   for (int i = 0; i < n; i++) {
  95.     cin >> arr[i];
  96.   }
  97.  
  98.   vector<vector<int>> g (n);
  99.  
  100.   for (int i = 0; i < n - 1; i++) {
  101.     int f, t;
  102.     cin >> f >> t;
  103.     f--, t--;
  104.     g[f].push_back(t);
  105.     g[t].push_back(f);
  106.   }
  107.  
  108.   vector<pair<int, long long>> depth(n);
  109.  
  110.   function<void(int, int)> Dfs = [&] (int from, int parent) {
  111.     depth[from].first = depth[parent].first + 1;
  112.     depth[from].second = depth[parent].second + arr[from];
  113.     for (int to : g[from]) {
  114.       if (to == parent) continue;
  115.       Dfs(to, from);
  116.     }
  117.   };
  118.  
  119.   Dfs(0, 0);
  120.  
  121.   int root = distance(begin(depth), max_element(all(depth)));
  122.   depth.assign(n, {0, 0ll});
  123.  
  124.   Dfs(root, root);
  125.  
  126.   cout << accumulate(all(arr), 0ll) - (*max_element(all(depth))).second << '\n';
  127. }
  128.  
  129.  
  130. void solveF() {
  131.   int X, Y;
  132.   cin >> X >> Y;
  133.   int N = max(X, Y) + 1;
  134.   vector<int> minSeive(N, 1);
  135.   vector<int> maxSeive(N, 1);
  136.   vector<bool> used(N, false);
  137.  
  138.   for (int i = 2; i < N; i++) {
  139.     if (used[i]) continue;
  140.     for (int j = i; j < N; j += i) {
  141.       if (!used[j]) {
  142.         minSeive[j] = i;
  143.         used[j] = true;
  144.       }
  145.       maxSeive[j] = i;
  146.     }
  147.   }
  148.  
  149.   vector<vector<long long>> arr(X, vector<long long>(Y, 0));
  150.   for (int x = 0; x < X; x++) {
  151.     for (int y = 0; y < Y; y++) {
  152.       arr[x][y] = 1ll * minSeive[x + 1] * maxSeive[y + 1];
  153.     }
  154.   }
  155.  
  156.   for (int x = 1; x < X; x++) {
  157.     for (int y = 0; y < Y; y++) {
  158.       arr[x][y] += arr[x - 1][y];
  159.     }
  160.   }
  161.  
  162.   for (int x = 0; x < X; x++) {
  163.     for (int y = 1; y < Y; y++) {
  164.       arr[x][y] += arr[x][y - 1];
  165.     }
  166.   }
  167.  
  168.   int q;
  169.   cin >> q;
  170.   while (q--) {
  171.     int x, y;
  172.     cin >> x >> y;
  173.     cout << arr[x - 1][y - 1] << '\n';
  174.   }
  175. }
  176.  
  177.  
  178. void solveG() {
  179.   int n;
  180.   cin >> n;
  181.   vector<string> g(n);
  182.   for (int i = 0; i < n; i++) {
  183.     cin >> g[i];
  184.   }
  185.  
  186.   vector<bool> used(n, false);
  187.   vector<bool> matched(n, false);
  188.   vector<int> mt(n, -1);
  189.  
  190.   function<bool(int)> Increment = [&] (int v) {
  191.     if (used[v]) return false;
  192.     used[v] = true;
  193.     for (int i = 0; i < g[v].size(); i++) {
  194.       if (g[v][i] == '0') continue;
  195.       int nxt = i;
  196.       if (mt[nxt] == -1) {
  197.         matched[v] = true;
  198.         mt[nxt] = v;
  199.         return true;
  200.       }
  201.     }
  202.    
  203.     for (int i = 0; i < g[v].size(); i++) {
  204.       if (g[v][i] == '0') continue;
  205.       int nxt = i;
  206.       if (Increment(mt[nxt])) {
  207.         matched[v] = true;
  208.         mt[nxt] = v;
  209.         return true;
  210.       }
  211.     }
  212.     return false;
  213.   };
  214.  
  215.   int answer = 0;
  216.   for (int run = 1; run; ) {
  217.     run = 0;
  218.     fill(all(used), false);
  219.     for (int i = 0; i < n; i++) {
  220.       if (!matched[i] && Increment(i)) {
  221.         run = 1;
  222.         answer++;
  223.       }
  224.     }
  225.   }
  226.  
  227.   cout << (answer == n ? "YES\n" : "NO\n");
  228. }
  229.  
  230. void solveH() {
  231.   int n;
  232.   cin >> n;
  233.   vector<tuple<int,int,int>> arr;
  234.   for (int x = 0; x < n; x++) {
  235.     int y;
  236.     cin >> y;
  237.     arr.emplace_back(x - y, x + y, x);
  238.   }
  239.   sort(all(arr));
  240.  
  241.   vector<int> from(n, -1);
  242.   vector<int> len(n, 0);
  243.   set<pair<int,int>> st;
  244.  
  245.   for (auto& [x, y, index] : arr) {
  246.     auto it = st.lower_bound({y, INT_MAX});
  247.     if (it == st.begin()) {
  248.       len[index] = 1;
  249.     } else {
  250.       int prevIndex = prev(it)->second;
  251.       len[index] = len[prevIndex] + 1;
  252.       from[index] = prevIndex;
  253.       if (it->first == y) {
  254.         st.erase(it);
  255.       }
  256.     }
  257.  
  258.     auto currentIterator = st.insert({y, index}).first;
  259.     while (next(currentIterator) != st.end()) {
  260.       auto nextIterator = next(currentIterator);
  261.       if (len[nextIterator->second] <= len[index]) {
  262.         st.erase(nextIterator);
  263.       } else {
  264.         break;
  265.       }
  266.     }
  267.   }
  268.  
  269.   int v = distance(begin(len), max_element(all(len)));
  270.   vector<int> answer;
  271.  
  272.   while (v != -1) {
  273.     answer.push_back(v);
  274.     v = from[v];
  275.   }
  276.  
  277.   cout << answer.size() << '\n';
  278.   while (answer.size()) {
  279.     cout << answer.back() + 1 << ' ';
  280.     answer.pop_back();
  281.   }
  282.   cout << '\n';
  283. }
  284.  
  285. int main() {
  286.   solveH();
  287. }
  288.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement