Submission #501544

#	Time	Username	Problem	Language	Result	Execution time	Memory
501544		gozonite	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	4360 ms	93648 KiB

street_lamps

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
using namespace std;
using ll = long long;

int n, q;
string s;
pair<int, int> inp[300001];
vector<pair<int, int> > pts;
bool cmpy(const pair<int, int>& a, const pair<int, int>& b) { return a.second < b.second; }
vector<int> val[300002], bit[300002];

void addv(int x, int y, int v) {
    for (; x <= n; x += x&-x) {
        for (int i = lower_bound(val[x].begin(), val[x].end(), y)-val[x].begin(); i < bit[x].size(); i += i&-i) {
            bit[x][i] += v;
        }
    }
}
int sumr(int x, int y) {
    int s = 0; // problem? ll
    for (; x >= 1; x -= x&-x) {
        for (int i = upper_bound(val[x].begin(), val[x].end(), y)-val[x].begin()-1; i >= 1; i -= i&-i) {
            s += bit[x][i];
        }
    }
    return s;
}
void addr(int fx, int sx, int fy, int sy, int v) {
    addv(fx, fy, v);
    addv(fx, sy+1, -v);
    addv(sx+1, fy, -v);
    addv(sx+1, sy+1, v);
}

int main() {
    cin >> n >> q >> s;
    s = " " + s;
    for (int i = 1; i <= q; i++) {
        string t; cin >> t;
        if (t == "query") {
            cin >> inp[i].first >> inp[i].second;
            inp[i].second--;
        } else {
            inp[i].first = -1;
            cin >> inp[i].second;
        }
    }
    set<int> off;
    off.insert(0); off.insert(n+1);
    for (int i = 1; i <= n; i++)
        if (s[i] == '0') off.insert(i);
    auto it = off.begin();
    while (*it != n+1) {
        int fv = *it+1; it++; int sv = *it - 1;
        if (fv > sv) continue;
        pts.push_back({fv, fv});
        pts.push_back({fv, sv+1});
        pts.push_back({sv+1, fv});
        pts.push_back({sv+1, sv+1});
    }
    for (int i = 1; i <= q; i++) {
        if (inp[i].first != -1) continue;
        if (off.find(inp[i].second) == off.end()) {
            it = off.lower_bound(inp[i].second);
            int sr = *it - 1; it--;  int fl = *it + 1;
            int fr = inp[i].second+1, sl = inp[i].second-1;
            pts.push_back({fl, fl});
            pts.push_back({fl, sl+1});
            pts.push_back({sl+1, fl});
            pts.push_back({sl+1, sl+1});

            pts.push_back({fr, fr});
            pts.push_back({fr, sr+1});
            pts.push_back({sr+1, fr});
            pts.push_back({sr+1, sr+1});

            off.insert(inp[i].second);
        } else {
            off.erase(inp[i].second);
            it = off.upper_bound(inp[i].second);
            int r = *it-1; it--; int l = *it+1;
            pts.push_back({l, l});
            pts.push_back({l, r+1});
            pts.push_back({r+1, l});
            pts.push_back({r+1, r+1});
        }
    }
    sort(pts.begin(), pts.end(), cmpy);
    for (int i = 1; i <= n; i++) val[i].push_back(0);
    for (auto pp : pts) {
        int x = pp.first, y = pp.second;
        for (; x <= n; x += x&-x) {
            if (val[x].back() != y) val[x].push_back(y);
        }
    }
    for (int i = 1; i <= n; i++) bit[i].resize(val[i].size(), 0);

    off.clear();
    off.insert(0); off.insert(n+1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0') off.insert(i);
    }
    it = off.begin();
    while (*it != n+1) {
        int l = *it+1; it++; int r = *it-1;
        addr(l, r, l, r, q);
    }
    for (int i = 1; i <= q; i++) {
        if (inp[i].first == -1) {
            if (off.find(inp[i].second) == off.end()) {
                it = off.upper_bound(inp[i].second);
                int r = *it-1; it--; int l = *it+1;
                addr(l, r, l, r, -(q-i));
                int fm = inp[i].second-1, sm = inp[i].second+1;
                addr(l, fm, l, fm, q-i);
                addr(sm, r, sm, r, q-i);
                off.insert(inp[i].second);
            } else {
                off.erase(inp[i].second);
                it = off.upper_bound(inp[i].second);
                int r = *it-1; it--; int l = *it+1;
                int fm = inp[i].second-1, sm = inp[i].second+1;
                addr(l, fm, l, fm, -(q-i));
                addr(sm, r, sm, r, -(q-i));
                addr(l, r, l, r, q-i);
            }
        } else {
            int a = inp[i].first, b = inp[i].second;
            int ans = sumr(a, b);
            if (off.lower_bound(a) == off.upper_bound(b)) ans -= q-i;
            cout << ans << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void addv(int, int, int)':
street_lamps.cpp:33:85: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i = lower_bound(val[x].begin(), val[x].end(), y)-val[x].begin(); i < bit[x].size(); i += i&-i) {
      |                                                                                   ~~^~~~~~~~~~~~~~~

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