oj.uz

Submission #401892

# Submission time Handle Problem Language Result Execution time Memory
401892 2021-05-11T00:34:05 Z kai824 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4009 ms 519340 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;
 
typedef gp_hash_table<int, int, hash<int>> 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:54:24: warning: unused variable 'd' [-Wunused-variable]
   54 |   int prev=0,ans,a,b,c,d;
      |                        ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 63772 KB Output is correct
2 Correct 64 ms 63604 KB Output is correct
3 Correct 65 ms 63592 KB Output is correct
4 Correct 66 ms 63684 KB Output is correct
5 Correct 68 ms 63680 KB Output is correct
6 Correct 69 ms 63676 KB Output is correct
7 Correct 70 ms 63652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 64724 KB Output is correct
2 Correct 259 ms 64956 KB Output is correct
3 Correct 447 ms 69580 KB Output is correct
4 Correct 2480 ms 279712 KB Output is correct
5 Correct 2722 ms 292288 KB Output is correct
6 Correct 2374 ms 287392 KB Output is correct
7 Correct 1522 ms 181512 KB Output is correct
8 Correct 1555 ms 183012 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 63908 KB Output is correct
2 Correct 71 ms 64024 KB Output is correct
3 Correct 74 ms 64264 KB Output is correct
4 Correct 72 ms 64064 KB Output is correct
5 Correct 2273 ms 218956 KB Output is correct
6 Correct 3508 ms 364632 KB Output is correct
7 Correct 4009 ms 478936 KB Output is correct
8 Correct 3418 ms 518856 KB Output is correct
9 Correct 161 ms 67548 KB Output is correct
10 Correct 172 ms 67772 KB Output is correct
11 Correct 169 ms 68120 KB Output is correct
12 Correct 3405 ms 518436 KB Output is correct
13 Correct 3406 ms 519340 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 64172 KB Output is correct
3 Correct 72 ms 64040 KB Output is correct
4 Correct 72 ms 63924 KB Output is correct
5 Correct 3751 ms 518328 KB Output is correct
6 Correct 3527 ms 479892 KB Output is correct
7 Correct 3074 ms 393028 KB Output is correct
8 Correct 2193 ms 205772 KB Output is correct
9 Correct 267 ms 70592 KB Output is correct
10 Correct 215 ms 66784 KB Output is correct
11 Correct 264 ms 70536 KB Output is correct
12 Correct 223 ms 66840 KB Output is correct
13 Correct 273 ms 70436 KB Output is correct
14 Correct 214 ms 66888 KB Output is correct
15 Correct 3448 ms 516820 KB Output is correct
16 Correct 3398 ms 517908 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 63772 KB Output is correct
2 Correct 64 ms 63604 KB Output is correct
3 Correct 65 ms 63592 KB Output is correct
4 Correct 66 ms 63684 KB Output is correct
5 Correct 68 ms 63680 KB Output is correct
6 Correct 69 ms 63676 KB Output is correct
7 Correct 70 ms 63652 KB Output is correct
8 Correct 215 ms 64724 KB Output is correct
9 Correct 259 ms 64956 KB Output is correct
10 Correct 447 ms 69580 KB Output is correct
11 Correct 2480 ms 279712 KB Output is correct
12 Correct 2722 ms 292288 KB Output is correct
13 Correct 2374 ms 287392 KB Output is correct
14 Correct 1522 ms 181512 KB Output is correct
15 Correct 1555 ms 183012 KB Output is correct
16 Correct 71 ms 63908 KB Output is correct
17 Correct 71 ms 64024 KB Output is correct
18 Correct 74 ms 64264 KB Output is correct
19 Correct 72 ms 64064 KB Output is correct
20 Correct 2273 ms 218956 KB Output is correct
21 Correct 3508 ms 364632 KB Output is correct
22 Correct 4009 ms 478936 KB Output is correct
23 Correct 3418 ms 518856 KB Output is correct
24 Correct 161 ms 67548 KB Output is correct
25 Correct 172 ms 67772 KB Output is correct
26 Correct 169 ms 68120 KB Output is correct
27 Correct 3405 ms 518436 KB Output is correct
28 Correct 3406 ms 519340 KB Output is correct
29 Correct 71 ms 64068 KB Output is correct
30 Correct 73 ms 64172 KB Output is correct
31 Correct 72 ms 64040 KB Output is correct
32 Correct 72 ms 63924 KB Output is correct
33 Correct 3751 ms 518328 KB Output is correct
34 Correct 3527 ms 479892 KB Output is correct
35 Correct 3074 ms 393028 KB Output is correct
36 Correct 2193 ms 205772 KB Output is correct
37 Correct 267 ms 70592 KB Output is correct
38 Correct 215 ms 66784 KB Output is correct
39 Correct 264 ms 70536 KB Output is correct
40 Correct 223 ms 66840 KB Output is correct
41 Correct 273 ms 70436 KB Output is correct
42 Correct 214 ms 66888 KB Output is correct
43 Correct 3448 ms 516820 KB Output is correct
44 Correct 3398 ms 517908 KB Output is correct
45 Correct 136 ms 66116 KB Output is correct
46 Correct 166 ms 66284 KB Output is correct
47 Correct 1620 ms 231512 KB Output is correct
48 Correct 3416 ms 417252 KB Output is correct
49 Correct 183 ms 68004 KB Output is correct
50 Correct 187 ms 67996 KB Output is correct
51 Correct 188 ms 68256 KB Output is correct
52 Correct 201 ms 72084 KB Output is correct
53 Correct 202 ms 72200 KB Output is correct
54 Correct 201 ms 72212 KB Output is correct