oj.uz

Submission #333395

# Submission time Handle Problem Language Result Execution time Memory
333395 2020-12-05T19:57:22 Z NaimSS Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1644 ms 83016 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]);
        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.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 16876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 431 ms 41496 KB Output isn't correct
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 13 ms 17132 KB Output is correct
4 Correct 12 ms 17004 KB Output is correct
5 Correct 1408 ms 80516 KB Output is correct
6 Correct 1631 ms 83016 KB Output is correct
7 Correct 1644 ms 78724 KB Output is correct
8 Correct 313 ms 64056 KB Output is correct
9 Correct 308 ms 50112 KB Output is correct
10 Correct 339 ms 50808 KB Output is correct
11 Correct 318 ms 53676 KB Output is correct
12 Correct 176 ms 34256 KB Output is correct
13 Correct 302 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 Correct 12 ms 17004 KB Output is correct
3 Correct 12 ms 17132 KB Output is correct
4 Correct 14 ms 17132 KB Output is correct
5 Correct 1042 ms 69496 KB Output is correct
6 Correct 1197 ms 72648 KB Output is correct
7 Correct 1372 ms 77068 KB Output is correct
8 Correct 1487 ms 80764 KB Output is correct
9 Incorrect 581 ms 42392 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 16876 KB Output isn't correct
2 Halted 0 ms 0 KB -