oj.uz

Submission #401446

# Submission time Handle Problem Language Result Execution time Memory
401446 2021-05-10T09:31:27 Z kai824 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 462324 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;
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 11 ms 14284 KB Output is correct
2 Correct 11 ms 14408 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Correct 10 ms 14412 KB Output is correct
5 Correct 9 ms 14408 KB Output is correct
6 Correct 10 ms 14412 KB Output is correct
7 Correct 9 ms 14364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 18684 KB Output is correct
2 Correct 427 ms 19112 KB Output is correct
3 Correct 1233 ms 25272 KB Output is correct
4 Execution timed out 5041 ms 267636 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14796 KB Output is correct
2 Correct 14 ms 14996 KB Output is correct
3 Correct 15 ms 15052 KB Output is correct
4 Correct 13 ms 14948 KB Output is correct
5 Execution timed out 5076 ms 215184 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15072 KB Output is correct
2 Correct 13 ms 14936 KB Output is correct
3 Correct 12 ms 14940 KB Output is correct
4 Correct 12 ms 14756 KB Output is correct
5 Execution timed out 5081 ms 462324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14284 KB Output is correct
2 Correct 11 ms 14408 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Correct 10 ms 14412 KB Output is correct
5 Correct 9 ms 14408 KB Output is correct
6 Correct 10 ms 14412 KB Output is correct
7 Correct 9 ms 14364 KB Output is correct
8 Correct 259 ms 18684 KB Output is correct
9 Correct 427 ms 19112 KB Output is correct
10 Correct 1233 ms 25272 KB Output is correct
11 Execution timed out 5041 ms 267636 KB Time limit exceeded
12 Halted 0 ms 0 KB -