Submission #553480

#	Time	Username	Problem	Language	Result	Execution time	Memory
553480		quocnguyen1012	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	2640 ms	153220 KiB

street_lamps

#include "bits/stdc++.h"

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

struct BIT2d {
  vector<vector<int>> val;
  vector<vector<pair<int, int>>> bit;
  BIT2d(int n) {
    bit.assign(n + 5, {});
    val.assign(n + 5, {});
  }
  pair<int, int> add(pair<int, int> x, pair<int, int> y) {
    x.first += y.first; x.second += y.second;
    return x;
  }
  pair<int, int> minus(pair<int, int> x, pair<int, int> y) {
    x.first -= y.first; x.second -= y.second;
    return x;
  }
  void normalize() {
    for (int x = 1; x < (int)bit.size(); ++x) {
      val[x].push_back(INT_MIN);
      sort(val[x].begin(), val[x].end());
      val[x].erase(unique(val[x].begin(), val[x].end()), val[x].end());
      bit[x].assign(val[x].size() + 5, {0, 0});
    }
  }
  void fakeupdate(int x, int y) {
    for (int i = x; i < (int)bit.size(); i += i & -i) {
      val[i].push_back(y);
    }
  }
  void update(int x, int y, pair<int, int> delta) {
    for (; x < (int)bit.size(); x += x & -x) {
      //debug(x, y, *upper_bound(val[x].begin(), val[x].end(), y));
      //debug(val[x]);
      for (int i = upper_bound(val[x].begin(), val[x].end(), y) - val[x].begin();
                i < (int)bit[x].size(); i += i & -i) {
                  bit[x][i] = add(bit[x][i], delta);
                }
    }
  }

  pair<int, int> getsum(int x, int l, int r) {
    pair<int, int> tot{0, 0};
    for (; x; x -= x & -x) {
      const auto get = [&](int y) {
        pair<int, int> res{0, 0};
        for (int i = upper_bound(val[x].begin(), val[x].end(), y) - val[x].begin();
                i; i -= i & -i) {
                  res = add(res, bit[x][i]);
                }
        return res;
      };
      tot = add(tot, minus(get(r), get(l - 1)));
    }
    return tot;
  }
  pair<int, int> getsum(int x1, int y1, int x2, int y2) {
    return minus(getsum(x2, y1, y2), getsum(x1 - 1, y1, y2));
  }
  pair<int, int> nestedInterval(int l, int r) {
    return getsum(1, r, l, 1e9);
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, q; cin >> n >> q;
  string s; cin >> s; s = " " + s;
  vector<tuple<int, int, int>> queries;
  queries.emplace_back(0, 0, 0);
  for (int i = 1; i <= q; ++i) {
    string op; cin >> op;
    if (op[0] == 'q') {
      int l, r; cin >> l >> r;
      queries.emplace_back(1, l, r);
    } else {
      int pos; cin >> pos;
      queries.emplace_back(0, pos, 0);
    }
  }
  set<pair<int, int>> intervals;
  BIT2d t(n + 5);

  const auto initIntervals = [&](const string &s) {
    vector<pair<int, int>> v;
    for (int i = 1; i <= n; ++i) {
      if (s[i] == '0') continue;
      int j = i;
      while (j <= n and s[i] == s[j]) ++j; --j;
      v.emplace_back(i, j);
      i = j;
    }
    return v;
  };
  /// fakeupdate 
  string cs = s;
  intervals.clear();
  for (const auto &x : initIntervals(s)) {
    intervals.insert(x);
  }
  vector<vector<tuple<int, int, int>>> addSeg(q + 5), delSeg(q + 5);
  map<pair<int, int>, int> last;
  for (auto [l, r] : intervals) {
    addSeg[1].emplace_back(l, r, 0);
    last[{l, r}] = 0;
  }
  for (int i = 1; i <= q; ++i) {
    const auto&[op, a, b] = queries[i];
    const auto addInterval = [&](int l, int r) {
      if (l > r) return;
      last[{l, r}] = i;
      intervals.insert({l, r});
      addSeg[i].emplace_back(l, r, i);
    };
    const auto delInterval = [&](int l, int r) {
      if (l > r) return; 
      intervals.erase(intervals.find({l, r}));
      delSeg[i].emplace_back(l, r, i);
      last[{l, r}] = 0;
    };
    if (op == 1) {
      
    } else {
      if (s[a] == '0') {
        auto it = intervals.upper_bound({a, INT_MAX}); 
        int l = a, r = a;
        auto pre = it; --pre;
        bool good = (it!=intervals.begin());
        if (it != intervals.end()) {
          if (it->first==a+1) {
            r=it->second;
            delInterval(it->first, it->second);
          }
        }
        if (good) {
          if (pre->second+1==a) {
            l = pre->first;
            delInterval(pre->first, pre->second);
          }
        }
        addInterval(l, r);
      } else {
        auto it = intervals.upper_bound({a, INT_MAX});
        --it;
        auto [l, r] = (*it);
        delInterval(l, r);
        addInterval(l, a-1);
        addInterval(a+1, r);
      }
      s[a] = '0' + '1' - s[a];
    }
    for (auto [x, y, ignore] : addSeg[i]) t.fakeupdate(x, y);
    for (auto [x, y, ignore] : delSeg[i]) t.fakeupdate(x, y);
  }
  t.normalize();
  for (int i = 1; i <= q; ++i) {
    for (auto [x, y, id] : addSeg[i]) {
      debug("add", x, y, id);
      t.update(x, y, {1, -id});
    } 
    for (auto [x, y, id] : delSeg[i]){
      t.update(x, y, {1, id});
      debug("del", x, y, id);
    } 
    auto [op, a, b] = queries[i];
    if (op == 1) {
      auto res = t.nestedInterval(a, b-1);
      debug(res);
      cout << (res.first % 2) * (i) + res.second<< '\n';
    }
  }
}

Compilation message (stderr)

street_lamps.cpp: In lambda function:
street_lamps.cpp:137:7: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  137 |       while (j <= n and s[i] == s[j]) ++j; --j;
      |       ^~~~~
street_lamps.cpp:137:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  137 |       while (j <= n and s[i] == s[j]) ++j; --j;
      |                                            ^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:151:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |   for (auto [l, r] : intervals) {
      |             ^
street_lamps.cpp:156:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |     const auto&[op, a, b] = queries[i];
      |                ^
street_lamps.cpp:193:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  193 |         auto [l, r] = (*it);
      |              ^
street_lamps.cpp:200:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  200 |     for (auto [x, y, ignore] : addSeg[i]) t.fakeupdate(x, y);
      |               ^
street_lamps.cpp:201:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  201 |     for (auto [x, y, ignore] : delSeg[i]) t.fakeupdate(x, y);
      |               ^
street_lamps.cpp:205:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  205 |     for (auto [x, y, id] : addSeg[i]) {
      |               ^
street_lamps.cpp:48:20: warning: statement has no effect [-Wunused-value]
   48 | #define debug(...) 42
      |                    ^~
street_lamps.cpp:206:7: note: in expansion of macro 'debug'
  206 |       debug("add", x, y, id);
      |       ^~~~~
street_lamps.cpp:209:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  209 |     for (auto [x, y, id] : delSeg[i]){
      |               ^
street_lamps.cpp:48:20: warning: statement has no effect [-Wunused-value]
   48 | #define debug(...) 42
      |                    ^~
street_lamps.cpp:211:7: note: in expansion of macro 'debug'
  211 |       debug("del", x, y, id);
      |       ^~~~~
street_lamps.cpp:213:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  213 |     auto [op, a, b] = queries[i];
      |          ^
street_lamps.cpp:48:20: warning: statement has no effect [-Wunused-value]
   48 | #define debug(...) 42
      |                    ^~
street_lamps.cpp:216:7: note: in expansion of macro 'debug'
  216 |       debug(res);
      |       ^~~~~

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