Submission #742686

#	Time	Username	Problem	Language	Result	Execution time	Memory
742686		He_Huanglu	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2364 ms	111812 KiB

street_lamps

#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);
            int tmp = t;
            if(*s.lower_bound(v) < u) tmp = 0;
            task.push_back({1, tmp, 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) {
//        cout << type << " " << x << " " << y << " " << u << " " << v << " " << last << " " << i << "\n";
        if(type) cout << x - get(y, u) << "\n";
        else up(x, y, u, v, last, i);
    }
    return 0;
}

Compilation message (stderr)

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

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