Submission #522309

#TimeUsernameProblemLanguageResultExecution timeMemory
522309SuffixAutomataStreet Lamps (APIO19_street_lamps)C++17
100 / 100
4976 ms243812 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; // clang-format off namespace io { const int __SIZE = (1 << 21) + 1; char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof; #define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; } inline void gc (char &x) { x = Gc(); } inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); } inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); } inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc(); for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; } template <class I> inline bool gi (I &x) { _eof = 0; for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; } for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; } template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); } struct Flusher_ {~Flusher_(){flush();}}io_flusher_; } using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print; // clang-format on #define all(a) a.begin(), a.end() #define fi first #define se second #define pb push_back #define mp make_pair using ll = long long; using pii = pair<int, int>; //#define int ll const int MOD = 1000000007; int n; int trr[300005]; struct lin { int k, b; const lin operator+(const lin &o) const { return {k + o.k, b + o.b}; } } s[15 << 20]; int lc[15 << 20], rc[15 << 20]; int _stt = 1; void modif(int &idx, int u, lin d, int l = 0, int r = n + 1) { if (!(l <= u && u < r)) return; if (!idx) idx = _stt++; if (r - l == 1) { s[idx] = s[idx] + d; return; } modif(lc[idx], u, d, l, (l + r) / 2); modif(rc[idx], u, d, (l + r) / 2, r); s[idx] = s[lc[idx]] + s[rc[idx]]; } lin nsbasket(int idx, int L, int R, int l = 0, int r = n + 1) { if (!idx || R <= l || r <= L) return {0, 0}; if (L <= l && r <= R) return s[idx]; return nsbasket(lc[idx], L, R, l, (l + r) / 2) + nsbasket(rc[idx], L, R, (l + r) / 2, r); } void add(int i, int j, lin r) { i++; while (i <= n + 2) { modif(trr[i], j, r); i += (i & (-i)); } } lin qry(int i, int j) { i++; lin ans = {0, 0}; while (i) { ans = ans + nsbasket(trr[i], 0, j + 1); i -= (i & (-i)); } return ans; } int T; void toggle(int l, int r, int f) { if (l > r) return; lin yes = {1, -T}, no = {-1, T}; if (f == -1) swap(yes, no); add(l, l, yes), add(l, r + 1, no), add(r + 1, l, no), add(r + 1, r + 1, yes); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int q; gi(n), gi(q); static char s[300005]; gstr(s); set<int> zp; zp.insert(-1), zp.insert(n); for (int i = 0; i < n; i++) if (s[i] == '0') zp.insert(i); { auto s = zp.begin(); while (s != zp.end()) { if (*s != -1) toggle(*prev(s) + 1, *s - 1, 1); s = next(s); } } for (T = 1; T <= q; T++) { gstr(s); if (s[0] == 't') { int i; gi(i); auto q = zp.find(--i); if (q != zp.end()) { toggle(*prev(q) + 1, i - 1, -1); toggle(i + 1, *next(q) - 1, -1); toggle(*prev(q) + 1, *next(q) - 1, 1); zp.erase(q); } else { q = zp.insert(i).first; toggle(*prev(q) + 1, *next(q) - 1, -1); toggle(*prev(q) + 1, i - 1, 1); toggle(i + 1, *next(q) - 1, 1); } } else { int l, r; gi(l), gi(r); lin ans = qry(l - 1, r - 2); print(T * ans.k + ans.b), pc('\n'); } } }

Compilation message (stderr)

street_lamps.cpp: In function 'void io::gstr(char*)':
street_lamps.cpp:16:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 |   for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
      |   ^~~
street_lamps.cpp:16:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   16 |   for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
      |                                                                         ^
street_lamps.cpp: In function 'bool io::gi(I&)':
street_lamps.cpp:19:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 |   for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
      |   ^~~
street_lamps.cpp:19:107: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   19 |   for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
      |                                                                                                           ^
street_lamps.cpp: In function 'void io::print(I)':
street_lamps.cpp:21:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   21 |   while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
      |   ^~~~~
street_lamps.cpp:21:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   21 |   while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
      |                                                 ^~~~~
#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...