Submission #142543

#	Time	Username	Problem	Language	Result	Execution time	Memory
142543		imeimi2000	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4153 ms	122732 KiB

street_lamps

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
 
void initv(vector<int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
 
struct fen1D {
    vector<llong> fen;
    vector<int> cp;
    void add(int x) {
        cp.push_back(x);
    }
    void init() {
        initv(cp);
        fen.resize(cp.size(), 0);
    }
    int find(int x) const {
        return lower_bound(cp.begin(), cp.end(), x) - cp.begin() + 1;
    }
    void update(int i, llong x) {
        i = find(i);
        while (i <= cp.size()) {
            fen[i - 1] += x;
            i += i & -i;
        }
    }
    llong query(int i) const {
        i = find(i);
        llong ret = 0;
        while (i) {
            ret += fen[i - 1];
            i -= i & -i;
        }
        return ret;
    }
};
 
struct fen2D {
    vector<fen1D> fen;
    vector<int> cp;
    void add1(int x) {
        cp.push_back(x);
    }
    void init1() {
        initv(cp);
        fen.resize(cp.size());
    }
    int find(int x) const {
        return lower_bound(cp.begin(), cp.end(), x) - cp.begin() + 1;
    }
    void add2(int x, int y) {
        x = find(x);
        while (x) {
            fen[x - 1].add(y);
            x -= x & -x;
        }
    }
    void init2() {
        for (fen1D &i : fen) i.init();
    }
    void update(int i, int j, llong x) {
        i = find(i);
        while (i <= cp.size()) {
            fen[i - 1].update(j, x);
            i += i & -i;
        }
    }
    llong query(int i, int j) const {
        i = find(i);
        llong ret = 0;
        while (i) {
            ret += fen[i - 1].query(j);
            i -= i & -i;
        }
        return ret;
    }
} fenM, fenB;
 
int n, q;
char in[300001];
int S[300001];
int A[300001];
int B[300001];
int L[300002];
int R[300002];
set<int> Rs;
 
void update(int x, int y, int v, int t) {
    fenM.update(x, -y, v);
    fenB.update(x, -y, -t * v);
}
 
void add(int x, int t) {
    int l = L[x], r = R[x + 1];
    update(l, x, -1, t);
    update(x + 1, r, -1, t);
    update(l, r, 1, t);
    L[l] = L[r] = l;
    R[l] = R[r] = r;
    Rs.erase(x);
}
 
void del(int x, int t) {
    int r = *Rs.lower_bound(x);
    int l = L[r];
    update(l, r, -1, t);
    update(l, x, 1, t);
    update(x + 1, r, 1, t);
    L[l] = L[x] = l;
    R[l] = R[x] = x;
    L[x + 1] = L[r] = x + 1;
    R[x + 1] = R[r] = r;
    Rs.insert(x);
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    cin >> in;
    for (int i = 1; i <= q; ++i) {
        char str[20];
        cin >> str;
        if (str[0] == 't') {
            cin >> A[i];
        }
        else {
            cin >> A[i] >> B[i];
            fenM.add1(A[i]);
            fenB.add1(A[i]);
        }
    }
    fenM.init1();
    fenB.init1();
    for (int i = 1; i <= q; ++i) if (B[i]) {
        fenM.add2(A[i], -B[i]);
        fenB.add2(A[i], -B[i]);
    }
    fenM.init2();
    fenB.init2();
    for (int i = 1; i <= n + 1; ++i) {
        L[i] = R[i] = i;
        Rs.insert(i);
        fenM.update(i, -i, 1);
        fenB.update(i, -i, 1);
    }
    for (int i = 1; i <= n; ++i) {
        S[i] = in[i - 1] - '0';
        if (S[i]) {
            add(i, 0);
        }
    }
    for (int i = 1; i <= q; ++i) {
        if (B[i]) {
            llong Mv = fenM.query(A[i], -B[i]);
            llong Bv = fenB.query(A[i], -B[i]);
            printf("%lld\n", Mv * i + Bv);
        }
        else {
            S[A[i]] ^= 1;
            if (S[A[i]]) add(A[i], i);
            else del(A[i], i);
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void fen1D::update(int, llong)':
street_lamps.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i <= cp.size()) {
                ~~^~~~~~~~~~~~
street_lamps.cpp: In member function 'void fen2D::update(int, int, llong)':
street_lamps.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i <= cp.size()) {
                ~~^~~~~~~~~~~~

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