Submission #683272

#TimeUsernameProblemLanguageResultExecution timeMemory
683272NursikStreet Lamps (APIO19_street_lamps)C++14
40 / 100
166 ms71000 KiB
#include <stdio.h> #include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second #define ld long double #define bug cout << "bug\n"; const ll maxn = 1e6 + 1, maxm = 2e2 + 1; const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 126067, base = 1000050017, biginf = 5e18; const ld eps = 1e-15; using namespace std; int subtask1 = 1; int subtask2 = 1; int subtask3 = 1; int n, q; string kek; string s[maxn], query[maxn]; int l[maxn], r[maxn], x[maxn], t[maxn * 4]; int last[maxn], answ[maxn]; void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){ if (tl == tr){ t[v] = val; return; } int tm = (tl + tr) / 2; if (pos <= tm) upd(pos, val, v + v, tl, tm); else upd(pos, val, v + v + 1, tm + 1, tr); t[v] = max(t[v + v], t[v + v + 1]); } int get(int l, int r, int v = 1, int tl = 1, int tr = n){ if (l <= tl && tr <= r){ return t[v]; } if (l > tr || r < tl) return -inf; int tm = (tl + tr) / 2; return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr)); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> q; cin >> s[0]; kek = s[0]; for (int i = 1; i <= q; ++i){ cin >> query[i]; if (query[i] == "query"){ cin >> l[i] >> r[i]; subtask2 &= (r[i] - l[i] == 1); } else{ cin >> x[i]; if (kek[x[i] - 1] == '1'){ subtask3 = 0; } else{ kek[x[i] - 1] = '1'; } } } subtask1 &= (n <= 100 && q <= 100); if (subtask1){ s[1] = s[0]; for (int i = 1; i <= q; ++i){ // cout << i << " " << s[i] << '\n'; if (query[i] == "query"){ int ans = 0; for (int j = i; j >= 1; --j){ int ok = 1; for (int k = l[i]; k <= r[i] - 1; ++k){ ok &= (s[j][k - 1] == '1'); } if (ok){ ans += 1; } } cout << ans << '\n'; s[i + 1] = s[i]; } else{ s[i + 1] = s[i]; if (s[i + 1][x[i] - 1] == '1'){ s[i + 1][x[i] - 1] = '0'; } else{ s[i + 1][x[i] - 1] = '1'; } } } exit(0); } if (subtask2){ for (int i = 0; i < n; ++i){ last[i] = -1; if (s[0][i] == '1'){ last[i] = 0; } } for (int i = 1; i <= q; ++i){ if (query[i] == "query"){ if (s[0][l[i] - 1] == '0'){ cout << answ[l[i] - 1] << '\n'; } else{ cout << answ[l[i] - 1] + i - last[l[i] - 1] << '\n'; } } else{ if (s[0][x[i] - 1] == '0'){ last[x[i] - 1] = i; s[0][x[i] - 1] = '1'; } else{ answ[x[i] - 1] += i - last[x[i] - 1]; s[0][x[i] - 1] = '0'; } } } exit(0); } if (subtask3){ for (int i = 0; i < n; ++i){ if (s[0][i] == '1'){ upd(i + 1, 0); } else{ upd(i + 1, inf); } } for (int i = 1; i <= q; ++i){ if (query[i] == "query"){ int z = get(l[i], r[i] - 1); cout << max(0, i - z); } else{ upd(x[i], i); } } exit(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...