Submission #1174718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174718		JelalTkm	Street Lamps (APIO19_street_lamps)	C++20	60 / 100	150 ms	25204 KiB

street_lamps

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1000 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;

struct node {
  int on = -1, sm = 0;
};

struct node1 {
  string s;
  int a, b;
};

struct segtree {
 
  vector<int> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, INF);
  }
 
  // void build(vector<int> &a, int x, int lx, int rx) {
  //   if (rx - lx == 1) {
  //     if (lx < (int) a.size())
  //       tree[x] = a[lx];
  //   } else {
  //     int m = (lx + rx) >> 1;
  //     build(a, 2 * x + 1, lx, m);
  //     build(a, 2 * x + 2, m, rx);
  //     tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  //   }
  // }
 
  // void build(vector<int> &a) {
  //   init((int) a.size());
  //   build(a, 0, 0, size);
  // }
 
  void set(int i, int v, int x, int lx, int rx) {
    if (rx - lx == 1) {
      tree[x] = v;
      return;
    }
    int m = (lx + rx) >> 1;
    if (i < m) {
      set(i, v, 2 * x + 1, lx, m);
    } else {
      set(i, v, 2 * x + 2, m, rx);
    }
    tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void set(int i, int v) {
    set(i, v, 0, 0, size);
  }
 
  int get(int l, int r, int x, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return 0;
    }
    if (lx >= l && rx <= r) {
      return tree[x];
    }
    int m = (lx + rx) >> 1;
    int s1 = get(l, r, 2 * x + 1, lx, m);
    int s2 = get(l, r, 2 * x + 2, m, rx);
    return max(s1, s2);
  }
 
  int get(int l, int r) {
    return get(l, r, 0, 0, size);
  }
};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n, q;
    cin >> n >> q;
    if (n <= 100 && q <= 100) {
      string s;
      cin >> s;
      s = '#' + s;
      vector<vector<int>> a(n + 2, vector<int> (n + 2));
      while (q--) {
        for (int i = 1; i <= n; i++)
          for (int j = i; j <= n; j++) {
            if (s[j] == '0') break;
            else a[i][j + 1]++;
          }
        string c;
        cin >> c;
        if (c == "toggle") {
          int i;
          cin >> i;
          s[i] = (s[i] == '1' ? '0' : '1');
        } else {
          int l, r;
          cin >> l >> r;
          cout << a[l][r] << '\n';
        }
      }
    } else {
      string s;
      cin >> s;
      s = '#' + s;
      vector<node1> que(q + 1);
      bool ok = 1;
      for (int i = 1; i <= q; i++) {
        cin >> que[i].s;
        if (que[i].s == "toggle") {
          cin >> que[i].a;
        } else {
          cin >> que[i].a >> que[i].b;
          if ((que[i].b - que[i].a) != 1)
            ok = 0;
        }
      }

      if (ok == 1) {
        vector<node> a(n + 1);
        for (int i = 1; i <= n; i++) {
          if (s[i] == '1') {
            a[i].on = 0;
          }
        }

        int tm = 0;
        for (int w = 1; w <= q; w++) {
          tm++;
          string c;
          c = que[w].s;
          if (c == "toggle") {
            int i = que[w].a;
            if (s[i] == '1') {
              a[i].sm += (tm - a[i].on);
              a[i].on = -1;
            } else {
              a[i].on = tm;
            }
            s[i] = (s[i] == '1' ? '0' : '1');
          } else {
            int l = que[w].a;
            int r = que[w].b;
            cout << a[l].sm + (tm - (a[l].on == -1 ? tm : a[l].on)) << '\n';
          }
        }
      } else {
        int tm = 0;
        segtree st;
        st.init(n + 1);
        for (int i = 1; i <= n; i++) {
          if (s[i] == '1') {
            st.set(i, 0);
          }
        }
        for (int w = 1; w <= q; w++) {
          tm++;
          if (que[w].s == "toggle") {
            st.set(que[w].a, tm);
          } else {
            cout << max(0ll, tm - (st.get(que[w].a, que[w].b))) << '\n';
          }
        }
      }
    }
  }

  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20