Submission #436996

#	Time	Username	Problem	Language	Result	Execution time	Memory
436996		alirezasamimi100	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	5045 ms	292372 KiB

street_lamps

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("O2")
/*#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = /*long long*/ int;
using ld = long double;
#define F first
#define S second
#define pb push_back
//#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=3e5+10,LN=20,M=3.5e7+10,SQ=350,BS=737,inf=1e9+10;
const ll INF=1e15;
const ld ep=1e-7;
const int MH=1000696969,MOD=1000000007,MD=998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,q;
string s;
set<ll> st={0};
gp_hash_table<ll,ll> f[N];
inline void upd(ll l, const ll &r, const ll &x){
    l++;
    while(l<N){
        for(ll i=r+1; i<N; i+=i&-i) f[l][i]+=x;
        l+=l&-l;
    }
}
inline void ADD(const ll &a, const ll &b, const ll &c, const ll &d, const ll &x){
    upd(a,b,x);
    upd(a,d+1,-x);
    upd(c+1,b,-x);
    upd(c+1,d+1,x);
}
inline ll get(ll l, const ll &r, ll x=0){
    l++;
    while(l){
        for(ll i=r+1; i; i-=i&-i) if(f[l].find(i)!=f[l].end()) x+=f[l][i];
        l-=l&-l;
    }
    return x;
}
int main(){
    fast_io;
    cin >> n >> q >> s;
    st.insert(n+1);
    for(ll i=1; i<=n; i++){
        if(s[i-1]=='0') st.insert(i);
    }
    for(ll i=1; i<=q; i++){
        string t;
        cin >> t;
        if(t[0]=='t'){
            ll x;
            cin >> x;
            ll l=*(--st.lower_bound(x))+1,r=*st.upper_bound(x);
            if(st.count(x)){
                st.erase(x);
                ADD(l,x+1,x,r,-i);
            }else{
                st.insert(x);
                ADD(l,x+1,x,r,i);
            }
        }else{
            ll l,r;
            cin >> l >> r;
            cout << get(l,r)+(st.lower_bound(l)==st.lower_bound(r)?i:0) << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp:3: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
street_lamps.cpp:19:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+15' to '2147483647' [-Woverflow]
   19 | const ll INF=1e15;
      |              ^~~~

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