oj.uz

답안 #1097525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097525 2024-10-07T14:32:25 Z lmToT27 가로등 (APIO19_street_lamps) C++17
20 / 100
 458 ms 49788 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.lower_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.lower_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 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 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 2652 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 398 ms 42224 KB Output is correct
6 Correct 458 ms 49788 KB Output is correct
7 Correct 425 ms 40912 KB Output is correct
8 Correct 232 ms 30748 KB Output is correct
9 Correct 54 ms 24508 KB Output is correct
10 Correct 62 ms 28100 KB Output is correct
11 Correct 73 ms 26808 KB Output is correct
12 Correct 220 ms 30152 KB Output is correct
13 Correct 234 ms 30412 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4696 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 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -