Submission #985338

#	Time	Username	Problem	Language	Result	Execution time	Memory
985338		ParsaGolestani	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	338 ms	58800 KiB

street_lamps

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int N = 300'000;

int n, q, s[N + 10];
int type[N + 10], a[N + 10], b[N + 10];
int ans[N + 10], val[N + 10], typeQuery[N + 10];
int x1[N + 10], x2[N + 10], y1[N + 10], y2[N + 10];

void readInput() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        s[i] = (c == '1');
    }
    for (int i = 1; i <= q; i++) {
        string s;
        cin >> s;
        if (s[0] == 't') {
            type[i] = 0;
            cin >> a[i];
        }
        else {
            type[i] = 1;
            cin >> a[i] >> b[i];
            b[i]--;
        }
    }
}

struct Segment {
    set<int> s1[2], s2[2];
    void init() {
        for (int i = 1; i <= n; i++) {
            s1[s[i]].insert(i);
            s2[s[i]].insert(-i);
        }
    }
    void toggle(int i) {
        s1[s[i]].erase(i);
        s2[s[i]].erase(-i);
        s[i] ^= 1;
        s1[s[i]].insert(i);
        s2[s[i]].insert(-i);
    }
    int getNext(int idx, int t) {
        auto au = s1[t].upper_bound(idx);
        return au == s1[t].end()? n + 1: *au;
    }
    int getLast(int idx, int t) {
        auto au = s2[t].upper_bound(-idx);
        return au == s2[t].end()? 0: -(*au);
    }
    bool isPath(int a, int b) {
        int k = getNext(a - 1, 0);
        return b < k;
    }
} seg;

struct Fenwick2D {
    vector<int> fen[N + 10], vals[N + 10];
    void updateRow(int x, int y, int val) {
        int idx = lower_bound(vals[x].begin(), vals[x].end(), y) - vals[x].begin();
        /*if (vals[x][idx] != y)
            cout << "bad " << endl;*/
        for (; idx < vals[x].size(); idx += idx & -idx)
            fen[x][idx] += val;
    }
    void updatePoint(int x, int y, int val) {
        if (x == 0 || y == 0)
            return;
        for (; x <= n; x += x & -x)
            updateRow(x, y, val);
    }
    void update(int x1, int x2, int y1, int y2, int val) {
        updatePoint(x2, y2, val);
        updatePoint(x2, y1 - 1, -val);
        updatePoint(x1 - 1, y2, -val);
        updatePoint(x1 - 1, y2 - 1, val);
    }
    void addPoint(int x, int y) {
        if (x == 0 || y == 0)
            return;
        for (; x <= n; x += x & -x)
            vals[x].push_back(y);
        for (; x; x -= x & -x)
            vals[x].push_back(y);
    }
    void addQueryChange(int x1, int x2, int y1, int y2) {
        addPoint(x2, y2);
        addPoint(x2, y1 - 1);
        addPoint(x1 - 1, y2);
        addPoint(x1 - 1, y1 - 1);
    }
    void addQueryGet(int x, int y) {
        addQueryChange(x, n, y, n);
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            vals[i].push_back(0);
            sort(vals[i].begin(), vals[i].end());
            vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin());
            fen[i].resize(vals[i].size() + 3);
        }
    }
    int getRow(int x, int idx) {
        if (idx == 0)
            return 0;
        int t = idx;
        idx = lower_bound(vals[x].begin(), vals[x].end(), idx) - vals[x].begin();
        /*if (vals[x][idx] != t)
            cout << "no " << endl;*/
        int res = 0;
        for (; idx; idx -= idx & -idx)
            res += fen[x][idx];
        return res;
    }
    int get(int x, int l, int r) {
        if (x == 0)
            return 0;
        int res = 0;
        for (; x; x -= x & -x)
            res += getRow(x, r) - getRow(x, l - 1);
        return res;
    }
    int get(int x1, int x2, int y1, int y2) {
        return get(x2, y1, y2) - get(x1 - 1, y1, y2);
    }
    int get(int x, int y) {
        return get(x, n, y, n);
    }
}  fen;

void change(int idx, int idQuery, int d) {
    int l = seg.getLast(idx, 0);
    int r = seg.getNext(idx, 0);
    fen.addQueryChange(l + 1, idx, idx, r - 1);
    typeQuery[idQuery] = 0;
    x1[idQuery] = l + 1;
    x2[idQuery] = idx;
    y1[idQuery] = idx;
    y2[idQuery] = r - 1;
    val[idQuery] = -d * idQuery;
    //cout << l << ' ' << idx << ' ' << r << '\n';
}

void initQueryChange(int idx, int idQuery) {
    if (!s[idx])
        change(idx, idQuery, 1);
    else
        change(idx, idQuery, -1);
    seg.toggle(idx);
}

void initQueryGet(int l, int r, int idQuery) {
    typeQuery[idQuery] = 1;
    x1[idQuery] = l;
    y1[idQuery] = r;
    val[idQuery] = (seg.isPath(l, r)? idQuery: 0);
    fen.addQueryGet(l, r);
    //cout << idQuery << ": " << seg.isPath(l, r) << '\n';
}

void init() {
    seg.init();
    for (int i = 1; i <= q; i++)
        if (type[i] == 0)
            initQueryChange(a[i], i);
        else
            initQueryGet(a[i], b[i], i);
    fen.init();
}

void solve() {
    for (int i = 1; i <= q; i++)
        if (type[i] == 0)
            fen.update(x1[i], x2[i], y1[i], y2[i], val[i]);
        else
            ans[i] = fen.get(x1[i], y1[i]) + val[i];
}

void writeOutput() {
    for (int i = 1; i <= q; i++)
        if (type[i])
            cout << ans[i] << '\n';
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    init();
    solve();
    writeOutput();
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void Fenwick2D::updateRow(int, int, int)':
street_lamps.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (; idx < vals[x].size(); idx += idx & -idx)
      |                ~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In member function 'int Fenwick2D::getRow(int, int)':
street_lamps.cpp:114:13: warning: unused variable 't' [-Wunused-variable]
  114 |         int t = idx;
      |             ^

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