oj.uz

Submission #447874

# Submission time Handle Problem Language Result Execution time Memory
447874 2021-07-27T22:43:06 Z AmShZ Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4342 ms 292628 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 63660 KB Output is correct
2 Correct 66 ms 63860 KB Output is correct
3 Correct 67 ms 63692 KB Output is correct
4 Correct 66 ms 63808 KB Output is correct
5 Correct 67 ms 63696 KB Output is correct
6 Correct 62 ms 63600 KB Output is correct
7 Correct 62 ms 63708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2420 ms 64916 KB Output is correct
2 Correct 2019 ms 65044 KB Output is correct
3 Correct 1735 ms 70628 KB Output is correct
4 Correct 2811 ms 212428 KB Output is correct
5 Correct 2710 ms 216132 KB Output is correct
6 Correct 3044 ms 219120 KB Output is correct
7 Correct 991 ms 79296 KB Output is correct
8 Correct 599 ms 66752 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 64708 KB Output is correct
2 Correct 76 ms 64488 KB Output is correct
3 Correct 74 ms 64476 KB Output is correct
4 Correct 67 ms 63748 KB Output is correct
5 Correct 3760 ms 292628 KB Output is correct
6 Correct 3349 ms 251452 KB Output is correct
7 Correct 2778 ms 215480 KB Output is correct
8 Correct 543 ms 66584 KB Output is correct
9 Correct 186 ms 65092 KB Output is correct
10 Correct 195 ms 65124 KB Output is correct
11 Correct 191 ms 65212 KB Output is correct
12 Correct 1081 ms 79280 KB Output is correct
13 Correct 545 ms 66608 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 63804 KB Output is correct
2 Correct 83 ms 64400 KB Output is correct
3 Correct 75 ms 64484 KB Output is correct
4 Correct 79 ms 64588 KB Output is correct
5 Correct 1470 ms 80284 KB Output is correct
6 Correct 2619 ms 193480 KB Output is correct
7 Correct 3051 ms 218592 KB Output is correct
8 Correct 3448 ms 237196 KB Output is correct
9 Correct 2886 ms 64876 KB Output is correct
10 Correct 4323 ms 64640 KB Output is correct
11 Correct 2803 ms 65020 KB Output is correct
12 Correct 4303 ms 64508 KB Output is correct
13 Correct 2805 ms 64888 KB Output is correct
14 Correct 4342 ms 64392 KB Output is correct
15 Correct 1068 ms 79292 KB Output is correct
16 Correct 545 ms 66644 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 63660 KB Output is correct
2 Correct 66 ms 63860 KB Output is correct
3 Correct 67 ms 63692 KB Output is correct
4 Correct 66 ms 63808 KB Output is correct
5 Correct 67 ms 63696 KB Output is correct
6 Correct 62 ms 63600 KB Output is correct
7 Correct 62 ms 63708 KB Output is correct
8 Correct 2420 ms 64916 KB Output is correct
9 Correct 2019 ms 65044 KB Output is correct
10 Correct 1735 ms 70628 KB Output is correct
11 Correct 2811 ms 212428 KB Output is correct
12 Correct 2710 ms 216132 KB Output is correct
13 Correct 3044 ms 219120 KB Output is correct
14 Correct 991 ms 79296 KB Output is correct
15 Correct 599 ms 66752 KB Output is correct
16 Correct 94 ms 64708 KB Output is correct
17 Correct 76 ms 64488 KB Output is correct
18 Correct 74 ms 64476 KB Output is correct
19 Correct 67 ms 63748 KB Output is correct
20 Correct 3760 ms 292628 KB Output is correct
21 Correct 3349 ms 251452 KB Output is correct
22 Correct 2778 ms 215480 KB Output is correct
23 Correct 543 ms 66584 KB Output is correct
24 Correct 186 ms 65092 KB Output is correct
25 Correct 195 ms 65124 KB Output is correct
26 Correct 191 ms 65212 KB Output is correct
27 Correct 1081 ms 79280 KB Output is correct
28 Correct 545 ms 66608 KB Output is correct
29 Correct 68 ms 63804 KB Output is correct
30 Correct 83 ms 64400 KB Output is correct
31 Correct 75 ms 64484 KB Output is correct
32 Correct 79 ms 64588 KB Output is correct
33 Correct 1470 ms 80284 KB Output is correct
34 Correct 2619 ms 193480 KB Output is correct
35 Correct 3051 ms 218592 KB Output is correct
36 Correct 3448 ms 237196 KB Output is correct
37 Correct 2886 ms 64876 KB Output is correct
38 Correct 4323 ms 64640 KB Output is correct
39 Correct 2803 ms 65020 KB Output is correct
40 Correct 4303 ms 64508 KB Output is correct
41 Correct 2805 ms 64888 KB Output is correct
42 Correct 4342 ms 64392 KB Output is correct
43 Correct 1068 ms 79292 KB Output is correct
44 Correct 545 ms 66644 KB Output is correct
45 Correct 2344 ms 64680 KB Output is correct
46 Correct 1593 ms 64604 KB Output is correct
47 Correct 1760 ms 128728 KB Output is correct
48 Correct 2965 ms 211992 KB Output is correct
49 Correct 213 ms 64972 KB Output is correct
50 Correct 215 ms 64832 KB Output is correct
51 Correct 210 ms 64960 KB Output is correct
52 Correct 221 ms 64840 KB Output is correct
53 Correct 219 ms 64872 KB Output is correct
54 Correct 219 ms 64776 KB Output is correct