Submission #141156

#TimeUsernameProblemLanguageResultExecution timeMemory
141156PlasmaticStreet Lamps (APIO19_street_lamps)C++11
20 / 100
5105 ms40380 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...