oj.uz

답안 #1097524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097524 2024-10-07T14:29:32 Z lmToT27 가로등 (APIO19_street_lamps) C++17
20 / 100
 455 ms 55244 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4568 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4576 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 385 ms 46016 KB Output is correct
6 Correct 455 ms 55244 KB Output is correct
7 Correct 425 ms 46320 KB Output is correct
8 Correct 241 ms 35788 KB Output is correct
9 Correct 61 ms 26304 KB Output is correct
10 Correct 68 ms 31216 KB Output is correct
11 Correct 71 ms 29960 KB Output is correct
12 Correct 225 ms 36584 KB Output is correct
13 Correct 234 ms 35832 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 2 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -