oj.uz

답안 #789065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789065 2023-07-21T00:25:32 Z tvladm2009 가로등 (APIO19_street_lamps) C++17
40 / 100
 152 ms 44916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 3e5 + 7;
int sol[107][107];
int n, q;
string s;

struct Operation {
  bool type;
  int a;
  int b;
};

vector<Operation> op;

int subtask() {
  if (n <= 100 && q <= 100) {
    return 1;
  }
  for (auto &it : op) {
    if (it.type == 1 && it.b - it.a != 1) {
      return 3;
    }
  }
  return 2;
}

int nodes = 0;

struct Dsu {
  struct History {
    int u;
    int v;
    int oldv;
    int oldszv;
  };

  vector<int> t, sz, par;
  vector<History> st;

  void init(int n) {
    t.resize(n + 1);
    sz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      t[i] = i;
      sz[i] = 1;
    }
  }

  int root(int u) {
    assert(u <= 6);
    if (t[u] == u) {
      return u;
    }
    return root(t[u]);
  }

  void unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u != v) {
      if (sz[u] < sz[v]) {
        swap(u, v);
      }
      st.push_back({u, v, t[v], sz[v]});
      t[v] = u;
      sz[u] += sz[v];
    }
  }

  void undo() {
    History aux = st.back();
    st.pop_back();
    t[aux.v] = aux.oldv;
    sz[aux.v] = aux.oldszv;
    sz[aux.u] -= aux.oldszv;
  }
};

struct DynamicConectivity {
  vector<vector<pair<int, int>>> segt;
  Dsu dsu;

  void init(int q, int n) {
    segt.resize(4 * q + 1);
    dsu.init(n);
  }

  void update(int v, int tl, int tr, int x, int y, pair<int, int> edg) {
    if (tr < x || y < tl) {
      return;
    }
    if (x <= tl && tr <= y) {
      segt[v].push_back(edg);
      return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, x, y, edg);
    update(2 * v + 1, tm + 1, tr, x, y, edg);
  }

  void ins(int x, int y, pair<int, int> edg) {
    update(1, 1, q, x, y, edg);
  }

  vector<pair<int, int>> edges;

  void query(int v, int tl, int tr, int x, int y, int node, int &comp) {
    if (tr < x || y < tl) {
      return;
    }
    int undo = 0;
    /// cout << "! " << v << "\n";
    for (auto &edg : segt[v]) {
      /// cout << edg.first << " " << edg.second << "\n";
      if (dsu.root(edg.first) != dsu.root(edg.second)) {
        undo++;
        assert(edg.first <= 6 && edg.second <= 6);
        dsu.unite(edg.first, edg.second);
      }
    }
    if (x <= tl && tr <= y) {
      comp = dsu.root(node);
      /// for (auto &it : edges) {
        /// cout << it.first << " " << it.second << "\n";
      /// }
      /// cout << "\n";
    } else {
      int tm = (tl + tr) / 2;
      query(2 * v, tl, tm, x, y, node, comp);
      query(2 * v + 1, tm + 1, tr, x, y, node, comp);
    }
    while (undo--) {
      dsu.undo();
      edges.pop_back();
    }
  }

  void del(int n) {
    dsu.init(n);
  }
};

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> q >> s;
  s = "#" + s;
  for (int iq = 1; iq <= q; iq++) {
    string t;
    cin >> t;
    if (t == "toggle") {
      int a;
      cin >> a;
      op.push_back({0, a, -1});
    } else {
      int a, b;
      cin >> a >> b;
      op.push_back({1, a, b});
    }
  }
  if (subtask() == 1) {
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        int j = i;
        while (j <= n && s[j] == '1') {
          sol[i][j + 1]++;
          j++;
        }
      }
    }
    for (auto &it : op) {
      if (it.type == 1) {
        cout << sol[it.a][it.b] << "\n";
      } else {
        int pos = it.a;
        s[pos] ^= '0' ^ '1';
      }

      for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
          int j = i;
          while (j <= n && s[j] == '1') {
            sol[i][j + 1]++;
            j++;
          }
        }
      }
    }
    return 0;
  }
  if (subtask() == 2) {
    vector<vector<pair<int, int>>> active(n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        active[i].push_back({0, -1});
      }
    }
    for (int i = 0; i < q; i++) {
      if (op[i].type == 0) {
        int pos = op[i].a;
        if (s[pos] == '0') {
          s[pos] = '1';
          active[pos].push_back({i + 1, -1});
        } else {
          s[pos] = '0';
          active[pos].back().second = i;
        }
      }
    }
    vector<vector<int>> sp(n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        active[i].back().second = q;
      }
      if ((int) active[i].size() == 0) {
        continue;
      }
      sp[i].resize((int) active[i].size());
      sp[i][0] = active[i][0].second - active[i][0].first + 1;
      for (int j = 1; j < (int) active[i].size(); j++) {
        sp[i][j] = sp[i][j - 1] + active[i][j].second - active[i][j].first + 1;
      }
    }
    function<int(int, int)> get = [&](int pos, int t) {
      int low = 0, high = (int) active[pos].size() - 1, x = -1;
      while (low <= high) {
        int mid = (low + high) / 2;
        if (active[pos][mid].second <= t) {
          low = mid + 1;
          x = mid;
        } else {
          high = mid - 1;
        }
      }
      int sol = 0;
      if (x != -1) {
        sol += sp[pos][x];
      }
      if (x + 1 < (int) active[pos].size() && active[pos][x + 1].first <= t) {
        sol += t - active[pos][x + 1].first + 1;
      }
      return sol;
    };
    for (int i = 0; i < q; i++) {
      if (op[i].type == 1) {
        assert(op[i].a + 1 == op[i].b);
        cout << get(op[i].a, i) << "\n";
      }
    }
    return 0;
  }
  if (subtask() == 3) {
    DynamicConectivity dc;
    dc.init(q + 1, n + 1);
    for (int i = 1; i <= n; i++) {
      if (s[i] == '1') {
        dc.ins(1, q + 1, {i, i + 1});
      }
    }

    for (int i = 0; i < q; i++) {
      if (op[i].type == 0) {
        dc.ins(i + 2, q + 1, {op[i].a, op[i].a + 1});
      }
    }

    /// int comp = 0;
    /// dc.query(1, 1, q + 1, 1, 6, 4, comp);
    ///cout << comp << "\n";
    /// return 0;

    for (int i = 0; i < q; i++) {
      if (op[i].type == 1) {
        int a = op[i].a;
        int b = op[i].b;
        int low = 1, high = i + 2, sol = -1;
        while (low <= high) {
          int mid = (low + high) / 2;
          int compa = 0, compb = 0;
          dc.query(1, 1, q + 1, 1, mid, a, compa);
          dc.query(1, 1, q + 1, 1, mid, b, compb);
          /// cout << mid << " " << a << " " << b << " => " << compa << " " << compb << "\n";
          if (compa == compb) {
            sol = mid;
            high = mid - 1;
          } else {
            low = mid + 1;
          }
        }
        if (sol == -1) {
          cout << "0\n";
        } else {
          cout << i + 2 - sol << "\n";
          /// cout << i << " " << sol << "\n";
        }
      }
    }
    return 0;
  }
  return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 6536 KB Output is correct
2 Correct 67 ms 9808 KB Output is correct
3 Correct 72 ms 10352 KB Output is correct
4 Correct 129 ms 37128 KB Output is correct
5 Correct 152 ms 43260 KB Output is correct
6 Correct 123 ms 37472 KB Output is correct
7 Correct 89 ms 25500 KB Output is correct
8 Correct 139 ms 44916 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 64 ms 6536 KB Output is correct
9 Correct 67 ms 9808 KB Output is correct
10 Correct 72 ms 10352 KB Output is correct
11 Correct 129 ms 37128 KB Output is correct
12 Correct 152 ms 43260 KB Output is correct
13 Correct 123 ms 37472 KB Output is correct
14 Correct 89 ms 25500 KB Output is correct
15 Correct 139 ms 44916 KB Output is correct
16 Runtime error 2 ms 852 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -