oj.uz

Submission #401889

# Submission time Handle Problem Language Result Execution time Memory
401889 2021-05-11T00:19:09 Z kai824 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define eb emplace_back
#define mp make_pair
typedef pair<int,int> pii;
#define f first
#define s second
 
#ifdef local
#define debug(x,label) cerr<<"DEBUG "<<label<<" "<<x<<'\n';
#else
#define debug(x,label);
#endif
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
 
//const int mod=1000000007 or 998244353;
 
int n,q;
unordered_map<int,int> ft[300005];
#define ls(x) (x&(-x))
void update(int a,int b,int upd){b++;
  //cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
  for(;a<=n;a+=ls(a)){
    for(int x=b;x<=n;x+=ls(x)){
      if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
      else ft[a][x]+=upd;
    }
  }
}
int query(int a,int b){b++;
  int ans=0;
  for(;a;a-=ls(a)){
    for(int x=b;x;x-=ls(x)){
      //if(ft[a].find(x)==ft[a].end())continue;
      ans+=ft[a][x];
    }
  }
  return ans;
}
 
bool lam[300005];
 
int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int prev=0,ans,a,b,c,d;
  cin>>n>>q;
  string s;
  cin>>s;
  set<pair<pii,int> > cur;//"cur ranges"
  set<pair<pii,int> >::iterator it;
  for(int i=0;i<n;i++){
    if(s[i]=='0'){
      if(prev<=i-1){
        cur.insert(mp(mp(prev+1,i),0));
      }
      prev=i+1;
    }
    lam[i+1]=(s[i]=='1');
  }
  if(prev<=n-1){
    cur.insert(mp(mp(prev+1,n),0));
  }
 
  for(int i=1;i<=q;i++){
    cin>>s;
    if(s[0]=='t'){
      cin>>a;
      if(lam[a]){
        it=--cur.upper_bound(mp(mp(a,INT_MAX),-1));
        b=it->f.f;c=it->f.s;//range b to c...
        update(b,n-c,i-it->s);
        cur.erase(it);
        if(b<a)cur.insert(mp(mp(b,a-1),i));
        if(a<c)cur.insert(mp(mp(a+1,c),i));
      }else{
        b=c=a;
        if(lam[a-1]){
          it=--cur.upper_bound(mp(mp(a-1,INT_MAX),-1));
          b=it->f.f;
          update(it->f.f,n-it->f.s,i-it->s);
          cur.erase(it);
        }
        if(lam[a+1]){
          it=--cur.upper_bound(mp(mp(a+1,INT_MAX),-1));
          c=it->f.s;
          update(it->f.f,n-it->f.s,i-it->s);
          cur.erase(it);
        }
        cur.insert(mp(mp(b,c),i));
      }
      lam[a]^=1;
    }else{
      ans=0;
      cin>>a>>b;b--;
      it=cur.upper_bound(mp(mp(a,INT_MAX),-1));
      if(it!=cur.begin()){
        it--;
        if(it->f.f<=a && b<=it->f.s){
          ans+=(i-it->s);
        }
      }
      ans+=query(a,n-b);//if first index >=a, then n-first index<=n-a
      cout<<ans<<'\n';
    }
  }
  return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:48:24: warning: unused variable 'd' [-Wunused-variable]
   48 |   int prev=0,ans,a,b,c,d;
      |                        ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16716 KB Output is correct
2 Correct 12 ms 16716 KB Output is correct
3 Correct 12 ms 16760 KB Output is correct
4 Correct 13 ms 16756 KB Output is correct
5 Correct 12 ms 16696 KB Output is correct
6 Correct 11 ms 16664 KB Output is correct
7 Correct 12 ms 16716 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 20876 KB Output is correct
2 Correct 328 ms 21480 KB Output is correct
3 Correct 648 ms 27296 KB Output is correct
4 Correct 4803 ms 267048 KB Output is correct
5 Execution timed out 5031 ms 287724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17100 KB Output is correct
2 Correct 15 ms 17228 KB Output is correct
3 Correct 14 ms 17428 KB Output is correct
4 Correct 14 ms 17352 KB Output is correct
5 Correct 4484 ms 217848 KB Output is correct
6 Execution timed out 5075 ms 353608 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17356 KB Output is correct
2 Correct 14 ms 17284 KB Output is correct
3 Correct 14 ms 17228 KB Output is correct
4 Correct 13 ms 17056 KB Output is correct
5 Execution timed out 5100 ms 524288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16716 KB Output is correct
2 Correct 12 ms 16716 KB Output is correct
3 Correct 12 ms 16760 KB Output is correct
4 Correct 13 ms 16756 KB Output is correct
5 Correct 12 ms 16696 KB Output is correct
6 Correct 11 ms 16664 KB Output is correct
7 Correct 12 ms 16716 KB Output is correct
8 Correct 200 ms 20876 KB Output is correct
9 Correct 328 ms 21480 KB Output is correct
10 Correct 648 ms 27296 KB Output is correct
11 Correct 4803 ms 267048 KB Output is correct
12 Execution timed out 5031 ms 287724 KB Time limit exceeded
13 Halted 0 ms 0 KB -