Submission #1105279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105279		ntdaccode	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2511 ms	227308 KiB

street_lamps

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=3e5+10;
const int N=1e3+10;
const int mod=1e9+7;
int n,q,a[M],b[M];
string tt[M];
int s[M];
// bit 1 chieu
int T[M];
void upd(int idx,int val)
{
  while(idx<=n)
  {
    T[idx]+=val;
    idx+=idx&(-idx);
  }
}
int get(int idx)
{
  int res=0;
  while(idx>0) {
    res+=T[idx];
    idx-=idx&(-idx);
  }
  return res;
}
int findl(int idx)
{
  int l=1,r=idx-1,ret=idx;
  while(l<=r) {
    int mid=(l+r)/2;
    //cout << idx << " " << mid << " " << get(idx)-get(mid-1) << " " << idx-mid+1 << "\n";
    if(get(idx)-get(mid-1)==idx-mid+1) {
      r=mid-1;
      ret=mid;
    }
    else l=mid+1;
  }
  return ret;
}
int findr(int idx)
{
  int l=idx+1,r=n,ret=idx;
  while(l<=r) {
    int mid=(l+r)/2;
    //cout << idx << " " << mid << " " << get(mid)-get(idx-1) << " " << mid-idx+1 << "\n";
    if(get(mid)-get(idx-1)==mid-idx+1) {
      l=mid+1;
      ret=mid;
    }
    else r=mid-1;
  }
  return ret;
}
// fake
vector<int> pos[M];
vector<int> bit[M];
void fake_upd2(int u,int v)
{
  while(u<=n) {
    pos[u].pb(v);
    u+=u&(-u);
  }
}
void fake_get2(int u,int v)
{
  while(u>0) {
    pos[u].pb(v);
    u-=u&(-u);
  }
}
void fake_sqrt2(int u,int v)
{
  fake_upd2(u,u);
  fake_upd2(v+1,u);
  fake_upd2(u,v+1);
  fake_upd2(v+1,v+1);

}
int tmps[M];
void fake_solve()
{
  fori(i,1,n) tmps[i]=s[i];
  fori(i,1,n) if(tmps[i]) upd(i,1);
  fori(i,1,q) {
    if(tt[i]=="toggle") {
        int idx=a[i];
      if(tmps[idx]) { //tach

        int l=findl(idx);
        int r=findr(idx);
        upd(idx,-1);
        tmps[idx]=0;

        fake_sqrt2(l,r+1);//->l,r;
      }
      else { // hop
        upd(idx,1);
        tmps[idx]=1;
        int l=findl(idx);
        int r=findr(idx);
        if(l!=idx) fake_sqrt2(l,idx);//->l,i-1
        if(r!=idx) fake_sqrt2(idx+1,r+1);//->i+1,r
      }
    }
    else {
      cin >> a[i] >> b[i];
      fake_get2(a[i],b[i]);// a[i],b[i]
    }
  }
  fori(i,1,n+1) {
    pos[i].pb(0);
    sort(pos[i].begin(),pos[i].end());
    pos[i].resize(unique(pos[i].begin(),pos[i].end())-pos[i].begin());
    bit[i].assign(pos[i].size(),0);
  }
  fori(i,1,n) T[i]=0;
}
// bit 2 chieu
void upd2(int u,int v,int val)
{
  for(int i=u;i<=n+1;i+=i&(-i)) {
    for(int j=lower_bound(pos[i].begin(),pos[i].end(),v)-pos[i].begin();j<pos[i].size();j+=j&(-j)) {
      bit[i][j]+=val;
    }
  }
}
int get2(int u,int v) {
  int res=0;
  for(int i=u;i>0;i-=i&(-i)) {
    for(int j=lower_bound(pos[i].begin(),pos[i].end(),v)-pos[i].begin();j>0;j-=j&(-j))
      res+=bit[i][j];
  }
  return res;
}
// segment tree
int t[4*M],lz[4*M];
void lazy(int s)
{
  t[s*2]=lz[s];
  t[s*2+1]=lz[s];
  lz[s*2]=lz[s];
  lz[s*2+1]=lz[s];
  lz[s]=0;
  return ;
}
void upd_seg(int s,int l,int r,int u,int v,int val)
{
  if(l>v||r<u) return ;
  if(u<=l&&r<=v)
  {
    t[s]=val;
    lz[s]=val;
    return ;
  }
  int mid=(l+r)/2;
  if(l!=r&&lz[s]) lazy(s);
  upd_seg(s*2,l,mid,u,v,val);
  upd_seg(s*2+1,mid+1,r,u,v,val);
  t[s]=max(t[s*2],t[s*2+1]);
}
int get_seg(int s,int l,int r,int u,int v)
{
  if(l>v||r<u) return 0;
  if(u<=l&&r<=v) return t[s];
  int mid=(l+r)/2;
  if(l!=r&&lz[s]) lazy(s);
  return max(get_seg(s*2,l,mid,u,v),get_seg(s*2+1,mid+1,r,u,v));
}
//
void sqrt2(int u,int v,int val)
{
  upd2(u,u,val);
  upd2(v+1,u,-val);
  upd2(u,v+1,-val);
  upd2(v+1,v+1,val);
}

void solve(){
  fori(i,1,n) if(s[i]) upd(i,1);
  fori(i,1,q) {
    if(tt[i]=="toggle") {
        int idx=a[i];
      if(s[idx]) { //tach
        int l=findl(idx);
        int r=findr(idx);
        upd(idx,-1);
        s[idx]=0;
        int pre=get_seg(1,1,n,l,r);
        sqrt2(l,r+1,i-pre);//->l,r;

        if(idx!=l) upd_seg(1,1,n,l,idx-1,i);
        if(idx!=r) upd_seg(1,1,n,idx+1,r,i);

      }
      else { // hop
        upd(idx,1);
        s[idx]=1;
        int l=findl(idx);
        int r=findr(idx);
        if(l!=idx) {
          int pre=get_seg(1,1,n,l,idx-1);
          sqrt2(l,idx,i-pre);//->l,i-1
        }
        if(r!=idx) {

          int pre=get_seg(1,1,n,idx+1,r);
          sqrt2(idx+1,r+1,i-pre);
        }
        //fori(i,1,n) fori(j,i,n) cout << i << " " << j << " " << get(j)-get(i-1) << "\n";
        //cout << l << " " << r << "\n";
        upd_seg(1,1,n,l,r,i);
      }
    }
    else {
      cin >> a[i] >> b[i];
      int x=0;
      //cout << get(b[i]-1)-get(a[i]-1) << " " << b[i]-a[i] << " ";
      if(get(b[i]-1)-get(a[i]-1)==b[i]-a[i]) x=i-get_seg(1,1,n,a[i],b[i]-1);
      cout << get2(a[i],b[i])+x << "\n";// a[i],b[i]
    }
  }
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }
  cin >> n >> q;
  fori(i,1,n) {
    char ch;
    cin >> ch;
    s[i]=ch-'0';
  }
  fori(i,1,q) {
    cin >> tt[i];
    if(tt[i]=="toggle") cin >> a[i];
    else cin >> a[i] >> b[i];
  }
  fake_solve();
  solve();
}

Compilation message (stderr)

street_lamps.cpp: In function 'void upd2(long long int, long long int, long long int)':
street_lamps.cpp:130:74: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int j=lower_bound(pos[i].begin(),pos[i].end(),v)-pos[i].begin();j<pos[i].size();j+=j&(-j)) {
      |                                                                         ~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:238:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:239:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:244:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:245:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  245 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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