Submission #1143680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143680		cadmiumsky	Street Lamps (APIO19_street_lamps)	C++20	60 / 100	5084 ms	280876 KiB

street_lamps

#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,int>;

const int nmax = 3e5 + 5;

int last[nmax];
int rez[nmax];

vector<tii> upds[nmax];

vector<tiii> squares;
namespace Beats {
   set<int> lends;
   int rend[nmax];
   int lval[nmax];
   void init(int n) {
      lends.emplace(1);
      rend[1] = n;
      lval[1] = 0;
   }
   
   void set(int l, int r, int a) {
      auto it = lends.lower_bound(l);
      if(it == lends.begin());
      else {
         it = prev(it);
         if(rend[*it] >= r) {
            int metar = rend[*it];
            rend[*it] = l - 1;
            squares.emplace_back(lval[*it], a, l, r);
            
            lends.emplace(l);
            rend[l] = r;
            lval[l] = a;
            
            if(metar > r) {
               lends.emplace(r + 1);
               rend[r + 1] = metar;
               lval[r + 1] = lval[*it];
            }
            return;
         }
         squares.emplace_back(lval[*it], a, l, rend[*it]);
         rend[*it] = l - 1;
      }
      while(1) {
         it = lends.lower_bound(l);
         if(it == lends.end()) break;
         if(*it > r) break;
         
         squares.emplace_back(lval[*it], a, max(l, *it), min(r, rend[*it]));
         
         if(rend[*it] > r) {
            lval[r + 1] = lval[*it];
            rend[r + 1] = rend[*it];
            lends.emplace(r + 1);
         }
         
         lends.erase(it);
      }
      lends.emplace(l);
      lval[l] = a;
      rend[l] = r;
      return;
   }
}

#define lsb(x) (x & -x)
struct AIB { // pt R-uri
   int fake = 1;
   map<int, int> atr;
   vector<int> tree;
   void upd(int p, int x) {
      if(fake) {
         atr[p];
         return;
      }
      p = atr[p];
      while(p < sz(tree)) tree[p] += x, p += lsb(p);
   }
   int query(int p) {
      if(fake) {
         //atr[p];
         return 0;
      }
      auto it = atr.upper_bound(p);
      if(it == atr.begin()) return 0;
      p = prev(it) -> second;
      int sum = 0;
      while(p > 0) sum += tree[p], p -= lsb(p);
      return sum;
   }
   
   void donefaking() {
      int cnt = 0;
      for(auto &[a, b] : atr) b = ++cnt;
      tree.assign(cnt + 2, 0);
      fake = 0;
      return;
   }
   AIB() { fake = 1; atr.clear(); tree.clear(); }
};

struct AIB2D {
   int n;
   AIB tree[nmax];
   void init(int n_) {
      n = n_ + 1;
   }
   int query(int l, int r) {
      int sum = 0;
      while(l < n) sum += tree[l].query(r), l += lsb(l);
      return sum;
   }
   void upd(int l, int r, int p) {
      while(l > 0) tree[l].upd(r, p), l -= lsb(l);
   }
   void donefaking() {
      for(int i = 1; i < n; i++) tree[i].donefaking();
   }
};

vector<pii> startsq[nmax], endsq[nmax];

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, q;
   cin >> n >> q;
   vector<pii> qs;
   
   string s, tmp;
   cin >> s;
   s = "#" + s;
   for(int i = 1; i <= n; i++) last[i] = 1;
   tmp = s;
   
   for(int i = 2; i <= q + 1; i++) {
      string act;
      cin >> act;
      if(act == "toggle") {
         int x;
         cin >> x;
         upds[x].emplace_back(last[x], i - 1, s[x] - '0');
         s[x] ^= '1' ^ '0';
         last[x] = i;
         qs.emplace_back(-1, x);
      }
      else {
         int l, r;
         cin >> l >> r;
         --r;
         qs.emplace_back(l, r);
      }
   }
   for(int i = 1; i <= n; i++) {
      upds[i].emplace_back(last[i], q + 1, s[i] - '0');
   }
   
   
   Beats::init(q + 1);
   for(int i = 1; i <= n; i++) {
      for(auto [u, d, type] : upds[i]) {
         if(type == 1) continue;
         Beats::set(u, d, i);
      }
   }
   Beats::set(1, q + 1, n + 1);
   
   for(auto &[l, r, u, d] : squares) {
      ++l, --r;
      startsq[u].emplace_back(l, r);
      endsq[d + 1].emplace_back(l, r);
   }
   
   AIB2D deja;
   deja.init(max(n, q) + 2);
   
   for(int step = 0; step < 2; step++) {
      s = tmp;
      int timer = 1;
      map<int, pii> opensq;
      
      auto effectuate = [&](int i) {
         for(auto [l, r] : endsq[i]) {
            if(opensq.count(l)) {
               deja.upd(r, l, i - opensq[l].second);
               opensq.erase(l);
            }
            else assert(false); //???
         }
         for(auto [l, r] : startsq[i])
            opensq[l] = make_pair(r, i);
         return;
      };
      
      effectuate(1);
      
      for(auto [l, r] : qs) {
         timer++;
         if(l == -1) {
            int x = r;
            s[x] ^= '1' ^ '0';
            rez[timer] = -1;
         }
         else {
            int standard = 0;
            if(s[l] == '0' || s[r] == '0');// cerr << "fail\n";
            else {
               auto it = opensq.upper_bound(l);
               assert(it != opensq.begin());
               it = prev(it);
               if(r <= it -> second.first)
                  standard += timer - it -> second.second;
            }
            rez[timer] = standard + deja.query(r, l);
         }
         if(timer != q + 1)
            effectuate(timer);
      }
      deja.donefaking();
   }
   
   for(int i = 2; i <= q + 1; i++) {
      if(rez[i] == -1) continue;
      cout << rez[i] << '\n';
   }
   return 0;
}

/**
      Binecuvanteaza Doamne Ukraina.
--
*/ 

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