Submission #855826

#	Time	Username	Problem	Language	Result	Execution time	Memory
855826		NeroZein	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	1318 ms	524288 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int INF = 1e9; 

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int, 3>> se; 
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') {
      continue;
    }
    int j = i;
    while (j + 1 < n && s[j + 1] == '1') {
      j++; 
    }
    se.insert({i, j, 0}); 
    i = j; 
  }
  vector<map<int, int>> tmp(n); 
  auto edit_set = [&](int i, int t) {
    if (s[i] == '1') {
      array<int, 3> key = {i, INF, INF};
      auto f = se.upper_bound(key);
      --f;
      for (int x = (*f)[0]; x <= (*f)[1]; x++) {
        for (int y = x; y <= (*f)[1]; y++) {
          tmp[x][y] += t - (*f)[2]; 
          //deb(x) deb(y) deb(i) deb(tmp[0][1]) cout << '\n';
        }
      }
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        se.erase(f); 
        int l = (*f)[0], r = (*f)[1]; 
        se.insert({l, i - 1, t});
        se.insert({i + 1, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        int l = (*f)[0];
        se.erase(f);
        se.insert({l, i - 1, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        int r = (*f)[1];
        se.erase(f);
        se.insert({i + 1, r, t}); 
      } else {
        se.erase(f); 
      }
    } else {
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto pr = se.upper_bound(key);
        --pr;
        key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        int l = (*pr)[0], r = (*nx)[1];
        for (int x = (*pr)[0]; x <= (*pr)[1]; ++x) {
          for (int y = x; y <= (*pr)[1]; ++y) {
            tmp[x][y] += t - (*pr)[2]; 
          }
        }
        for (int x = (*nx)[0]; x <= (*nx)[1]; ++x) {
          for (int y = x; y <= (*nx)[1]; ++y) {
            tmp[x][y] += t - (*nx)[2]; 
          }
        }
        se.erase(pr);
        se.erase(nx);
        se.insert({l, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto pr = se.upper_bound(key);
        --pr;
        int l = (*pr)[0], r = i; 
        for (int x = (*pr)[0]; x <= (*pr)[1]; ++x) {
          for (int y = x; y <= (*pr)[1]; ++y) {
            tmp[x][y] += t - (*pr)[2]; 
          }
        }
        se.erase(pr); 
        se.insert({l, r, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        for (int x = (*nx)[0]; x <= (*nx)[1]; ++x) {
          for (int y = x; y <= (*nx)[1]; ++y) {
            tmp[x][y] += t - (*nx)[2]; 
          }
        }
        int l = i, r = (*nx)[1];
        se.erase(nx); 
        se.insert({l, r, t}); 
      } else {
        se.insert({i, i, t}); 
      }
    }
    s[i] ^= 1; 
  }; 
  vector<vector<pair<int, int>>> vec(n);
  for (int i = 1; i <= q; ++i) {
    string qs;
    cin >> qs;
    if (qs == "query") {
      int l, r;
      cin >> l >> r;
      --l, r -= 2; 
      int ans = 0; 
      array<int, 3> key = {l, INF, INF}; 
      auto f = se.upper_bound(key);
      if (f != se.begin()) {
        --f; 
        if ((*f)[0] <= l && (*f)[1] >= r) {
          ans += i - (*f)[2];
        }
      }
      cout << ans + tmp[l][r] << '\n'; 
    } else {
      int ind;
      cin >> ind;
      edit_set(ind - 1, i); 
    }
  }
  return 0;
}

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