oj.uz

Submission #436998

# Submission time Handle Problem Language Result Execution time Memory
436998 2021-06-25T14:15:07 Z alirezasamimi100 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4664 ms 292416 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 73 ms 63728 KB Output is correct
2 Correct 76 ms 63732 KB Output is correct
3 Correct 74 ms 63684 KB Output is correct
4 Correct 77 ms 63716 KB Output is correct
5 Correct 76 ms 63780 KB Output is correct
6 Correct 69 ms 63636 KB Output is correct
7 Correct 68 ms 63748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2517 ms 64824 KB Output is correct
2 Correct 2083 ms 65096 KB Output is correct
3 Correct 1965 ms 70616 KB Output is correct
4 Correct 3557 ms 212032 KB Output is correct
5 Correct 3394 ms 215544 KB Output is correct
6 Correct 3551 ms 218548 KB Output is correct
7 Correct 1169 ms 78660 KB Output is correct
8 Correct 699 ms 66104 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 64708 KB Output is correct
2 Correct 84 ms 64560 KB Output is correct
3 Correct 83 ms 64412 KB Output is correct
4 Correct 69 ms 63612 KB Output is correct
5 Correct 4664 ms 292416 KB Output is correct
6 Correct 4129 ms 251012 KB Output is correct
7 Correct 3447 ms 215016 KB Output is correct
8 Correct 670 ms 66132 KB Output is correct
9 Correct 188 ms 64720 KB Output is correct
10 Correct 205 ms 64644 KB Output is correct
11 Correct 199 ms 64784 KB Output is correct
12 Correct 1344 ms 78744 KB Output is correct
13 Correct 658 ms 66136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 63700 KB Output is correct
2 Correct 81 ms 64324 KB Output is correct
3 Correct 87 ms 64476 KB Output is correct
4 Correct 91 ms 64580 KB Output is correct
5 Correct 1787 ms 80132 KB Output is correct
6 Correct 3310 ms 192880 KB Output is correct
7 Correct 3889 ms 218144 KB Output is correct
8 Correct 4348 ms 236556 KB Output is correct
9 Correct 2819 ms 64424 KB Output is correct
10 Correct 4276 ms 63964 KB Output is correct
11 Correct 2762 ms 67676 KB Output is correct
12 Correct 4458 ms 66800 KB Output is correct
13 Correct 2900 ms 67988 KB Output is correct
14 Correct 4431 ms 66816 KB Output is correct
15 Correct 1372 ms 84600 KB Output is correct
16 Correct 674 ms 72208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 63728 KB Output is correct
2 Correct 76 ms 63732 KB Output is correct
3 Correct 74 ms 63684 KB Output is correct
4 Correct 77 ms 63716 KB Output is correct
5 Correct 76 ms 63780 KB Output is correct
6 Correct 69 ms 63636 KB Output is correct
7 Correct 68 ms 63748 KB Output is correct
8 Correct 2517 ms 64824 KB Output is correct
9 Correct 2083 ms 65096 KB Output is correct
10 Correct 1965 ms 70616 KB Output is correct
11 Correct 3557 ms 212032 KB Output is correct
12 Correct 3394 ms 215544 KB Output is correct
13 Correct 3551 ms 218548 KB Output is correct
14 Correct 1169 ms 78660 KB Output is correct
15 Correct 699 ms 66104 KB Output is correct
16 Correct 86 ms 64708 KB Output is correct
17 Correct 84 ms 64560 KB Output is correct
18 Correct 83 ms 64412 KB Output is correct
19 Correct 69 ms 63612 KB Output is correct
20 Correct 4664 ms 292416 KB Output is correct
21 Correct 4129 ms 251012 KB Output is correct
22 Correct 3447 ms 215016 KB Output is correct
23 Correct 670 ms 66132 KB Output is correct
24 Correct 188 ms 64720 KB Output is correct
25 Correct 205 ms 64644 KB Output is correct
26 Correct 199 ms 64784 KB Output is correct
27 Correct 1344 ms 78744 KB Output is correct
28 Correct 658 ms 66136 KB Output is correct
29 Correct 75 ms 63700 KB Output is correct
30 Correct 81 ms 64324 KB Output is correct
31 Correct 87 ms 64476 KB Output is correct
32 Correct 91 ms 64580 KB Output is correct
33 Correct 1787 ms 80132 KB Output is correct
34 Correct 3310 ms 192880 KB Output is correct
35 Correct 3889 ms 218144 KB Output is correct
36 Correct 4348 ms 236556 KB Output is correct
37 Correct 2819 ms 64424 KB Output is correct
38 Correct 4276 ms 63964 KB Output is correct
39 Correct 2762 ms 67676 KB Output is correct
40 Correct 4458 ms 66800 KB Output is correct
41 Correct 2900 ms 67988 KB Output is correct
42 Correct 4431 ms 66816 KB Output is correct
43 Correct 1372 ms 84600 KB Output is correct
44 Correct 674 ms 72208 KB Output is correct
45 Correct 2330 ms 66092 KB Output is correct
46 Correct 1596 ms 66256 KB Output is correct
47 Correct 2075 ms 131352 KB Output is correct
48 Correct 3627 ms 216564 KB Output is correct
49 Correct 222 ms 68036 KB Output is correct
50 Correct 217 ms 67832 KB Output is correct
51 Correct 216 ms 68036 KB Output is correct
52 Correct 233 ms 68364 KB Output is correct
53 Correct 228 ms 68244 KB Output is correct
54 Correct 228 ms 68268 KB Output is correct