Submission #1101269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101269		Mike_Vu	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	640 ms	36844 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct BIT{
    int n;
    vector<int> bit;
    void init(int _n = 0) {
        n = _n;
        bit.assign(n+1, 0);
    }
    void update(int k, int x) {
        while (k <= n) {
            bit[k] += x;
            k += k & (-k);
        }
    }
    int getsum(int k) {
        int res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k & (-k);
        }
        return res;
    }
};

const int maxn = 3e5+5;
int n, q;

namespace sub1{
    bool check(){
        return (n <= 105 && q <= 105);
    }
    bool getval(string s, int l, int r) {
        for (int i= l; i <= r; i++) {
            if (s[i] == '0') return 0;
        }
        return 1;
    }
    void solve() {
        string cur;
        vector<string> s;
        cin >> cur;
        while (q--) {
            s.pb(cur);
            string type;
            cin >> type;
            if (type[0] == 't') {
                int i;
                cin >> i;
                int x = cur[i-1]-'0';
                x = (x+1)%2;
                cur[i-1] = x+'0';
            }
            else {
                int l, r;
                cin >> l >> r;
                int ans = 0;
                for (int i= 0; i < (int)s.size(); i++) {
                    ans += getval(s[i], l-1, r-2);
                }
                cout << ans << "\n";
            }
        }
    }
}

namespace sub5{
    struct event{
        bool type;
        int l, r, val; //ans in case of queries
        event(bool _type, int _l, int _r, int _val = 0) {
            type = _type;
            l = _l;
            r = _r;
            val = _val;
        }
        void check() {
            cout << type << ' ' << l << ' ' << r << ' ' << val << "\n";
        }
    };
    bool cmp(event a, event b) {
        if (a.r != b.r) return a.r > b.r;
        return a.type < b.type;
    }
    vector<event> all;
    BIT bit;
    void dnc(int ql, int qr) {
        if (ql >= qr) return;
//        system("pause");
        int mid = (ql+qr)>>1;
        //continue
        dnc(ql, mid);
        dnc(mid+1, qr);
//        cout << "dnc: " << ql << ' ' << qr << "\n";
        //solve
        vector<event> e;
        bool can;
        can = 0;
        for (int i = ql; i <= mid; i++) {
            if (all[i].type == 0) {
                can = 1;
                e.pb(all[i]);
            }
        }
        if (!can) return;
        can = 0;
        for (int i = mid+1; i <= qr; i++) {
            if (all[i].type == 1) {
                can = 1;
                e.pb(event(all[i].type, all[i].l, all[i].r, i));
            }
        }
        if (!can) return;
        sort(e.begin(), e.end(), cmp);
        for (int i = 0; i < (int)e.size(); i++) {
            if (e[i].type == 0) {
                bit.update(e[i].l, e[i].val);
            }
            else {
                all[e[i].val].val += bit.getsum(e[i].l);
            }
//            e[i].check();
        }
        //reset
        for (int i= 0; i < (int)e.size(); i++) {
            if (e[i].type == 0) {
                bit.update(e[i].l, -e[i].val);
            }
        }
    }
    void solve() {
        string s;
        cin >> s;
        //init
        bit.init(n);
        multiset<pii> st;
        int j = 0;
        while (j < n) {
            while (s[j] == '0' && j < n) ++j;
            int i;
            for (i = j; i < n; i++) {
                if (s[i] == '0') {
                    st.insert({j+1, i});
                    all.pb(event(0, j+1, i, q+1));
//                    cout << j+1 << ' ' << i << endl;
                    break;
                }
                if (s[i] == '1' && i == n-1) {
                    st.insert({j+1, i+1});
                    all.pb(event(0, j+1, i+1, q+1));
                }
            }
            j = i+1;
        }
//        system("pause");
        //push events
        for (int t = 1; t <= q; t++) {
//            system("pause");
            string type;
            cin >> type;
            if (type[0] == 't') {
                //update
                int j;
                cin >> j;
                auto it = st.upper_bound({j, n+1});
                if (it != st.begin()) {
                    --it;
                    int l = (*it).fi, r = (*it).se;
                    if (l <= j && j <= r) {
                        //case remove
                        all.pb(event(0, l, r, -(q+1-t)));
                        st.erase(it);
                        if (l < j) {
                            all.pb(event(0, l, j-1, q+1-t));
                            st.insert({l, j-1});
                        }
                        if (j < r) {
                            all.pb(event(0, j+1, r, q+1-t));
                            st.insert({j+1, r});
                        }
                        continue;
                    }
                    //check case join
                    ++it;
                    if (it != st.end()) {
                        int l2 = (*it).fi, r2 = (*it).se;
                        if (r == j-1 && l2 == j+1) {
                            //join
                            all.pb(event(0, l2, r2, -(q+1-t)));
                            auto temp = it;
                            --it;
                            st.erase(temp);
                            all.pb(event(0, l, r, -(q+1-t)));
                            st.erase(it);
                            all.pb(event(0, l, r2, q+1-t));
                            st.insert({l, r2});
                            continue;
                        }
                    }
                    if (r == j-1) {
                        //con
                        --it;
                        all.pb(event(0, l, r, -(q+1-t)));
                        st.erase(it);
                        all.pb(event(0, l, j, q+1-t));
                        st.insert({l, j});
                        continue;
                    }
                }
                if (it != st.end()) {
                    int l = (*it).fi, r = (*it).se;
                    if (l == j+1) {
                        //con
                        all.pb(event(0, l, r, -(q+1-t)));
                        st.erase(it);
                        all.pb(event(0, j, r, q+1-t));
                        st.insert({j, r});
                        continue;
                    }
                }
                //case new
                all.pb(event(0, j, j, q+1-t));
                st.insert({j, j});
            }
            else {
                int l, r;
                cin >> l >> r;
                all.pb(event(1, l, r-1, 0));
                //case last
                auto it = st.upper_bound({l, n+1});
                if (it != st.begin()) {
                    --it;
                    int l2 = (*it).fi, r2 = (*it).se;
//                    cout << l << ' ' << r-1 << ' ' << l2 << ' ' << r2 << "\n";
                    if (l2 <= l && r-1 <= r2) {
                        all.back().val += -(q+1-t);
                    }
                }
            }
        }
//        cout << "finish pushval"  << endl;
//        system("pause");
        //cdq
//        for (int i = 0; i < (int)all.size(); i++) {
//            all[i].check();
//        }
        dnc(0, (int)all.size()-1);
        for (int i = 0; i < (int)all.size(); i++) {
            if (all[i].type == 1) {
                cout << all[i].val << "\n";
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> q;
//    if (sub1::check()) return sub1::solve(), 0;
    return sub5::solve(), 0;
}
/*
4 2
0111
toggle 2
toggle 2

4 4
0111
toggle 1
query 1 2
toggle 2
toggle 2

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

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