oj.uz

Submission #596419

# Submission time Handle Problem Language Result Execution time Memory
596419 2022-07-14T17:51:51 Z thezomb1e Street Lamps (APIO19_street_lamps) C++17
60 / 100
 275 ms 524288 KB 
//thatsramen

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

#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)

using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;

//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;

//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set

void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
    unsyncIO(); setPrec();
    if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}

// #define TEST_CASES

struct SegmentTree {

    vector<int> tre;
    int sz;

    SegmentTree(int n) {
        sz = 1;
        while (sz < n) sz *= 2;
        tre.assign(2 * sz, IINF);
        //build(a, 1, 0, sz);
    }

    void rcl(int x) {
        tre[x] = max(tre[2 * x], tre[2 * x + 1]);
    }

    void build(vector<int> &a, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < a.size()) {
                tre[x] = a[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x, lx, m);
        build(a, 2 * x + 1, m, rx);
        rcl(x);
    }

    void set(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tre[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            set(i, v, 2 * x, lx, m);
        } else {
            set(i, v, 2 * x + 1, m, rx);
        }
        rcl(x);
    }

    void set(int i, int v) {
        set(i, v, 1, 0, sz);
    }

    int get(int l, int r, int x, int lx, int rx) {
        if (rx <= l || lx >= r) {
            return -IINF;
        }
        if (l <= lx && r >= rx) {
            return tre[x];
        }
        int m = (lx + rx) / 2;
        int s1 = get(l, r, 2 * x, lx, m);
        int s2 = get(l, r, 2 * x + 1, m, rx);
        return max(s1, s2);
    }

    int get(int l, int r) {
        return get(l, r, 1, 0, sz);
    }
};

struct BIT {
    vector<int> tre;
    int sz;
    BIT(int n) {
        sz = n;
        tre.assign(sz + 5, 0);
    }
    void upd(int i, int k) {
        while (i <= sz) {
            tre[i] += k;
            i += i & -i;
        }
    }
    int get(int i) {
        int res = 0;
        while (i > 0) {
            res += tre[i];
            i -= i & -i;
        }
        return res;
    }
    int get(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    string tmp = s;
    SegmentTree st(n);
    for (int i = 0; i < n; i++) {
        if (tmp[i] == '1') st.set(i, 0);
    }
    vector<tuple<int, int, int>> qs(q);
    bool subtask3 = true, subtask2 = true;
    for (int i = 0; i < q; i++) {
        string op;
        cin >> op;
        if (op == "toggle") {
            int x; cin >> x; x--;
            if (tmp[x] == '1') subtask3 = false;
            tmp[x] = (tmp[x] == '1' ? '0' : '1');
            qs[i] = {1, x, -1};
        } else {
            int l, r; cin >> l >> r;
            l--; r--;
            if (r - l != 1) subtask2 = false;
            qs[i] = {2, l, r};
        }
    }
    if (subtask2) {
        vector<int> last(n, -1), ans(n, 0);
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') last[i] = 0;
        }
        for (int tim = 1; tim <= q; tim++) {
            auto [op, l, r] = qs[tim - 1];
            if (op == 1) {
                if (s[l] == '1') {
                    ans[l] += tim - last[l];
                    s[l] = '0';
                } else {
                    last[l] = tim;
                    s[l] = '1';
                }
            } else {
                int res = ans[l];
                if (s[l] == '1') {
                    res += tim - last[l];
                }
                cout << res << '\n';
            }
        }
        return;
    }
    if (subtask3) {
         for (int tim = 1; tim <= q; tim++) {
            auto [op, l, r] = qs[tim - 1];
            if (op == 1) {
                st.set(l, tim);
            } else {
                int mx = st.get(l, r);
                mins(mx, tim);
                cout << tim - mx << '\n';
            }
        }
        return;
    }
    BIT bit(n);
    vector<string> prev(q + 5);
    prev[0] = s;
    for (int tim = 1; tim <= q; tim++) {
        auto [op, l, r] = qs[tim - 1];
        if (op == 1) {
            if (s[l] == '1') {
                s[l] = '0';
            } else {
                s[l] = '1';
            }
        } else {
            int ans = 0;
            for (int i = 0; i < tim; i++) {
                int c = 0;
                for (int j = l; j < r; j++) {
                    c += prev[i][j] == '1';
                }
                ans += (c == r - l);
            }
            cout << ans << '\n';
        }
        prev[tim] = s;
    }
}

int main() {
    setIO();

    int tt = 1;
    #ifdef TEST_CASES
        cin >> tt;
    #endif

    while (tt--)
        solve();

    return 0;
}

Compilation message

street_lamps.cpp: In member function 'void SegmentTree::build(std::vector<int>&, int, int, int)':
street_lamps.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if (lx < a.size()) {
      |                 ~~~^~~~~~~~~~
street_lamps.cpp: In function 'void setIn(std::string)':
street_lamps.cpp:44:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void setOut(std::string)':
street_lamps.cpp:45:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4740 KB Output is correct
2 Correct 75 ms 4740 KB Output is correct
3 Correct 74 ms 4824 KB Output is correct
4 Correct 105 ms 11668 KB Output is correct
5 Correct 106 ms 12000 KB Output is correct
6 Correct 84 ms 11612 KB Output is correct
7 Correct 94 ms 11764 KB Output is correct
8 Correct 128 ms 12896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 224 KB Output is correct
5 Correct 90 ms 8660 KB Output is correct
6 Correct 167 ms 8784 KB Output is correct
7 Correct 170 ms 8988 KB Output is correct
8 Correct 230 ms 10644 KB Output is correct
9 Correct 77 ms 3928 KB Output is correct
10 Correct 82 ms 4220 KB Output is correct
11 Correct 82 ms 4316 KB Output is correct
12 Correct 183 ms 9240 KB Output is correct
13 Correct 229 ms 10544 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1288 KB Output is correct
2 Correct 105 ms 1548 KB Output is correct
3 Correct 70 ms 1364 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Runtime error 275 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 62 ms 4740 KB Output is correct
9 Correct 75 ms 4740 KB Output is correct
10 Correct 74 ms 4824 KB Output is correct
11 Correct 105 ms 11668 KB Output is correct
12 Correct 106 ms 12000 KB Output is correct
13 Correct 84 ms 11612 KB Output is correct
14 Correct 94 ms 11764 KB Output is correct
15 Correct 128 ms 12896 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 224 KB Output is correct
20 Correct 90 ms 8660 KB Output is correct
21 Correct 167 ms 8784 KB Output is correct
22 Correct 170 ms 8988 KB Output is correct
23 Correct 230 ms 10644 KB Output is correct
24 Correct 77 ms 3928 KB Output is correct
25 Correct 82 ms 4220 KB Output is correct
26 Correct 82 ms 4316 KB Output is correct
27 Correct 183 ms 9240 KB Output is correct
28 Correct 229 ms 10544 KB Output is correct
29 Correct 115 ms 1288 KB Output is correct
30 Correct 105 ms 1548 KB Output is correct
31 Correct 70 ms 1364 KB Output is correct
32 Correct 6 ms 1364 KB Output is correct
33 Runtime error 275 ms 524288 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -