oj.uz

Submission #141189

# Submission time Handle Problem Language Result Execution time Memory
141189 2019-08-07T05:59:58 Z Plasmatic Street Lamps (APIO19_street_lamps) C++11
40 / 100
 5000 ms 312080 KB 
#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];
inline int make() {
    static int ctr = 0;
    // assert(ctr + 1 < MSN);
    return ++ctr;
}

#define nrt nodes[rt] // Current node

int cqr; line cv; // Current QL and QR
line upd(int &rt, int l, int r) {
    if (!rt) rt = make();
    
    if (l > cqr || r < cqr) return nrt.v;
    if (l == cqr && 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 || l > cqr) return ZERO;

    if (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) {
    cqr = b;
    line ret = ZERO;
    for (; a; a -= a & -a)
        ret.merge(query(bit[a], 1, n));
    return ret;
}

inline void add(int a) {
    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, const line x) {
    cv = x;

    cqr = y1; add(x1);
    cqr = y2 + 1; add(x2 + 1); 
    
    cv.inv();

    add(x1); // cqr already y2 + 1
    cqr = y1; add(x2 + 1);
}

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
                auto ptr = --segs.upper_bound({ba, -1});
                // There should always be an L who is less than the current thing

                updRect(ptr->l, ba, ba, ptr->r, {-1, 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
                    segs.insert(ins1);
                if (ins2.l <= ins2.r) // Same for ins2
                    segs.insert(ins2);
            }
            else { // !state[ba]
                // Find states to combine
                auto ptr2 = segs.upper_bound({ba, -1}), 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);
                }

                int l = condPtr ? ptr->l : ba, r = condPtr2 ? ptr2->r : ba;
                updRect(l, ba, ba, r, {1, -i - 1});

                // debug(i, ba, condPtr, condPtr2, l, r);
                
                if (condPtr)
                    segs.erase(ptr);
                if (condPtr2)
                    segs.erase(ptr2);
                segs.insert({l, r});
            }

            state[ba] ^= true;
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 1336 KB Output is correct
2 Correct 465 ms 1548 KB Output is correct
3 Correct 993 ms 5560 KB Output is correct
4 Correct 3725 ms 255860 KB Output is correct
5 Correct 3536 ms 256340 KB Output is correct
6 Correct 4029 ms 262184 KB Output is correct
7 Correct 137 ms 1652 KB Output is correct
8 Correct 150 ms 3040 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 5 ms 892 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Execution timed out 5038 ms 312080 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 4 ms 764 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 1166 ms 206896 KB Output is correct
6 Correct 2375 ms 241092 KB Output is correct
7 Correct 3575 ms 261432 KB Output is correct
8 Execution timed out 5087 ms 276636 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 355 ms 1336 KB Output is correct
9 Correct 465 ms 1548 KB Output is correct
10 Correct 993 ms 5560 KB Output is correct
11 Correct 3725 ms 255860 KB Output is correct
12 Correct 3536 ms 256340 KB Output is correct
13 Correct 4029 ms 262184 KB Output is correct
14 Correct 137 ms 1652 KB Output is correct
15 Correct 150 ms 3040 KB Output is correct
16 Correct 6 ms 1016 KB Output is correct
17 Correct 6 ms 1016 KB Output is correct
18 Correct 5 ms 892 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Execution timed out 5038 ms 312080 KB Time limit exceeded
21 Halted 0 ms 0 KB -