General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
53560424 Practice:
mnbvmar
1150E - 16 C++17 (GCC 7-32) Accepted 186 ms 12836 KB 2019-04-30 12:09:28 2019-04-30 12:09:28
→ Source
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Tree {
  // Node maximizing the value of depth(l) - 2*depth(v) + depth(r) for l<=v<=r
  struct Node {
    int delta;        // num '(' - num ')'
    int min_depth;    // minimum value of [num '(' - num ')'] on prefix
    int max_depth;    // maximum ...
    int max_lv;       // max value of [depth(l) - 2 * depth(v)], l <= v
    int max_rv;       // max value of [depth(r) - 2 * depth(v)], v <= r
    int max_lvr;      // max value of [depth(l) - 2 * depth(v) + depth(r)]

    static Node Empty() {
      return Node{0, 0, 0, 0, 0, 0};
    }

    static Node LeftParenthesis() {
      return Node{1, 0, 1, 0, 1, 1};
    }

    static Node RightParenthesis() {
      return Node{-1, -1, 0, 2, 1, 1};
    }

    static Node FromCharacter(char ch) {
      if (ch == '(')
        return LeftParenthesis();
      else
        return RightParenthesis();
    }

    Node ShiftHeight(int displacement) const {
      return Node{delta + displacement,
                  min_depth + displacement,
                  max_depth + displacement,
                  max_lv - displacement,
                  max_rv - displacement,
                  max_lvr};
    }

    static Node Merge(const Node &lhs, const Node &rhs) {
      Node rhs_shifted = rhs.ShiftHeight(lhs.delta);

      Node result;
      result.delta = rhs_shifted.delta;
      result.min_depth = min(lhs.min_depth, rhs_shifted.min_depth);
      result.max_depth = max(lhs.max_depth, rhs_shifted.max_depth);
      result.max_lv = max(
          {lhs.max_lv, rhs_shifted.max_lv, lhs.max_depth - 2 * rhs_shifted.min_depth});
      result.max_rv = max(
          {lhs.max_rv, rhs_shifted.max_rv, rhs_shifted.max_depth - 2 * lhs.min_depth});
      result.max_lvr = max(
          {lhs.max_lvr, rhs_shifted.max_lvr,
           lhs.max_lv + rhs_shifted.max_depth,
           rhs_shifted.max_rv + lhs.max_depth});
      return result;
    }
  };

  vector<Node> data;
  int Base;

  Tree(int N) : Base(1) {
    while (Base < N + 1) { Base *= 2; }
    data.resize(Base * 2, Node::Empty());
  }

  void Replace(int pos, char ch) {
    pos += Base;
    data[pos] = Node::FromCharacter(ch);
    pos /= 2;

    while (pos) {
      data[pos] = Node::Merge(data[pos * 2], data[pos * 2 + 1]);
      pos /= 2;
    }
  }

  int GetMaxPath() const {
    return data[1].max_lvr;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, Q;
  string paren_string;
  cin >> N >> Q >> paren_string;
  --N;

  Tree path_tree(N * 2);
  for (int i = 0; i < N * 2; ++i) {
    path_tree.Replace(i, paren_string[i]);
  }

  cout << path_tree.GetMaxPath() << "\n";
  for (int query_idx = 0; query_idx < Q; ++query_idx) {
    int first_swap, second_swap;
    cin >> first_swap >> second_swap;
    --first_swap;
    --second_swap;

    const char next_first = paren_string[second_swap];
    const char next_second = paren_string[first_swap];

    assert(next_first != next_second);
    path_tree.Replace(first_swap, next_first);
    paren_string[first_swap] = next_first;

    path_tree.Replace(second_swap, next_second);
    paren_string[second_swap] = next_second;

    cout << path_tree.GetMaxPath() << "\n";
  }
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details