Submission #1097524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097524		lmToT27	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	455 ms	55244 KiB

street_lamps

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 3e5 + 3;
const ll MOD[] = {1000000007, 998244353};

int n, q, ans[MAX];
int state[MAX];
string st;
set <pair <int, int>> segmentOnActive;

struct FenwickTree {
        int bit[MAX];

        void update(int u, int v) {
                for (; u > 0; u -= u & -u) bit[u] += v;
        }

        int get(int u) {
                int res = 0;
                for (; u <= n; u += u & -u) res += bit[u];
                return res;
        }
} fwSum, fwCnt;

struct up_t { 
        int time, l, r, val;

        up_t(int a = 0, int b = 0, int c = 0, int d = 0) : time(a), l(b), r(c), val(d) {}
};

struct query_t {
        int time, l1, l2, r;

        query_t(int a = 0, int b = 0, int c = 0, int d = 0) : time(a), l1(b), l2(c), r(d) {}
};

void call(int leftBound, int rightBound, vector <up_t> &updates, vector <query_t> &queries) {
        int updatesPointer = 0;
        int mid = (leftBound + rightBound) / 2;
        vector <query_t> leftQrs, rightQrs;
        for (auto &[i, l1, l2, R] : queries) {
                if (l1 == leftBound && l2 == rightBound) {
                        while (updatesPointer < (int)updates.size()) {
                                auto &[time, l, r, val] = updates[updatesPointer];
                                if (time > i) break;
                                fwSum.update(r, time * val);
                                fwCnt.update(r, val);
                                updatesPointer++;
                        }
                        ans[i] += fwCnt.get(R) * i - fwSum.get(R); 
                } else if (l2 <= mid) {
                        leftQrs.emplace_back(i, l1, l2, R);
                } else if (l1 > mid) {
                        rightQrs.emplace_back(i, l1, l2, R);
                } else {
                        leftQrs.emplace_back(i, l1, mid, R);
                        rightQrs.emplace_back(i, mid + 1, l2, R);
                }
        }

        updatesPointer--;

        while (updatesPointer >= 0) {
                auto &[time, l, r, val] = updates[updatesPointer];
                fwSum.update(r, -time * val);
                fwCnt.update(r, -val);
                updatesPointer--;
        }

        if (leftBound != rightBound) {
                vector <up_t> leftUps, rightUps;
                for (auto &[time, l, r, val] : updates) {
                        if (l <= mid) leftUps.emplace_back(time, l, r, val);
                        else rightUps.emplace_back(time, l, r, val);
                }
                call(leftBound, mid, leftUps, leftQrs);
                call(mid + 1, rightBound, rightUps, rightQrs);
        }
}

void Solve() {
        cin >> n >> q;
        cin >> st;
        vector <up_t> updates;
        vector <query_t> queries;
        for (int i = 1; i <= n; i++) state[i] = st[i - 1] - '0';
        for (int i = 1, j; i <= n; i++) {
                if (state[i]) {
                        j = i;
                        while (j <= n && state[j]) j++;
                        j--;
                        segmentOnActive.insert(make_pair(i, j));
                        updates.emplace_back(0, i, j, 1);
                        i = j;
                }
        }

        string qType;
        int u, v;
       
        for (int i = 1; i <= q; i++) {
                ans[i] = -1;
                cin >> qType >> u;
                if (qType == "query") {
                        cin >> v;
                        ans[i] = 0;
                        queries.emplace_back(i, 1, u, v - 1);
                } else {
                        state[u] ^= 1;
                        if (state[u] == 0) {
                                auto f = *prev(segmentOnActive.upper_bound(make_pair(u, -1)));
                                segmentOnActive.erase(f);
                                updates.emplace_back(i, f.first, f.second, -1);
                                if (state[i - 1]) {
                                        segmentOnActive.insert(make_pair(f.first, u - 1));
                                        updates.emplace_back(i, f.first, u - 1, 1);
                                }
                                if (state[i + 1]) {
                                        segmentOnActive.insert(make_pair(u + 1, f.second));
                                        updates.emplace_back(i, u + 1, f.second, 1);
                                }
                        } else {
                                int l = u, r = u;
                                if (state[u - 1]) {
                                        auto f = *prev(segmentOnActive.upper_bound(make_pair(u, -1)));
                                        segmentOnActive.erase(f);
                                        updates.emplace_back(i, f.first, f.second, -1);
                                        l = f.first;
                                }
                                if (state[u + 1]) {
                                        auto f = *segmentOnActive.upper_bound(make_pair(u, -1));
                                        segmentOnActive.erase(f);
                                        updates.emplace_back(i, f.first, f.second, -1);
                                        r = f.second;
                                }
                                segmentOnActive.insert(make_pair(l, r));
                                updates.emplace_back(i, l, r, 1);
                        }
                }
        }
        
        call(1, n, updates, queries);

        for (int i = 1; i <= q; i++) if (ans[i] != -1) cout << ans[i] << '\n';
}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        #define TASK "TASK"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:171:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:172:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20