oj.uz

Submission #436994

# Submission time Handle Problem Language Result Execution time Memory
436994 2021-06-25T14:07:37 Z alirezasamimi100 Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 296600 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){
    l++;
    r++;
    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){
    l++;
    r++;
    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;
}

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 81 ms 63688 KB Output is correct
2 Correct 80 ms 63628 KB Output is correct
3 Correct 84 ms 63700 KB Output is correct
4 Correct 80 ms 63812 KB Output is correct
5 Correct 92 ms 63924 KB Output is correct
6 Correct 75 ms 63640 KB Output is correct
7 Correct 74 ms 63628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2795 ms 64808 KB Output is correct
2 Correct 2319 ms 64992 KB Output is correct
3 Correct 1872 ms 70632 KB Output is correct
4 Correct 3456 ms 211968 KB Output is correct
5 Correct 3183 ms 215412 KB Output is correct
6 Correct 3745 ms 218532 KB Output is correct
7 Correct 1318 ms 78664 KB Output is correct
8 Correct 654 ms 66128 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 64672 KB Output is correct
2 Correct 87 ms 64504 KB Output is correct
3 Correct 90 ms 64428 KB Output is correct
4 Correct 74 ms 63612 KB Output is correct
5 Correct 4711 ms 296600 KB Output is correct
6 Correct 4301 ms 255856 KB Output is correct
7 Correct 3598 ms 220228 KB Output is correct
8 Correct 710 ms 71964 KB Output is correct
9 Correct 189 ms 67456 KB Output is correct
10 Correct 200 ms 67720 KB Output is correct
11 Correct 202 ms 67876 KB Output is correct
12 Correct 1398 ms 84624 KB Output is correct
13 Correct 666 ms 72016 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 63792 KB Output is correct
2 Correct 85 ms 64304 KB Output is correct
3 Correct 86 ms 64500 KB Output is correct
4 Correct 101 ms 64668 KB Output is correct
5 Correct 1754 ms 80024 KB Output is correct
6 Correct 3121 ms 192896 KB Output is correct
7 Correct 3603 ms 218188 KB Output is correct
8 Correct 4158 ms 236604 KB Output is correct
9 Correct 3080 ms 64324 KB Output is correct
10 Execution timed out 5084 ms 64204 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 63688 KB Output is correct
2 Correct 80 ms 63628 KB Output is correct
3 Correct 84 ms 63700 KB Output is correct
4 Correct 80 ms 63812 KB Output is correct
5 Correct 92 ms 63924 KB Output is correct
6 Correct 75 ms 63640 KB Output is correct
7 Correct 74 ms 63628 KB Output is correct
8 Correct 2795 ms 64808 KB Output is correct
9 Correct 2319 ms 64992 KB Output is correct
10 Correct 1872 ms 70632 KB Output is correct
11 Correct 3456 ms 211968 KB Output is correct
12 Correct 3183 ms 215412 KB Output is correct
13 Correct 3745 ms 218532 KB Output is correct
14 Correct 1318 ms 78664 KB Output is correct
15 Correct 654 ms 66128 KB Output is correct
16 Correct 98 ms 64672 KB Output is correct
17 Correct 87 ms 64504 KB Output is correct
18 Correct 90 ms 64428 KB Output is correct
19 Correct 74 ms 63612 KB Output is correct
20 Correct 4711 ms 296600 KB Output is correct
21 Correct 4301 ms 255856 KB Output is correct
22 Correct 3598 ms 220228 KB Output is correct
23 Correct 710 ms 71964 KB Output is correct
24 Correct 189 ms 67456 KB Output is correct
25 Correct 200 ms 67720 KB Output is correct
26 Correct 202 ms 67876 KB Output is correct
27 Correct 1398 ms 84624 KB Output is correct
28 Correct 666 ms 72016 KB Output is correct
29 Correct 97 ms 63792 KB Output is correct
30 Correct 85 ms 64304 KB Output is correct
31 Correct 86 ms 64500 KB Output is correct
32 Correct 101 ms 64668 KB Output is correct
33 Correct 1754 ms 80024 KB Output is correct
34 Correct 3121 ms 192896 KB Output is correct
35 Correct 3603 ms 218188 KB Output is correct
36 Correct 4158 ms 236604 KB Output is correct
37 Correct 3080 ms 64324 KB Output is correct
38 Execution timed out 5084 ms 64204 KB Time limit exceeded
39 Halted 0 ms 0 KB -