oj.uz

Submission #401893

# Submission time Handle Problem Language Result Execution time Memory
401893 2021-05-11T00:35:47 Z kai824 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4343 ms 517820 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)
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
typedef gp_hash_table<int, int, chash> ht;
 
//const int mod=1000000007 or 998244353;
 
int n,q;
ht 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:58:24: warning: unused variable 'd' [-Wunused-variable]
   58 |   int prev=0,ans,a,b,c,d;
      |                        ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 63684 KB Output is correct
2 Correct 62 ms 63704 KB Output is correct
3 Correct 66 ms 63656 KB Output is correct
4 Correct 65 ms 63656 KB Output is correct
5 Correct 71 ms 63724 KB Output is correct
6 Correct 67 ms 63716 KB Output is correct
7 Correct 70 ms 63624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 64708 KB Output is correct
2 Correct 261 ms 64900 KB Output is correct
3 Correct 457 ms 69556 KB Output is correct
4 Correct 2535 ms 279596 KB Output is correct
5 Correct 2844 ms 292204 KB Output is correct
6 Correct 2411 ms 287316 KB Output is correct
7 Correct 1584 ms 181596 KB Output is correct
8 Correct 1507 ms 182956 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 63940 KB Output is correct
2 Correct 72 ms 64064 KB Output is correct
3 Correct 73 ms 64156 KB Output is correct
4 Correct 72 ms 64012 KB Output is correct
5 Correct 2502 ms 218804 KB Output is correct
6 Correct 3658 ms 364420 KB Output is correct
7 Correct 4343 ms 473588 KB Output is correct
8 Correct 3407 ms 512788 KB Output is correct
9 Correct 196 ms 64836 KB Output is correct
10 Correct 170 ms 64672 KB Output is correct
11 Correct 175 ms 64872 KB Output is correct
12 Correct 3447 ms 512156 KB Output is correct
13 Correct 3513 ms 513480 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 64068 KB Output is correct
2 Correct 73 ms 64128 KB Output is correct
3 Correct 72 ms 64032 KB Output is correct
4 Correct 73 ms 63804 KB Output is correct
5 Correct 3800 ms 517820 KB Output is correct
6 Correct 3563 ms 474412 KB Output is correct
7 Correct 3097 ms 387880 KB Output is correct
8 Correct 2239 ms 201356 KB Output is correct
9 Correct 261 ms 67032 KB Output is correct
10 Correct 216 ms 63956 KB Output is correct
11 Correct 266 ms 67136 KB Output is correct
12 Correct 218 ms 63932 KB Output is correct
13 Correct 261 ms 67132 KB Output is correct
14 Correct 215 ms 63912 KB Output is correct
15 Correct 3473 ms 510732 KB Output is correct
16 Correct 3529 ms 511904 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 63684 KB Output is correct
2 Correct 62 ms 63704 KB Output is correct
3 Correct 66 ms 63656 KB Output is correct
4 Correct 65 ms 63656 KB Output is correct
5 Correct 71 ms 63724 KB Output is correct
6 Correct 67 ms 63716 KB Output is correct
7 Correct 70 ms 63624 KB Output is correct
8 Correct 218 ms 64708 KB Output is correct
9 Correct 261 ms 64900 KB Output is correct
10 Correct 457 ms 69556 KB Output is correct
11 Correct 2535 ms 279596 KB Output is correct
12 Correct 2844 ms 292204 KB Output is correct
13 Correct 2411 ms 287316 KB Output is correct
14 Correct 1584 ms 181596 KB Output is correct
15 Correct 1507 ms 182956 KB Output is correct
16 Correct 70 ms 63940 KB Output is correct
17 Correct 72 ms 64064 KB Output is correct
18 Correct 73 ms 64156 KB Output is correct
19 Correct 72 ms 64012 KB Output is correct
20 Correct 2502 ms 218804 KB Output is correct
21 Correct 3658 ms 364420 KB Output is correct
22 Correct 4343 ms 473588 KB Output is correct
23 Correct 3407 ms 512788 KB Output is correct
24 Correct 196 ms 64836 KB Output is correct
25 Correct 170 ms 64672 KB Output is correct
26 Correct 175 ms 64872 KB Output is correct
27 Correct 3447 ms 512156 KB Output is correct
28 Correct 3513 ms 513480 KB Output is correct
29 Correct 71 ms 64068 KB Output is correct
30 Correct 73 ms 64128 KB Output is correct
31 Correct 72 ms 64032 KB Output is correct
32 Correct 73 ms 63804 KB Output is correct
33 Correct 3800 ms 517820 KB Output is correct
34 Correct 3563 ms 474412 KB Output is correct
35 Correct 3097 ms 387880 KB Output is correct
36 Correct 2239 ms 201356 KB Output is correct
37 Correct 261 ms 67032 KB Output is correct
38 Correct 216 ms 63956 KB Output is correct
39 Correct 266 ms 67136 KB Output is correct
40 Correct 218 ms 63932 KB Output is correct
41 Correct 261 ms 67132 KB Output is correct
42 Correct 215 ms 63912 KB Output is correct
43 Correct 3473 ms 510732 KB Output is correct
44 Correct 3529 ms 511904 KB Output is correct
45 Correct 134 ms 64216 KB Output is correct
46 Correct 176 ms 64108 KB Output is correct
47 Correct 1688 ms 228324 KB Output is correct
48 Correct 3551 ms 412188 KB Output is correct
49 Correct 184 ms 64452 KB Output is correct
50 Correct 180 ms 64420 KB Output is correct
51 Correct 188 ms 64620 KB Output is correct
52 Correct 204 ms 68160 KB Output is correct
53 Correct 200 ms 68164 KB Output is correct
54 Correct 202 ms 68308 KB Output is correct