oj.uz

Submission #436996

# Submission time Handle Problem Language Result Execution time Memory
436996 2021-06-25T14:12:39 Z alirezasamimi100 Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 292372 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];
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 78 ms 63660 KB Output is correct
2 Correct 82 ms 63680 KB Output is correct
3 Correct 78 ms 63736 KB Output is correct
4 Correct 81 ms 63724 KB Output is correct
5 Correct 73 ms 63804 KB Output is correct
6 Correct 69 ms 63684 KB Output is correct
7 Correct 82 ms 63688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2999 ms 64824 KB Output is correct
2 Correct 2369 ms 65120 KB Output is correct
3 Correct 2050 ms 70564 KB Output is correct
4 Correct 3529 ms 212052 KB Output is correct
5 Correct 3192 ms 215356 KB Output is correct
6 Correct 3852 ms 218576 KB Output is correct
7 Correct 1129 ms 78740 KB Output is correct
8 Correct 670 ms 66252 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 64840 KB Output is correct
2 Correct 84 ms 64556 KB Output is correct
3 Correct 82 ms 64460 KB Output is correct
4 Correct 88 ms 63684 KB Output is correct
5 Correct 4835 ms 292372 KB Output is correct
6 Correct 4238 ms 250936 KB Output is correct
7 Correct 3551 ms 214956 KB Output is correct
8 Correct 680 ms 66048 KB Output is correct
9 Correct 187 ms 64580 KB Output is correct
10 Correct 197 ms 64672 KB Output is correct
11 Correct 198 ms 64788 KB Output is correct
12 Correct 1331 ms 78624 KB Output is correct
13 Correct 639 ms 66048 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 63808 KB Output is correct
2 Correct 82 ms 64324 KB Output is correct
3 Correct 82 ms 64492 KB Output is correct
4 Correct 91 ms 64484 KB Output is correct
5 Correct 1859 ms 79944 KB Output is correct
6 Correct 3264 ms 193072 KB Output is correct
7 Correct 3767 ms 218168 KB Output is correct
8 Correct 4164 ms 236640 KB Output is correct
9 Correct 3253 ms 64420 KB Output is correct
10 Execution timed out 5045 ms 64008 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 63660 KB Output is correct
2 Correct 82 ms 63680 KB Output is correct
3 Correct 78 ms 63736 KB Output is correct
4 Correct 81 ms 63724 KB Output is correct
5 Correct 73 ms 63804 KB Output is correct
6 Correct 69 ms 63684 KB Output is correct
7 Correct 82 ms 63688 KB Output is correct
8 Correct 2999 ms 64824 KB Output is correct
9 Correct 2369 ms 65120 KB Output is correct
10 Correct 2050 ms 70564 KB Output is correct
11 Correct 3529 ms 212052 KB Output is correct
12 Correct 3192 ms 215356 KB Output is correct
13 Correct 3852 ms 218576 KB Output is correct
14 Correct 1129 ms 78740 KB Output is correct
15 Correct 670 ms 66252 KB Output is correct
16 Correct 85 ms 64840 KB Output is correct
17 Correct 84 ms 64556 KB Output is correct
18 Correct 82 ms 64460 KB Output is correct
19 Correct 88 ms 63684 KB Output is correct
20 Correct 4835 ms 292372 KB Output is correct
21 Correct 4238 ms 250936 KB Output is correct
22 Correct 3551 ms 214956 KB Output is correct
23 Correct 680 ms 66048 KB Output is correct
24 Correct 187 ms 64580 KB Output is correct
25 Correct 197 ms 64672 KB Output is correct
26 Correct 198 ms 64788 KB Output is correct
27 Correct 1331 ms 78624 KB Output is correct
28 Correct 639 ms 66048 KB Output is correct
29 Correct 72 ms 63808 KB Output is correct
30 Correct 82 ms 64324 KB Output is correct
31 Correct 82 ms 64492 KB Output is correct
32 Correct 91 ms 64484 KB Output is correct
33 Correct 1859 ms 79944 KB Output is correct
34 Correct 3264 ms 193072 KB Output is correct
35 Correct 3767 ms 218168 KB Output is correct
36 Correct 4164 ms 236640 KB Output is correct
37 Correct 3253 ms 64420 KB Output is correct
38 Execution timed out 5045 ms 64008 KB Time limit exceeded
39 Halted 0 ms 0 KB -