oj.uz

Submission #742687

# Submission time Handle Problem Language Result Execution time Memory
742687 2023-05-16T17:38:48 Z He_Huanglu Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2360 ms 107456 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
int n, nq, a[N], pre;
set <int> s;
vector <int> vt[N], bit[N];
struct ngu {
    int a, b, c, d, e, f, g;
}; vector <ngu> task;

void upd(int x, int _y, int last, int i) {
    while (x) {
        int y = lower_bound(vt[x].begin(), vt[x].end(), _y) - vt[x].begin();
        while (y < vt[x].size()) {
            bit[x][y] += (i ? last : -last);
            y += (y & -y);
        }
        x -= (x & -x);
    }
}
void up(int x, int y, int u, int v, int last, int i) {
    upd(x, y, last, i);
    upd(x, v + 1, last, 1 - i);
    upd(u - 1, y, last, 1 - i);
    upd(u - 1, v + 1, last, i);
}

void fake_up(int x, int y, int u, int v, int last, int i) {
    task.push_back({0, x, y, u, v, last, i});
    while (x) {
        vt[x].push_back(y);
        vt[x].push_back(v + 1);
        x -= (x & -x);
    }
    x = u - 1;
    while (x    ) {
        vt[x].push_back(y);
        vt[x].push_back(v + 1);
        x -= (x & -x);
    }
}

int get(int x, int _y) {
    int ret = 0;
    while (x <= n) {
        int y = lower_bound(vt[x].begin(), vt[x].end(), _y) - vt[x].begin();
        while (y) {
            ret += bit[x][y];
            y -= (y & -y);
        }
        x += (x & -x);
    }
    return ret;
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> nq; n++;
    for(int i = 1; i < n; i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
        if(!a[i]) {
            s.insert(i);
            up(n, pre + 1, i + 1, i, 0, 0);
            pre = i;
        }
    }
    s.insert(0); s.insert(n);
    for(int t = 1; t <= nq; t++) {
        string str; cin >> str;
        if(str == "query") {
            int u, v; cin >> u >> v;
            if(u < v) swap(u, v);
            if(*s.lower_bound(v) < u) task.push_back({1, 0, u, v, 0, 0, 0});
            else task.push_back({1, t, u, v, 0, 0, 0});
            while (u <= n) {
                vt[u].push_back(v);
                u += (u & -u);
            }
        }
        else {
            int i; cin >> i;
            a[i] = 1 - a[i];
            if(!a[i]) s.insert(i);
            else s.erase(i);
            int j = *(--(s.lower_bound(i)));
            int k = *s.upper_bound(i);
            fake_up(k, j + 1, i + 1, i, t, a[i]);
        }
    }
    for(int i = 1; i <= n; i++) {
        vt[i].push_back(-1);
        sort(vt[i].begin(), vt[i].end());
        vt[i].resize(unique(vt[i].begin(), vt[i].end()) - vt[i].begin());
        bit[i].resize(vt[i].size());
    }
    for(auto [type, x, y, u, v, last, i] : task) {
        if(type) cout << x - get(y, u) << "\n";
        else up(x, y, u, v, last, i);
    }
}

Compilation message

street_lamps.cpp: In function 'void upd(int, int, int, int)':
street_lamps.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         while (y < vt[x].size()) {
      |                ~~^~~~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main () {
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14436 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 7 ms 14360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 40284 KB Output is correct
2 Correct 331 ms 44612 KB Output is correct
3 Correct 581 ms 52416 KB Output is correct
4 Correct 1671 ms 93040 KB Output is correct
5 Correct 1527 ms 83952 KB Output is correct
6 Correct 1683 ms 95176 KB Output is correct
7 Correct 1222 ms 75408 KB Output is correct
8 Correct 927 ms 62924 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14548 KB Output is correct
2 Correct 10 ms 14548 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14520 KB Output is correct
5 Correct 2360 ms 101200 KB Output is correct
6 Correct 1924 ms 91068 KB Output is correct
7 Correct 1506 ms 80820 KB Output is correct
8 Correct 912 ms 64504 KB Output is correct
9 Correct 117 ms 25796 KB Output is correct
10 Correct 123 ms 32984 KB Output is correct
11 Correct 158 ms 33804 KB Output is correct
12 Correct 1148 ms 77284 KB Output is correct
13 Correct 932 ms 64540 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14508 KB Output is correct
2 Correct 9 ms 14476 KB Output is correct
3 Correct 9 ms 14660 KB Output is correct
4 Correct 10 ms 14548 KB Output is correct
5 Correct 1093 ms 70616 KB Output is correct
6 Correct 1373 ms 83700 KB Output is correct
7 Correct 1705 ms 95240 KB Output is correct
8 Correct 2152 ms 107456 KB Output is correct
9 Correct 396 ms 50568 KB Output is correct
10 Correct 386 ms 46772 KB Output is correct
11 Correct 410 ms 50492 KB Output is correct
12 Correct 327 ms 46856 KB Output is correct
13 Correct 452 ms 50632 KB Output is correct
14 Correct 323 ms 46456 KB Output is correct
15 Correct 1189 ms 77124 KB Output is correct
16 Correct 946 ms 64472 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14436 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 7 ms 14360 KB Output is correct
8 Correct 253 ms 40284 KB Output is correct
9 Correct 331 ms 44612 KB Output is correct
10 Correct 581 ms 52416 KB Output is correct
11 Correct 1671 ms 93040 KB Output is correct
12 Correct 1527 ms 83952 KB Output is correct
13 Correct 1683 ms 95176 KB Output is correct
14 Correct 1222 ms 75408 KB Output is correct
15 Correct 927 ms 62924 KB Output is correct
16 Correct 10 ms 14548 KB Output is correct
17 Correct 10 ms 14548 KB Output is correct
18 Correct 9 ms 14548 KB Output is correct
19 Correct 8 ms 14520 KB Output is correct
20 Correct 2360 ms 101200 KB Output is correct
21 Correct 1924 ms 91068 KB Output is correct
22 Correct 1506 ms 80820 KB Output is correct
23 Correct 912 ms 64504 KB Output is correct
24 Correct 117 ms 25796 KB Output is correct
25 Correct 123 ms 32984 KB Output is correct
26 Correct 158 ms 33804 KB Output is correct
27 Correct 1148 ms 77284 KB Output is correct
28 Correct 932 ms 64540 KB Output is correct
29 Correct 9 ms 14508 KB Output is correct
30 Correct 9 ms 14476 KB Output is correct
31 Correct 9 ms 14660 KB Output is correct
32 Correct 10 ms 14548 KB Output is correct
33 Correct 1093 ms 70616 KB Output is correct
34 Correct 1373 ms 83700 KB Output is correct
35 Correct 1705 ms 95240 KB Output is correct
36 Correct 2152 ms 107456 KB Output is correct
37 Correct 396 ms 50568 KB Output is correct
38 Correct 386 ms 46772 KB Output is correct
39 Correct 410 ms 50492 KB Output is correct
40 Correct 327 ms 46856 KB Output is correct
41 Correct 452 ms 50632 KB Output is correct
42 Correct 323 ms 46456 KB Output is correct
43 Correct 1189 ms 77124 KB Output is correct
44 Correct 946 ms 64472 KB Output is correct
45 Correct 121 ms 25428 KB Output is correct
46 Correct 183 ms 29408 KB Output is correct
47 Correct 887 ms 54592 KB Output is correct
48 Correct 1705 ms 91972 KB Output is correct
49 Correct 146 ms 33688 KB Output is correct
50 Correct 159 ms 33044 KB Output is correct
51 Correct 157 ms 33672 KB Output is correct
52 Correct 165 ms 34300 KB Output is correct
53 Correct 193 ms 34312 KB Output is correct
54 Correct 165 ms 34352 KB Output is correct