Submission #972920

#	Time	Username	Problem	Language	Result	Execution time	Memory
972920		vjudge1	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	325 ms	37600 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

struct Node{
   int x, y;
   int lx, ly;
   Node (int _x=0, int _y=0, int _lx=0, int _ly=0){
      x=_x, y=_y, lx=_lx, ly=_ly;
   }
   Node operator+(const Node &b){
      return Node(x+b.x, y+b.y);
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int l, int r, int x, int y){
      t[k].x+=(r-l+1)*x;
      t[k].y+=(r-l+1)*y;
      t[k].lx+=x;
      t[k].ly+=y;
   }
   void push(int k, int l, int r){
      if (t[k].lx || t[k].ly){
         int mid=(l+r)>>1;
         apply(k<<1, l, mid, t[k].lx, t[k].ly);
         apply(k<<1|1, mid+1, r, t[k].lx, t[k].ly);
         t[k].lx=t[k].ly=0;
      }
   }
   void add(int k, int l, int r, int L, int R, int x, int y){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, l, r, x, y);
         return;
      }
      push(k, l, r);
      int mid=(l+r)>>1;
      add(k<<1, l, mid, L, R, x, y);
      add(k<<1|1, mid+1, r, L, R, x, y);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   Node get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return t[0];
      if (L<=l && r<=R) return t[k];
      push(k, l, r);
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R)+get(k<<1|1, mid+1, r, L, R);
   }
} seg;

struct Event{
   int x;
   int ly, ry;
   int tx, ty;
   Event (int _x=0, int _ly=0, int _ry=0, int _tx=0, int _ty=0){
      x=_x, ly=_ly, ry=_ry, tx=_tx, ty=_ty;
   }
   bool operator<(const Event &b){
      if (x==b.x){
         if (abs(tx+ty)==abs(b.tx+b.ty)) return ly<b.ly;
         return abs(tx+ty)>abs(b.tx+b.ty);
      }
      return x<b.x;
   }
};

const int N=3e5+10;
int n, q, ans[N], is_query[N];
string s;

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   vector<Event> v;
   set<pair<int, int>> st;
   map<pair<int, int>, int> mp;
   cin >> n >> q >> s;
   auto insert=[&](int t, int l, int r){
      mp[{l, r}]=t;
      st.emplace(l, r);
   };
   auto erase=[&](int t, int l, int r){
      int tt=mp[{l, r}];
      v.emplace_back(l, tt, t, 1, 0);
      v.emplace_back(r+1, tt, t, 0, -1);
      st.erase({l, r});
      mp.erase({l, r});
   };
   s=" "+s;
   for (int i=1; i<=n; ++i) if (s[i]=='1'){
      int j=i;
      while (j<n && s[j+1]=='1') ++j;
      insert(1, i, j);
      i=j;
   }
   for (int i=2; i<=q+1; ++i){
      string type; cin >> type;
      if (type[0]=='t'){
         int x; cin >> x;
         if (s[x]=='0'){
            if (st.empty()){
               insert(i, x, x);
            }else{
               auto it=st.lower_bound({x, x});
               int l=x, r=x;
               if (it!=st.end() && x+1==it->first){
                  r=it->second;
                  erase(i, it->first, it->second);
                  it=st.lower_bound({x, x});
               }
               if (it!=st.begin() && (--it)->second==l-1){
                  l=it->first;
                  erase(i, it->first, it->second);
               }
               insert(i, l, r);
            }
         }else{
            auto it=st.lower_bound({x, (int)1e9}); --it;
            int l=it->first, r=it->second;
            erase(i, l, r);
            if (l!=x) insert(i, l, x-1);
            if (r!=x) insert(i, x+1, r);
         }
         s[x]^=1;
      }else{
         is_query[i]=1;
         int l, r; cin >> l >> r; --r;
         v.emplace_back(l, -i, -i, 0, 0);
         v.emplace_back(r, i, i, 0, 0);
      }
   }
   vector<pair<int, int>> tmp(st.begin(), st.end());
   for (auto &i:tmp) erase(q+2, i.first, i.second);
   sort(v.begin(), v.end());
   seg.init(q+2);
   for (auto &i:v){
      if (abs(i.tx+i.ty)){
         seg.add(1, 1, seg.n, i.ly, i.ry, i.tx, i.ty);
      }else{
         if (i.ly<0){
            ans[-i.ly]=seg.get(1, 1, seg.n, 1, -i.ly-1).x;
         }else{
            ans[i.ly]+=seg.get(1, 1, seg.n, 1, i.ly-1).y;
         }
      }
   }
   for (int i=2; i<=q+1; ++i) if (is_query[i]) cout << ans[i] << '\n';
   return 0;
}

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