oj.uz

Submission #436993

# Submission time Handle Problem Language Result Execution time Memory
436993 2021-06-25T14:02:37 Z alirezasamimi100 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 524292 KB 
#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];
void upd(ll l, ll r, ll x){
    while(l<N){
        for(ll i=r; i<N; i+=i&-i) f[l][i]+=x;
        l+=l&-l;
    }
}
void ADD(ll a, ll b, ll c, ll d, ll x){
    upd(a,b,x);
    upd(a,d+1,-x);
    upd(c+1,b,-x);
    upd(c+1,d+1,x);
}
ll get(ll l, ll r, ll x=0){
    while(l){
        for(ll i=r; 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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 91844 KB Output is correct
2 Correct 89 ms 91860 KB Output is correct
3 Correct 87 ms 91868 KB Output is correct
4 Correct 87 ms 91976 KB Output is correct
5 Correct 84 ms 92036 KB Output is correct
6 Correct 107 ms 91812 KB Output is correct
7 Correct 86 ms 91848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2966 ms 96316 KB Output is correct
2 Correct 2425 ms 97204 KB Output is correct
3 Correct 2091 ms 108504 KB Output is correct
4 Correct 3952 ms 387892 KB Output is correct
5 Correct 3555 ms 397736 KB Output is correct
6 Correct 4101 ms 401648 KB Output is correct
7 Correct 1232 ms 112896 KB Output is correct
8 Correct 712 ms 100144 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 93844 KB Output is correct
2 Correct 92 ms 93548 KB Output is correct
3 Correct 95 ms 93320 KB Output is correct
4 Correct 85 ms 91788 KB Output is correct
5 Runtime error 4345 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 91996 KB Output is correct
2 Correct 89 ms 93124 KB Output is correct
3 Correct 102 ms 93372 KB Output is correct
4 Correct 96 ms 93508 KB Output is correct
5 Correct 1892 ms 122472 KB Output is correct
6 Correct 3583 ms 349740 KB Output is correct
7 Correct 4065 ms 401384 KB Output is correct
8 Correct 4547 ms 438360 KB Output is correct
9 Correct 3189 ms 96440 KB Output is correct
10 Execution timed out 5059 ms 95276 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 91844 KB Output is correct
2 Correct 89 ms 91860 KB Output is correct
3 Correct 87 ms 91868 KB Output is correct
4 Correct 87 ms 91976 KB Output is correct
5 Correct 84 ms 92036 KB Output is correct
6 Correct 107 ms 91812 KB Output is correct
7 Correct 86 ms 91848 KB Output is correct
8 Correct 2966 ms 96316 KB Output is correct
9 Correct 2425 ms 97204 KB Output is correct
10 Correct 2091 ms 108504 KB Output is correct
11 Correct 3952 ms 387892 KB Output is correct
12 Correct 3555 ms 397736 KB Output is correct
13 Correct 4101 ms 401648 KB Output is correct
14 Correct 1232 ms 112896 KB Output is correct
15 Correct 712 ms 100144 KB Output is correct
16 Correct 102 ms 93844 KB Output is correct
17 Correct 92 ms 93548 KB Output is correct
18 Correct 95 ms 93320 KB Output is correct
19 Correct 85 ms 91788 KB Output is correct
20 Runtime error 4345 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -