oj.uz

Submission #333393

# Submission time Handle Problem Language Result Execution time Memory
333393 2020-12-05T19:54:56 Z NaimSS Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1720 ms 83192 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{

        int A = pos,B = pos;
        while(s[A]=='1')A--;
        while(s[B]=='1')B++;
        A++,B--;
        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;
        
        assert(A == l and B == r);

        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 24 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 19564 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 13 ms 17132 KB Output is correct
2 Correct 13 ms 17132 KB Output is correct
3 Correct 14 ms 17132 KB Output is correct
4 Correct 13 ms 17004 KB Output is correct
5 Correct 1468 ms 80540 KB Output is correct
6 Correct 1720 ms 83192 KB Output is correct
7 Correct 1702 ms 78660 KB Output is correct
8 Correct 328 ms 64056 KB Output is correct
9 Correct 327 ms 50092 KB Output is correct
10 Correct 336 ms 50680 KB Output is correct
11 Correct 336 ms 53676 KB Output is correct
12 Correct 173 ms 34236 KB Output is correct
13 Correct 317 ms 64056 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17004 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 24 ms 19564 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -