oj.uz

Submission #141157

# Submission time Handle Problem Language Result Execution time Memory
141157 2019-08-07T04:13:55 Z Plasmatic Street Lamps (APIO19_street_lamps) C++11
20 / 100
 5000 ms 287676 KB 
#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;
    }
};

// Hashes seg objects
struct SegHash {
    // https://stackoverflow.com/questions/1646807/quick-and-simple-hash-code-combinations
    size_t operator()(const seg &o) const {
        return 16337 + 31 * hash<int>()(o.l) + hash<int>()(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];
unordered_map<seg, line, SegHash> curLines;
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);
}

inline line tryGetCurLines(const seg &toFind) {
    auto ptr = curLines.find(toFind);
    return ptr == curLines.end() ? ZERO : ptr->second;
}

// Removes a segment from the BIT (assiming that curTime is the current minute and that this is a toggle operation)
inline void removeSegFromBit(const seg s, int curTime) {
    line cLine = tryGetCurLines(s);
    // line tnl = mergel(invl(cLine), {0, cLine.gety(curTime)}); debug(s, cLine, tnl);
    updRect(s.l, s.l, s.r, s.r, mergel(invl(cLine), curLines[s] = {0, cLine.gety(curTime)})); // Subtract original diagonal (or non diagonal) line, add new straight one
}

// Same thing but for adding
inline void addSegIntoBit(const seg s, int curTime) {
    line cLine = tryGetCurLines(s);
    // line tnl = mergel(invl(cLine), {1, cLine.gety(curTime) - curTime}); debug(s, curTime, cLine, tnl);
    updRect(s.l, s.l, s.r, s.r, mergel(invl(cLine), curLines[s] = {1, cLine.gety(curTime) - curTime}));
}

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)
        addSegIntoBit(seg, 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--;

                removeSegFromBit(*ptr, i + 1);
                segs.erase(ptr);

                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
                    addSegIntoBit(ins1, i + 1);
                    segs.insert(ins1);
                }
                if (ins2.l <= ins2.r) { // Same for ins2
                    addSegIntoBit(ins2, i + 1);
                    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);
                
                if (condPtr && condPtr2) { // Both
                    removeSegFromBit(*ptr, i + 1);
                    segs.erase(ptr);

                    removeSegFromBit(*ptr2, i + 1);
                    segs.erase(ptr2);

                    seg toAdd = {ptr->l, ptr2->r};
                    addSegIntoBit(toAdd, i + 1);
                    segs.insert(toAdd);
                }   
                else if (condPtr) { // Left satisfied
                    removeSegFromBit(*ptr, i + 1);
                    segs.erase(ptr);

                    seg toAdd = {ptr->l, ba};
                    addSegIntoBit(toAdd, i + 1);
                    segs.insert(toAdd);
                }
                else if (condPtr2) { // Right satisfied
                    removeSegFromBit(*ptr2, i + 1);
                    segs.erase(ptr2);

                    seg toAdd = {ba, ptr2->r};
                    addSegIntoBit(toAdd, i + 1);
                    segs.insert(toAdd);
                }
                else {
                    addSegIntoBit({ba, ba}, i + 1);
                    segs.insert({ba, ba});
                }
            }

            state[ba] ^= true;
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 2 ms 352 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 4608 KB Output is correct
2 Correct 886 ms 5364 KB Output is correct
3 Correct 1867 ms 12436 KB Output is correct
4 Execution timed out 5072 ms 274344 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1128 KB Output is correct
2 Correct 9 ms 1064 KB Output is correct
3 Correct 7 ms 1016 KB Output is correct
4 Correct 3 ms 424 KB Output is correct
5 Execution timed out 5109 ms 287676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 792 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 8 ms 924 KB Output is correct
4 Correct 10 ms 1016 KB Output is correct
5 Correct 1522 ms 217656 KB Output is correct
6 Correct 3830 ms 263944 KB Output is correct
7 Execution timed out 5052 ms 279188 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 404 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 639 ms 4608 KB Output is correct
9 Correct 886 ms 5364 KB Output is correct
10 Correct 1867 ms 12436 KB Output is correct
11 Execution timed out 5072 ms 274344 KB Time limit exceeded
12 Halted 0 ms 0 KB -