oj.uz

Submission #789938

# Submission time Handle Problem Language Result Execution time Memory
789938 2023-07-22T07:54:10 Z GrindMachine Street Lamps (APIO19_street_lamps) C++17
20 / 100
 142 ms 14048 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        int mx,sum;
    };

    data neutral = {-inf1,0};

    data merge(data &left, data &right) {
        data curr;
        curr.mx = max(left.mx,right.mx);
        curr.sum = left.sum + right.sum;
        return curr;
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {
        tr[i].mx = v;
        tr[i].sum ^= 1;
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    int n,q; cin >> n >> q;
    vector<int> a(n+5);
    rep1(i,n){
        char ch; cin >> ch;
        a[i] = ch-'0';
    }

    segtree<int> st(n+5);
    rep1(i,n){
        if(a[i]){
            st.pupd(i,0);
        }
    }

    rep1(id,q){
        string t; cin >> t;
        if(t == "toggle"){
            int i; cin >> i;
            st.pupd(i,id);
        }
        else{
            int l,r; cin >> l >> r;
            r--;
            int len = r-l+1;
            
            auto [mx,sum] = st.query(l,r);
            int ans = 0;

            if(sum == len){
                ans = id-mx;
            }

            cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 3892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 66 ms 10404 KB Output is correct
6 Correct 91 ms 11100 KB Output is correct
7 Correct 109 ms 11716 KB Output is correct
8 Correct 142 ms 14048 KB Output is correct
9 Correct 64 ms 3916 KB Output is correct
10 Correct 70 ms 4228 KB Output is correct
11 Correct 71 ms 4468 KB Output is correct
12 Correct 124 ms 12632 KB Output is correct
13 Correct 142 ms 14020 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -