oj.uz

Submission #333394

# Submission time Handle Problem Language Result Execution time Memory
333394 2020-12-05T19:55:58 Z NaimSS Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1663 ms 83188 KB 
#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]);
        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.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 19564 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 19692 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17132 KB Output is correct
2 Correct 14 ms 17152 KB Output is correct
3 Correct 13 ms 17132 KB Output is correct
4 Correct 12 ms 17004 KB Output is correct
5 Correct 1435 ms 80652 KB Output is correct
6 Correct 1615 ms 83188 KB Output is correct
7 Correct 1663 ms 78660 KB Output is correct
8 Correct 297 ms 64056 KB Output is correct
9 Correct 318 ms 50092 KB Output is correct
10 Correct 330 ms 50808 KB Output is correct
11 Correct 327 ms 53828 KB Output is correct
12 Correct 180 ms 34236 KB Output is correct
13 Correct 300 ms 64056 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16964 KB Output is correct
2 Runtime error 19 ms 19692 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 19564 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -