Submission #973208

#	Time	Username	Problem	Language	Result	Execution time	Memory
973208		vjudge1	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	1474 ms	203848 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=3e5+10, inf=1e18;;

struct BIT2d{
   int n;
   vector<pair<int, pair<int, int>>> t[N];
   void init(int _n){
      n=_n;
      for (int i=1; i<=n; ++i) t[i].push_back({-1, {0, 0}});
   }
   void fake_update(int x, int y){
      for (int i=x; i<=n; i+=i&(-i)) t[i].push_back({y, {0, 0}});
   }
   void compress(){
      for (int i=1; i<=n; ++i){
         sort(t[i].begin(), t[i].end());
         t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
      }
   }
   void update(int x, int y, int t1, int t2){
      if (x>n || y>n) return;
      for (int i=x; i<=n; i+=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, make_pair(-inf, -inf)))-t[i].begin(); j<(int)t[i].size(); j+=j&(-j)){
            t[i][j].second.first+=t1;
            t[i][j].second.second+=t2;
         }
      }
   }
   pair<int, int> get(int x, int y){
      pair<int, int> ans={0, 0};
      for (int i=x; i; i-=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y+1, make_pair(-inf, -inf)))-t[i].begin()-1; j; j-=j&(-j)){
            ans.first+=t[i][j].second.first;
            ans.second+=t[i][j].second.second;
         }
      }
      return ans;
   }
};

struct Event{
   int lx, rx, ly, ry, idx;
   Event (int _lx=0, int _rx=0, int _ly=0, int _ry=0, int _idx=0){
      lx=_lx, rx=_rx, ly=_ly, ry=_ry, idx=_idx;
   }
   bool operator<(const Event &b){
      if (rx==b.rx) return idx<b.idx;
      return rx>b.rx;
   }
};

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 tr, int l, int r){
      int tl=mp[{l, r}];
      v.emplace_back(l, r, tl, tr);
      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, r, 1, i-1, i);
      }
   }
   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());
   BIT2d bit;
   bit.init(N-1);
   for (auto &i:v){
      if (i.idx==0){
         bit.fake_update(i.lx, i.ly);
         bit.fake_update(i.lx, i.ry);
      }
   }
   bit.compress();
   for (auto &i:v){
      if (i.idx==0){
         // cout << "update " << i.lx << ' ' << i.ly << ' ' << 1 << ' ' << -i.ly+1 << '\n';
         // cout << "update " << i.lx << ' ' << i.ry << ' ' << -1 << ' ' << i.ry << '\n';
         bit.update(i.lx, i.ly, 1, -i.ly+1);
         bit.update(i.lx, i.ry, -1, i.ry);
      }else{
         // cout << "query " << i.lx << ' ' << i.ry << '\n';
         auto tmp=bit.get(i.lx, i.ry);
         ans[i.idx]=tmp.first*i.ry+tmp.second;
      }
   }
   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