oj.uz

Submission #141156

# Submission time Handle Problem Language Result Execution time Memory
141156 2019-08-07T03:10:06 Z Plasmatic Street Lamps (APIO19_street_lamps) C++11
20 / 100
 5000 ms 40380 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__)

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 {
    size_t operator()(const seg &o) const {
        return 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;
}

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

inline line tryGet(unordered_map<int, line> &umi, int id) {
    auto ptr = umi.find(id);
    return ptr == umi.end() ? ZERO : ptr->second;
}

inline line sum(int a, int b) {
    line sum = ZERO;
    for (; a; a -= a & -a)
        for (int cb = b; cb; cb -= cb & -cb)
            sum.merge(tryGet(bit[a], cb)); 
    return sum;
}

inline void add(int a, int b, const line x) {
    if (a > n || b > n) // If either a or b is 0
        return;

    for(; a <= n; a += a & -a) {
        for (int cb = b; cb <= n; cb += cb & -cb) {
            auto &cline = bit[a][cb];
            cline.merge(x);
            if (!cline.m && !cline.b)
                bit[a].erase(cb);
        }
    }
}

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);

    for (int i = 1; i <= n; i++)
        state[i] = bt[i - 1] == '1';
    
    // 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 18 ms 16780 KB Output is correct
2 Correct 18 ms 16836 KB Output is correct
3 Correct 18 ms 16848 KB Output is correct
4 Correct 19 ms 16836 KB Output is correct
5 Correct 19 ms 16864 KB Output is correct
6 Correct 18 ms 16840 KB Output is correct
7 Correct 18 ms 16776 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 21084 KB Output is correct
2 Correct 2381 ms 21740 KB Output is correct
3 Execution timed out 5003 ms 23100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17356 KB Output is correct
2 Correct 33 ms 17232 KB Output is correct
3 Correct 29 ms 17300 KB Output is correct
4 Correct 18 ms 16872 KB Output is correct
5 Execution timed out 5105 ms 29660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17040 KB Output is correct
2 Correct 26 ms 17116 KB Output is correct
3 Correct 33 ms 17188 KB Output is correct
4 Correct 39 ms 17228 KB Output is correct
5 Execution timed out 5043 ms 40380 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16780 KB Output is correct
2 Correct 18 ms 16836 KB Output is correct
3 Correct 18 ms 16848 KB Output is correct
4 Correct 19 ms 16836 KB Output is correct
5 Correct 19 ms 16864 KB Output is correct
6 Correct 18 ms 16840 KB Output is correct
7 Correct 18 ms 16776 KB Output is correct
8 Correct 1119 ms 21084 KB Output is correct
9 Correct 2381 ms 21740 KB Output is correct
10 Execution timed out 5003 ms 23100 KB Time limit exceeded
11 Halted 0 ms 0 KB -