oj.uz

Submission #1044991

# Submission time Handle Problem Language Result Execution time Memory
1044991 2024-08-05T15:25:14 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 97 ms 41952 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;

struct SegT {
    vector<int> data;
    int sz;
    void reset(int s) {
        sz = s;
        data.assign(2*sz + 5, INF);
    }
    void update(int ind, int val) {
        ind += sz;
        for(data[ind] = val; ind > 1; ind >>= 1) {
            data[ind >> 1] = max(data[ind], data[ind ^ 1]);
        } 
    }
    int query(int l, int r) { // [l, r)
        int ret = 0;
        for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ret = max(data[l++], ret);
            if(r & 1) ret = max(data[--r], ret);
        }
        return ret;
    }

};


inline void solve() {
    cin >> n >> q;
    string s;
    cin >> s;
    s = '$' + s;
    vector<vector<array<int, 2> > > upd(n + 2, vector<array<int, 2> >()); // (]
    vector<array<int, 3> > que;
    vector<int> tm(n + 2, 0);
    for(int z = 1; z <= q; z++) {
        string t;
        cin >> t;
        if(t == "toggle") {
            int i;
            cin >> i;
            if(s[i] == '0') {
                tm[i] = z;
                s[i] = '1';
            }
            else {
                upd[i].pb({tm[i], z});
                s[i] = '0';
            }
        }   
        else {
            int a, b;
            cin >> a >> b;
            que.pb({a, b, z});
        }
    } 
    for(int i = 1; i <= n; i++) {
        if(s[i] == '1') {
            upd[i].pb({tm[i], q});
        }
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << "\n\n";
    //     auto &x = upd[i];
    //     for(auto &c : x) {
    //         cout << c[0] << " " << c[1] << "\n";
    //     }
    // }
    vector<int> ans(q + 1, -1);
    SegT st;
    st.reset(n + 2);
    for(int i = 1; i <= n; i++) {
        for(auto c : upd[i]) {
            st.update(i, c[0] + 1);
        }
    }
    for(auto c : que) {
        int l = st.query(c[0], c[1]);
        ans[c[2]] = max(0ll, c[2] - l + 1);
    }
    for(int i = 0; i <= q; i++) {
        if(ans[i] == -1) continue;
        cout << ans[i] << "\n";
    }


}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 8716 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 44 ms 26560 KB Output is correct
6 Correct 64 ms 29360 KB Output is correct
7 Correct 79 ms 31348 KB Output is correct
8 Correct 96 ms 36600 KB Output is correct
9 Correct 38 ms 8884 KB Output is correct
10 Correct 40 ms 13240 KB Output is correct
11 Correct 45 ms 12948 KB Output is correct
12 Correct 84 ms 26520 KB Output is correct
13 Correct 97 ms 41952 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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