Submission #141174

#	Time	Username	Problem	Language	Result	Execution time	Memory
141174		Plasmatic	Street Lamps (APIO19_street_lamps)	C++11	60 / 100	5061 ms	314908 KiB

street_lamps

#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt,tune=native"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// Defines and one-liners
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
template <typename T> inline T& back(vector<T> &vec) { return *(vec.end() - 1); }
template <typename T> inline void pop(vector<T> &vec) { return vec.erase(vec.end() - 1); }

// Scan, Debug, and other nonsense
template <typename T> ostream& operator<<(ostream& out,vector<T> iter){out<<"[";for(auto t:iter){out<<t<<", ";}out<<"]";return out;}
template <typename T> void printArray(ostream& out,T* arr,int sz){out<<"[";for(int i=0;i<sz;i++){out<<arr[i]<<", "; } out<<"]";}
#define OUT_OPERATOR(type, propa, propb) ostream& operator<<(ostream& out,type obj){out<<"("<<#propa<<"="<<obj. propa<<", "<<#propb<<"="<<obj. propb<<")";return out;}

void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
int di_; string dnms_, co_ = ",";
void debug_(){cout<<endl;}
template<typename F, typename... R> void debug_(F f,R... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
#define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)

// Structures for Problem
struct seg {
    int l, r;
    bool operator<(const seg &o) const {
        return l < o.l;
    }
    bool operator==(const seg &o) const {
        return l == o.l && r == o.r;
    }
};

struct line {
    int m, b;
    void merge(line o) {
        m += o.m;
        b += o.b;
    }
    void inv() {
        m *= -1;
        b *= -1;
    }
    int gety(int x) {
        return m * x + b;
    }
};

OUT_OPERATOR(seg, l, r)
OUT_OPERATOR(line, m, b)

const line ZERO = {0, 0};

inline line mergel(line a, line b) {
    a.merge(b);
    return a;
}

inline line invl(line a) {
    a.inv();
    return a;
}

// Segment Tree
struct InnerSegNode {
    int l, r; line v;
};
const int MSN = 20e6 + 1;
InnerSegNode nodes[MSN];
int make() {
    static int ctr = 0;
    // assert(ctr + 1 < MSN);
    return ++ctr;
}

#define nrt nodes[rt] // Current node

int cql, cqr; line cv; // Current QL and QR
line upd(int &rt, int l, int r) {
    if (!rt) rt = make();
    
    if (r < cql || l > cqr) return nrt.v;
    if (l == cql && r == cqr) {
        nrt.v.merge(cv);
        return nrt.v;
    }

    int mid = (l + r) >> 1;
    return nrt.v = mergel(upd(nrt.l, l, mid), upd(nrt.r, mid + 1, r));
}

line query(int &rt, int l, int r) {
    if (!rt || (r < cql || l > cqr)) return ZERO;

    if (l >= cql && r <= cqr) return nrt.v;

    int mid = (l + r) >> 1;
    return mergel(query(nrt.l, l, mid), query(nrt.r, mid + 1, r));
}

#undef nrt

const int MN = 3e5 + 1;
int n, q, ba, bb;
string bt;
bool state[MN];
set<seg> segs;

// BIT Functions
int bit[MN]; // Bit of "SegTree"

inline line sum(int a, int b) {
    cql = 1; cqr = b;
    line ret = ZERO;
    for (; a; a -= a & -a)
        ret.merge(query(bit[a], 1, n));
    return ret;
}

inline void add(int a, int b, const line x) {
    cql = cqr = b; cv = x;
    for(; a <= n; a += a & -a)
        upd(bit[a], 1, n);
}

// Range Add/Sub functions and other utility functions used in main()
inline void updRect(int x1, int y1, int x2, int y2, line x) {
    add(x1, y1, x);
    add(x2 + 1, y2 + 1, x);
    x.inv();
    add(x1, y2 + 1, x);
    add(x2 + 1, y1, x);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    scan(n, q, bt);

    // Init hashmaps and set states
    for (int i = 1; i <= n; i++)
        state[i] = bt[i - 1] == '1';

    // for (int i = 1; i <= n; i++) {
    //     bit[i].reserve(128);
    //     bit[i].max_load_factor(0.25);
    // }
    
    // Initial states
    int lastBegin = -1;
    for (int i = 1; i <= n; i++) {
        if (state[i] && lastBegin == -1)
            lastBegin = i;
        else if (!state[i] && lastBegin != -1) {
            segs.insert({lastBegin, i - 1});
            lastBegin = -1;
        }
    }
    if (lastBegin != -1)
        segs.insert({lastBegin, n});

    // Add states onto 2D BIT
    for (auto seg : segs)
        updRect(seg.l, seg.l, seg.r, seg.r, {1, 0});
    
    for (int i = 0; i < q; i++) {
        // CurTime = i + 1
        scan(bt, ba);

        // Debug
        // vector<seg> vss(segs.begin(), segs.end());
        // debug(i, vss);
        // for (int j = 1; j <= n; j++) {
        //     vector<int> vc;
        //     for (int k = 1; k <= n; k++) {
        //         auto sumv = sum(j, k);
        //         // debug(j, k, sumv, sumv.gety(i + 1));
        //         vc.push_back(sumv.gety(i + 1));
        //     }
        //     debug(vc);
        // }

        if (bt == "query") {
            scan(bb);
            bb--;

            cout << sum(ba, bb).gety(i + 1) << "\n";
        }
        else { // bt == "toggle"
            if (state[ba]) {
                // Find state to split
                seg toFind = {ba, -1};
                auto ptr = segs.upper_bound(toFind);
                // assert(ptr != segs.begin()); // There should always be an L who is less than the current thing
                ptr--;

                segs.erase(ptr);
                updRect(ptr->l, ba, ba, ptr->r, {-1, i + 1});

                seg ins1 = {ptr->l, ba - 1}, ins2 = {ba + 1, ptr->r};
                if (ins1.l <= ins1.r) // if ins1.l > ins1.r then the seg is size 0 and doesn't matter
                    segs.insert(ins1);
                if (ins2.l <= ins2.r) // Same for ins2
                    segs.insert(ins2);
            }
            else { // !state[ba]
                // Find states to combine
                seg toFind = {ba, -1};
                auto ptr2 = segs.upper_bound(toFind), ptr = ptr2; // ptr = left, ptr2 = right
                // ptr is invalid -> ptr2 == segs.begin(), ptr2 s invalid, ptr2 == segs.end()

                bool condPtr = false, condPtr2 = false;
                if (segs.size()) { // If the segs set is empty, don't try to set the ptr
                    ptr--; // 
                    condPtr = (ptr2 != segs.begin()) && (ptr->r + 1 == ba); 
                    condPtr2 = (ptr2 != segs.end()) && (ptr2->l - 1 == ba);
                }

                // debug(i, ba, condPtr, condPtr2);
                
                line toAdd = {1, -i - 1};
                if (condPtr && condPtr2) { // Both
                    segs.erase(ptr);
                    segs.erase(ptr2);
                    segs.insert({ptr->l, ptr2->r});

                    updRect(ptr->l, ba, ba, ptr2->r, toAdd);
                }   
                else if (condPtr) { // Left satisfied
                    segs.erase(ptr);
                    segs.insert({ptr->l, ba});

                    updRect(ptr->l, ba, ba, ba, toAdd);
                }
                else if (condPtr2) { // Right satisfied
                    segs.erase(ptr2);
                    segs.insert({ba, ptr2->r});

                    updRect(ba, ba, ba, ptr2->r, toAdd);
                }
                else {
                    segs.insert({ba, ba});
                    
                    updRect(ba, ba, ba, ba, toAdd);
                }
            }

            state[ba] ^= true;
        }
    }

    return 0;
}

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