Submission #333395

#	Time	Username	Problem	Language	Result	Execution time	Memory
333395		NaimSS	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	1644 ms	83016 KiB

street_lamps

#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
#define int long long  
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; g(...) 0
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
    if (e & 1) ans = ans * b % m;
  return ans;
}

template<class T, int SZ> struct OffBIT2D { 
  bool mode = 0; // mode = 1 -> initialized
  vector<pii> todo; // locations of updates to process
  int cnt[SZ], st[SZ];
  vi val; vector<T> bit; // store all BITs in single vector
  void init() { assert(!mode); mode = 1;
    int lst[SZ]; 
    rep(i,0,SZ) lst[i] = cnt[i] = 0;
    sort(all(todo),[](const pii& a, const pii& b) { 
      return a.ss < b.ss; });
    trav(t,todo) for (int x = t.ff; x < SZ; x += x&-x) {
          if (lst[x] != t.ss) lst[x] = t.ss, cnt[x] ++;
    }

    int sum = 0; rep(i,0,SZ) lst[i] = 0, st[i] = (sum += cnt[i]);
    val.resize(sum); bit.resize(sum); reverse(all(todo));
    trav(t,todo) for (int x = t.ff; x < SZ; x += x&-x) 
      if (lst[x] != t.ss) lst[x] = t.ss, val[--st[x]] = t.ss;
  }
  int rank(int y, int l, int r) {
    return upper_bound(begin(val)+l,begin(val)+r,y)-begin(val)-l; }
  void UPD(int x, int y, T t) {
    for (y = rank(y,st[x],st[x]+cnt[x]); y <= cnt[x]; y += y&-y) 
      bit[st[x]+y-1] += t; }
  void upd(int x, int y, T t) { 
    if (!mode) todo.pb({x,y});
    else for (;x<SZ;x+=x&-x) UPD(x,y,t); }
  int QUERY(int x, int y) { T res = 0;
    for (y = rank(y,st[x],st[x]+cnt[x]); y; y -= y&-y) res += bit[st[x]+y-1];
    return res; }
  T query(int x, int y) { assert(mode);
    T res = 0; for (;x;x-=x&-x) res += QUERY(x,y);
    return res; }
  T query(int xl, int xr, int yl, int yr) { 
    return query(xr,yr)-query(xl-1,yr)
      -query(xr,yl-1)+query(xl-1,yl-1); }
};


struct event{
  int l,r,mx,v;
};


OffBIT2D<ll,300100> BIT;

vector<event> ev;

int n,q;
void add_event(int l,int r,int mx,ll v,int A=0){
  BIT.upd(l,mx,v);
  if(r!=n)BIT.upd(r+1,mx,-v);
  if(!A)ev.pb({l,r,mx,v});
}

ll ask(int a,int b,int A=0){
  ll res=0;
  if(!A)ev.pb({a,b,-1,-1});
  else{
    res = BIT.query(1,a,b,n);
  }
  return res;
}

const int N = 300100;
char s[N];

int fim[N];

int last[N];
string Q[N];
int a[N],b[N];


int32_t main(){
  fastio;
  cin >> n >> q;
  for(int i=1;i<=n;i++){
    cin >> s[i];
  }
  s[0]='0';
  set<pii> S;
  s[n+1]='0';
  for(int i=n;i>=0;i--){
    last[i] = 0;
    if(s[i] =='1'){
      if(s[i+1]=='1')fim[i] = fim[i+1];
      else{
        fim[i] = i;
      }
      continue;
    }
    if(s[i+1]=='1'){
      S.insert(pii(i+1,fim[i+1]));
    }
  }
  
  for(int ii=1;ii<=q;ii++){
    cin >> Q[ii];
    if(Q[ii][0]=='t'){
      cin >> a[ii];
      int pos = a[ii];
      if(s[pos] == '0'){
        s[pos] ='1';
        int l = pos,r = pos;
        if(s[pos-1]=='1'){
          auto it = S.lower_bound(pii(pos,-1));
          assert(it!=S.begin());
          it--;
          l = it->ff;
          add_event(it->ff,it->ss,it->ss,ii-last[it->ff]);
          last[it->ff] = ii;
          S.erase(it);
        }
        if(s[pos+1]=='1'){
          auto it = S.lower_bound(pii(pos,-1));
          assert(it!=S.end());
          r=it->ss;
          add_event(it->ff,it->ss,it->ss,ii-last[it->ff]);
          last[it->ff] = ii;
          S.erase(it);
        }
        S.insert(pii(l,r));
        last[l] = ii;
        
        int A = pos,B = pos;
        while(s[A]=='1')A--;
        while(s[B]=='1')B++;
        A++,B--;
        assert(A == l and B == r);
        
       // db2(l,r);
      }else{

        s[pos]='0';
        auto it = S.lower_bound(pii(pos+1,-1));
        assert(it!=S.begin());
        it--;
        int t = last[it->ff];
        int l = it->ff,r = it->ss;
        


        if(pos!=r)
          last[pos+1] = t;
        add_event(l,r,it->ss,ii-last[it->ff]);
        S.erase(it);
        last[l] = ii;
        if(pos!=l)S.insert(pii(l,pos-1));
        if(pos!=r)S.insert(pii(pos+1,r));
      }

    }else{
      cin >> a[ii] >> b[ii];
      b[ii]--;
      if(s[a[ii]] == '0'){
        ask(a[ii],b[ii]);
       // cout << "HI "<<a[i] << endl;
        continue;
      }
      auto it = S.lower_bound(pii(a[ii]+1,-1));
      if(it == S.begin())while(1);
      //assert(it!=S.begin());
      it--;
      add_event(it->ff,it->ss,it->ss,ii-last[it->ff]);
      //cout << "HI "<<it->ff<<" "<<it->ss<<" "<<last[it->ff] << endl;
      last[it->ff] = ii;
      ask(a[ii],b[ii]);
    }
  }
  BIT.init();

  for(auto it : ev){
    //cout << it.l<<" "<<it.r<<" "<<it.mx<<" "<<it.v << endl;
    if(it.mx != -1){
      add_event(it.l,it.r,it.mx,it.v,1);
    }else{
      cout << ask(it.l,it.r,1) << endl;
    }
  }

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

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