Submission #131261

#	Time	Username	Problem	Language	Result	Execution time	Memory
131261		osaaateiasavtnl	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2433 ms	116768 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define app push_back
const int N = 3e5 + 7;
struct Quer {
    int t, i, l, r;
};
struct Fen {
    int w, l, cnt;
    Fen() {
        w = 0; l = 0; cnt = 0;
    }   
};  
struct Event {
    int t, l, r, tm;
};
int n, q;
bool a[N]; 
Quer d[N];
vector <int> f[N];
vector <Event> mem;
void add(int l, int r, int t) {
    r = n - r;
    mem.app({1, l, r, t});
    for (int i = l; i < N; i |= i + 1) {
        f[i].app(r);
    }   
}
int cl[N], cr[N];
int sum[N << 2];
void build(int v, int tl, int tr) {
    if (tl == tr) {
        sum[v] = a[tl];
        return;
    }   
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
    sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
}   
void upd(int v, int tl, int tr, int p, int x) {
    if (tr == tl) {
        sum[v] = x;
        return;
    }   
    int tm = (tl + tr) >> 1;
    if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
    else upd(v * 2 + 2, tm + 1, tr, p, x);
    sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
}
int getl(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl || sum[v] == tr - tl + 1) return n;
    if (tl == tr) return tl;
    int tm = (tl + tr) >> 1;
    int t = getl(v * 2 + 1, tl, tm, l, r);
    if (t != n) return t;
    else return getl(v * 2 + 2, tm + 1, tr, l, r);    
}     
int getr(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl || sum[v] == tr - tl + 1) return -1;
    if (tl == tr) return tl;
    int tm = (tl + tr) >> 1;
    int t = getr(v * 2 + 2, tm + 1, tr, l, r);
    if (t != -1) return t;
    else return getr(v * 2 + 1, tl, tm, l, r);
}   
vector <Fen> fn[N];
void add1(int x, int y, int t) {
    for (int i = x; i < N; i |= i + 1) {
        int j = lower_bound(f[i].begin(), f[i].end(), y) - f[i].begin();
        for (; j < fn[i].size(); j |= j + 1) {
            fn[i][j].l += t;
            fn[i][j].cnt++;
        }   
    }   
}   
void del1(int x, int y, int t) {
    for (int i = x; i < N; i |= i + 1) {
        int j = lower_bound(f[i].begin(), f[i].end(), y) - f[i].begin();
        for (; j < fn[i].size(); j |= j + 1) {
            fn[i][j].l -= t;
            fn[i][j].cnt--;
        }   
    }   
}   
void add2(int x, int y, int t) {
    for (int i = x; i < N; i |= i + 1) {
        int j = lower_bound(f[i].begin(), f[i].end(), y) - f[i].begin();
        for (; j < fn[i].size(); j |= j + 1) {
            fn[i][j].w += t;
        }   
    }       
}   
int get(int x, int y, int t) {
    int ans = 0;
    for (int i = x; i >= 0; i &= i + 1, --i) {
        int j = upper_bound(f[i].begin(), f[i].end(), y) - f[i].begin() - 1;
        for (; j >= 0; j &= j + 1, --j) {
            ans += fn[i][j].w;
            ans -= fn[i][j].l;
            ans += fn[i][j].cnt * t;
        }   
    }
    return ans;   
}   

map <int, int> dc[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        a[i] = c == '1';
    }   
    for (int i = 0; i < q; ++i) {
        string t;
        cin >> t;
        if (t == "toggle") {
            d[i].t = 1;
            cin >> d[i].i;
            --d[i].i;
        }
        else {
            d[i].t = 2;
            cin >> d[i].l >> d[i].r;
            --d[i].r;
            --d[i].l; --d[i].r;
        }
    }
    int l = -1;
    for (int i = 0; i < n; ++i) {
        if (!a[i]) {
            if (l != -1) {
                add(l, i - 1, 0);
                l = -1;
            }
        }   
        else {
            if (l == -1) {
                l = i;
            }   
        }   
    }   
    if (a[n - 1]) {
        add(l, n - 1, 0);
    }   
    build(0, 0, n - 1);
    for (int i = 0; i < q; ++i) {
        if (d[i].t == 1) {
            int p = d[i].i;
            if (a[p]) {
                int l = getr(0, 0, n - 1, 0, p - 1) + 1;
                int r = getl(0, 0, n - 1, p + 1, n - 1) - 1;
                mem.app({2, l, n - r, i + 1});
                if (l != p) {
                    add(l, p - 1, i + 1);
                }   
                if (r != p) {
                    add(p + 1, r, i + 1);
                }   
            }
            else {
                int l = getr(0, 0, n - 1, 0, p - 1) + 1;
                int r = getl(0, 0, n - 1, p + 1, n - 1) - 1;
                if (l != p) {
                    mem.app({2, l, n - (p - 1), i + 1});
                }   
                if (r != p) {
                    mem.app({2, p + 1, n - r, i + 1});
                }
                add(l, r, i + 1);
            }
            a[p] ^= 1;
            upd(0, 0, n - 1, p, a[p]);
        }
        else {
            mem.app({3, d[i].l, n - d[i].r, i + 1});                
        }   
    }   
    for (int i = 0; i < N; ++i) {
        sort(f[i].begin(), f[i].end());
        f[i].resize(unique(f[i].begin(), f[i].end()) - f[i].begin());
    }   
    for (int i = 0; i < N; ++i) {
        fn[i].resize(f[i].size());
    }   

    #ifdef HOME
    for (auto e : mem) {
        cout << e.t << ' ' << e.l << ' ' << -e.r + n << ' ' << e.tm << '\n';
    }   
    #endif

    for (auto e : mem) {
        if (e.t == 1) {
            add1(e.l, e.r, e.tm);  
            dc[e.l][e.r] = e.tm;
        }
        else if (e.t == 2) {
            int pr = dc[e.l][e.r];
            del1(e.l, e.r, pr);
            add2(e.l, e.r, e.tm - pr);
        }
        else {
            cout << get(e.l, e.r, e.tm) << '\n';
        }   
    }   
}   

Compilation message (stderr)

street_lamps.cpp: In function 'void add1(int, int, int)':
street_lamps.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; j < fn[i].size(); j |= j + 1) {
                ~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'void del1(int, int, int)':
street_lamps.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; j < fn[i].size(); j |= j + 1) {
                ~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'void add2(int, int, int)':
street_lamps.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; j < fn[i].size(); j |= j + 1) {
                ~~^~~~~~~~~~~~~~

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