oj.uz

Submission #885992

# Submission time Handle Problem Language Result Execution time Memory
885992 2023-12-11T10:01:39 Z fanwen Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2144 ms 121216 KB 
// 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

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

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 42364 KB Output is correct
2 Correct 259 ms 41500 KB Output is correct
3 Correct 498 ms 47448 KB Output is correct
4 Correct 1250 ms 93020 KB Output is correct
5 Correct 983 ms 77040 KB Output is correct
6 Correct 1416 ms 101168 KB Output is correct
7 Correct 275 ms 58028 KB Output is correct
8 Correct 109 ms 44472 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 6 ms 14556 KB Output is correct
3 Correct 5 ms 14676 KB Output is correct
4 Correct 4 ms 14428 KB Output is correct
5 Correct 2144 ms 116860 KB Output is correct
6 Correct 1577 ms 100880 KB Output is correct
7 Correct 1002 ms 75440 KB Output is correct
8 Correct 108 ms 44460 KB Output is correct
9 Correct 71 ms 23948 KB Output is correct
10 Correct 95 ms 30644 KB Output is correct
11 Correct 72 ms 31200 KB Output is correct
12 Correct 308 ms 57432 KB Output is correct
13 Correct 111 ms 44120 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 5 ms 14552 KB Output is correct
5 Correct 286 ms 51420 KB Output is correct
6 Correct 815 ms 76900 KB Output is correct
7 Correct 1354 ms 99572 KB Output is correct
8 Correct 2024 ms 121216 KB Output is correct
9 Correct 324 ms 55388 KB Output is correct
10 Correct 283 ms 51884 KB Output is correct
11 Correct 334 ms 56924 KB Output is correct
12 Correct 282 ms 52572 KB Output is correct
13 Correct 325 ms 54880 KB Output is correct
14 Correct 282 ms 50152 KB Output is correct
15 Correct 261 ms 56852 KB Output is correct
16 Correct 107 ms 44208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14428 KB Output is correct
3 Correct 4 ms 14424 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 3 ms 14548 KB Output is correct
7 Correct 3 ms 14428 KB Output is correct
8 Correct 205 ms 42364 KB Output is correct
9 Correct 259 ms 41500 KB Output is correct
10 Correct 498 ms 47448 KB Output is correct
11 Correct 1250 ms 93020 KB Output is correct
12 Correct 983 ms 77040 KB Output is correct
13 Correct 1416 ms 101168 KB Output is correct
14 Correct 275 ms 58028 KB Output is correct
15 Correct 109 ms 44472 KB Output is correct
16 Correct 6 ms 14684 KB Output is correct
17 Correct 6 ms 14556 KB Output is correct
18 Correct 5 ms 14676 KB Output is correct
19 Correct 4 ms 14428 KB Output is correct
20 Correct 2144 ms 116860 KB Output is correct
21 Correct 1577 ms 100880 KB Output is correct
22 Correct 1002 ms 75440 KB Output is correct
23 Correct 108 ms 44460 KB Output is correct
24 Correct 71 ms 23948 KB Output is correct
25 Correct 95 ms 30644 KB Output is correct
26 Correct 72 ms 31200 KB Output is correct
27 Correct 308 ms 57432 KB Output is correct
28 Correct 111 ms 44120 KB Output is correct
29 Correct 4 ms 14428 KB Output is correct
30 Correct 4 ms 14684 KB Output is correct
31 Correct 5 ms 14684 KB Output is correct
32 Correct 5 ms 14552 KB Output is correct
33 Correct 286 ms 51420 KB Output is correct
34 Correct 815 ms 76900 KB Output is correct
35 Correct 1354 ms 99572 KB Output is correct
36 Correct 2024 ms 121216 KB Output is correct
37 Correct 324 ms 55388 KB Output is correct
38 Correct 283 ms 51884 KB Output is correct
39 Correct 334 ms 56924 KB Output is correct
40 Correct 282 ms 52572 KB Output is correct
41 Correct 325 ms 54880 KB Output is correct
42 Correct 282 ms 50152 KB Output is correct
43 Correct 261 ms 56852 KB Output is correct
44 Correct 107 ms 44208 KB Output is correct
45 Correct 88 ms 28540 KB Output is correct
46 Correct 131 ms 28928 KB Output is correct
47 Correct 604 ms 53568 KB Output is correct
48 Correct 1239 ms 93152 KB Output is correct
49 Correct 80 ms 30392 KB Output is correct
50 Correct 79 ms 31412 KB Output is correct
51 Correct 85 ms 31428 KB Output is correct
52 Correct 84 ms 32344 KB Output is correct
53 Correct 77 ms 32452 KB Output is correct
54 Correct 80 ms 32548 KB Output is correct