Submission #1143742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143742		cadmiumsky	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	2512 ms	204292 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>;
#define assert kbjsadksja

string tmp;

void assert(bool ok) {
   if(!ok) {
      vector<int> v;
      v.emplace_back(9);
      while(1) v.resize(2 * sz(v), v.back() + sz(v));
   }
}

void myassert(bool ok) {
   if(!ok) {
      exit(-1);
   }
}

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, string s) {
      int lst = 1;
      for(int i = 1; i <= n; i++) {
         if(s[i] == '0') {
            if(i == lst);
            else {
               lends.emplace(lst);
               rend[lst] = i - 1;
               lval[lst] = 1;
            }
            lst = i + 1;
         }
      }
      if(lst <= n) {
         lends.emplace(lst);
         rend[lst] = n;
         lval[lst] = 1;
      }
   }
   
   void reset(int p, int timer) {
      auto it = lends.upper_bound(p);
      myassert(it != lends.begin());
      it = prev(it);
      //cerr << p << '\t' << *it << ' ' << rend[*it] << '\n';
      myassert(rend[*it] >= p);
      
      squares.emplace_back(*it, rend[*it], lval[*it], timer - 1);
      if(*it == p && rend[*it] == p)
         lends.erase(it);
      else if(*it == p && rend[*it] != p) {
         rend[p + 1] = rend[*it];
         lval[p + 1] = timer;
         lends.erase(*it);
         lends.emplace(p + 1);
      }
      else if(*it != p && rend[*it] == p) {
         rend[*it]--;
         lval[*it] = timer;
      }
      else if(*it != p && rend[*it] != p) {
         rend[p + 1] = rend[*it];
         rend[*it] = p - 1;
         lends.emplace(p + 1);
         lval[p + 1] = lval[*it] = timer;
      }
   }
   
   void set(int p, int timer) {
      auto nx = lends.upper_bound(p);
      int l = p, r = p;
      if(nx != lends.end()) {
         if(*nx == p + 1) {
            squares.emplace_back(*nx, rend[*nx], lval[*nx], timer - 1);
            r = rend[*nx];
            lends.erase(nx);
         }
      }
      auto prv = lends.upper_bound(p);
      if(prv != lends.begin()) {
         prv = prev(prv);
         if(rend[*prv] == p - 1) {
            squares.emplace_back(*prv, rend[*prv], lval[*prv], timer - 1);
            l = *prv;
            lends.erase(prv);
         }
         
      }
      lends.emplace(l);
      rend[l] = r;
      lval[l] = timer;
      return;
   }
   void liquidate(int T) {
      for(auto x : lends) {
         squares.emplace_back(x, rend[x], lval[x], T);
      }
   }
   void print() {
      //for(auto x : lends)
         //cerr << x << ", " << rend[x] << '\t';
      //cerr << '\n';
      
   }
}

#define lsb(x) (x & -x)

mt19937 rng(8283173);

template<typename T>
struct Treap {
   struct Node {
      Node *l, *r;
      int pri;
      T data;
   } *nil = new Node {0, 0, 0, T()};
   Treap() { nil -> l = nil -> r = nil; }
   
   using ns = Node*;
   struct pns { ns l, r; };
   
   ns updnode(ns node, ns x, int t) {
      (t == 0? node -> l : node -> r) = x;
      node -> data.pull(node -> l -> data, node -> r -> data);
      return node;
   }
   ns merge(ns l, ns r) {
      return l == nil? r:
               r == nil? l:
                  l -> pri > r -> pri? updnode(l, merge(l -> r, r), 1):
                     updnode(r, merge(l, r -> l), 0);
   }
   template<class CB> pns split(CB&& cb, ns node) { // here <= cst
      pns tmp;
      return node == nil? pns{nil, nil}:
               cb(node -> data)? (tmp = split(cb, node -> r), tmp.l = updnode(node, tmp.l, 1), tmp):
                  (tmp = split(cb, node -> l), tmp.r = updnode(node, tmp.r, 0), tmp);
   }
   
   ns root = nil;
};
struct Val {
   int poz;
   int sum, mine;
   void pull(const Val& x, const Val& y) { sum = x.sum + y.sum + mine; }
};

struct AIB : Treap<Val> {
   void upd(int p, int x) {
      auto [l, r] = split([&](Val& a) { return a.poz <= p; }, root);
      root = merge(l, merge(new Node{nil, nil, rng(), Val{p, x, x}}, r));
   }
   int query(int p) {
      auto [l, r] = split([&](Val& a) { return a.poz <= p; }, root);
      int rnv = l -> data.sum;
      root = merge(l, r);
      return rnv;
   }
};

struct AIB2D {
   int n;
   AIB tree[nmax];
   void init(int n_) {
      n = n_ + 1;
      //for(int i = 1; i < n; i++) tree[i].N = n;
   }
   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;
   cin >> s;
   s = "#" + s;
   for(int i = 1; i <= n; i++) last[i] = 1;
   tmp = s;
   
   Beats::init(n, s);
   for(int i = 2; i <= q + 1; i++) {
      string act;
      cin >> act;
      Beats::print();
      //cerr << act << '\n';
      if(act == "toggle") {
         int x;
         cin >> x;
         if(s[x] == '1') Beats::reset(x, i);
         else Beats::set(x, i);
         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);
      }
   }
   
   
   Beats::liquidate(q + 1);
   //cerr << "---\n";
   for(auto &[l, r, u, d] : squares) {
      //cerr << l << ' ' << r << '\t' << u << ' ' << d << '\n';
      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 < 1; 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.
--
*/ 

Compilation message (stderr)

street_lamps.cpp:16: warning: "assert" redefined
   16 | #define assert kbjsadksja
      | 
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from street_lamps.cpp:3:
/usr/include/assert.h:92: note: this is the location of the previous definition
   92 | #  define assert(expr)                                                  \
      | 
street_lamps.cpp: In member function 'void AIB::upd(int, int)':
street_lamps.cpp:178:51: warning: narrowing conversion of 'rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  178 |       root = merge(l, merge(new Node{nil, nil, rng(), Val{p, x, x}}, r));
      |                                                ~~~^~

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