Submission #885992

#	Time	Username	Problem	Language	Result	Execution time	Memory
885992		fanwen	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2144 ms	121216 KiB

street_lamps

// author : bo may can 5

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);

void you_make_it(void);

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("street_lamps");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

const int MAX = 3e5 + 5;

int n, q;

vector <int> bit[MAX], val[MAX];

struct Query {
    int t, x, y, u, v, val;
    Query(int t = 0, int x = 0, int y = 0, int u = 0, int v = 0, int val = 0) : t(t), x(x), y(y), u(u), v(v), val(val){}
};

vector <Query> queries;

void update_temp(int x, int y) {
    for (; x <= n; x += x & -x) {
        bit[x].push_back(y);
    }
}

void update_temp(int x, int y, int u, int v, int d) {
    queries.emplace_back(1, x, y, u, v, d);
    update_temp(x, y);
    update_temp(u + 1, y);
    update_temp(x, v + 1);
    update_temp(u + 1, v + 1);
}

void update(int x, int y, int d) {
    for (; x <= n; x += x & - x) {
        int i = lower_bound(bit[x].begin(), bit[x].end(), y) - bit[x].begin() + 1;
        for (; i <= (int) bit[x].size(); i += i & -i) {
            val[x][i] += d;
        }
    }
}

void update(int x, int y, int u, int v, int d) {
    update(x, y, d);
    update(x, v + 1, -d);
    update(u + 1, y, -d);
    update(u + 1, v + 1, d);
}

int get(int x, int y) {
    int ans = 0;
    for (; x > 0; x -= x & -x) {
        int i = upper_bound(bit[x].begin(), bit[x].end(), y) - bit[x].begin();
        for (; i > 0; i -= i & -i) {
            ans += val[x][i];
        }
    }
    return ans;
}

void you_make_it(void) {
    cin >> n >> q;
    set <int> s;
    for (int i = 1; i <= n; ++i) {
        char x; cin >> x;
        if(x == '0') s.insert(i);
    }
    for (int i = 1; i <= q; ++i) {
        string op; cin >> op;
        if(op == "toggle") {
            int p; cin >> p;
            if(s.count(p)) {
                auto it = s.find(p);
                int l = it == s.begin() ? 1 : *prev(it) + 1;
                int r = next(it) == s.end() ? n : *next(it) - 1;
                s.erase(it);
                update_temp(l, p, p, r, -i);
            } else {
                s.insert(p);
                auto it = s.find(p);
                int l = it == s.begin() ? 1 : *prev(it) + 1;
                int r = (next(it)) == s.end() ? n : *next(it) - 1;
                update_temp(l, p, p, r, +i);
            }
        } else {
            int l, r, v; cin >> l >> r; --r;
            auto it = s.lower_bound(l);
            v = ((it == s.end() || *it > r) ? i : 0);
            queries.emplace_back(0, l, r, l, r, v);
        }
    }

    for (int i = 1; i <= n; ++i) {
        sort(bit[i].begin(), bit[i].end());
        bit[i].erase(unique(bit[i].begin(), bit[i].end()), bit[i].end());
        val[i].resize((int) bit[i].size() + 10);
    }

    for (auto [t, x, y, u, v, val] : queries) {
        // cout << val << '\n';
        if(t == 1) {
            update(x, y, u, v, val);
        } else {
            cout << get(x, y) + val << '\n';
        }
    }


}

// Dream it. Wish it. Do it.

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:22:5: note: in expansion of macro 'file'
   22 |     file("street_lamps");
      |     ^~~~
street_lamps.cpp:12:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:22:5: note: in expansion of macro 'file'
   22 |     file("street_lamps");
      |     ^~~~

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