Submission #139510

#TimeUsernameProblemLanguageResultExecution timeMemory
139510eriksuenderhaufStreet Lamps (APIO19_street_lamps)C++11
40 / 100
5103 ms33928 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define pii pair<int, int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; const int INF = 1e9 + 7; const int MAXN = 3e5 + 5; const int BLOCK = 4000; char str[MAXN], tmp[20]; int sm[MAXN], a[MAXN], ans[MAXN]; int nx[MAXN], val[MAXN]; int seg[MAXN*4]; struct query { int t, a, b; } qry[MAXN]; struct sweep { int t, a, b, val; bool operator<(const sweep rhs) const { if (rhs.b == b) { if (t == rhs.t) { if (a == rhs.a) return val < rhs.val; return a < rhs.a; } return t < rhs.t; } return b > rhs.b; } }; map<sweep,int> cparr; map<pii,int> act; int f(int ind) { ind++; int ret = 0; while (ind) { ret += sm[ind]; ind -= ind & -ind; } return ret; } void g(int ind, int v) { ind++; while (ind < MAXN) { sm[ind] += v; ind += ind & -ind; } } void build(int l, int r, int k) { seg[k] = 0; if (l == r) return; int m = (l+r) / 2; build(l,m,k*2); build(m+1,r,k*2+1); } void upd(int l, int r, int k, int x, int y, int v) { if (x <= l && r <= y) { seg[k] += v; return; } int m = (l+r) / 2; if (x <= m) upd(l,m,k*2,x,y,v); if (m < y) upd(m+1,r,k*2+1,x,y,v); } int segqry(int l, int r, int k, int x) { if (x <= l && r <= x) return seg[k]; int m = (l+r) / 2; return seg[k] + (x <= m ? segqry(l,m,k*2,x) : segqry(m+1,r,k*2+1,x)); } int main() { clock_t tim = clock(); sm[0] = 0; int n, q; scanf("%d %d", &n, &q); scanf("%s", str+1); for (int i = 1; i <= n; i++) { a[i] = str[i]-'0', val[i] = a[i]; g(i,a[i]); } for (int j = 1; j <= q; j++) { scanf("%s", tmp); if (tmp[0] == 't') { qry[j].t = 1; scanf("%d", &qry[j].a); } else { qry[j].t = 2; scanf("%d %d", &qry[j].a, &qry[j].b); } } for (int j = 1; j <= n; j++) { if (a[j] == 0) continue; int k = j; for (; k <= n && a[k] == 1; k++); act[mp(j,k-1)] = 1; nx[j] = k-1; nx[k-1] = j; j = k-1; } int curm = 0; for (int i = 1; i <= q; i += BLOCK) { for (int j = max(1,i-BLOCK); j < i; j++) { if (qry[j].t == 2) continue; int ind = qry[j].a; if (!val[ind]) { int lo = ind, hi = ind; if (val[ind-1]) { lo = nx[ind-1]; auto it = act.find(mp(lo,ind-1)); cparr[{1, lo, ind-1, 0}] += j-it->se+1; act.erase(it); nx[ind-1] = 0; } if (val[ind+1]) { hi = nx[ind+1]; auto it = act.find(mp(ind+1,hi)); cparr[{1, ind+1, hi, 0}] += j-it->se+1; act.erase(it); nx[ind+1] = 0; } act[mp(lo,hi)] = j+1; nx[lo] = hi; nx[hi] = lo; } else { auto it = prev(act.upper_bound(mp(ind,INF))); int lo = it->fi.fi, hi = it->fi.se; cparr[{1, lo, hi, 0}] += j-it->se+1; act.erase(it); nx[lo] = nx[hi] = 0; if (lo < ind) { act[mp(lo,ind-1)] = j+1; nx[lo] = ind-1; nx[ind-1] = lo; } if (ind < hi) { act[mp(ind+1,hi)] = j+1; nx[ind+1] = hi; nx[hi] = ind+1; } } val[ind] ^= 1; } //for (int j = 1; j <= n; j++) sm[j] = sm[j-1] + a[j]; for (int j = i; j <= min(q,i+BLOCK-1); j++) { if (qry[j].t == 1) continue; cparr[{2, qry[j].a, qry[j].b-1, j}] = 0; //int cur = sm[qry[j].b-1] - sm[qry[j].a-1]; int cur = f(qry[j].b-1)-f(qry[j].a-1); int ind = cur == qry[j].b-qry[j].a ? i : j; if (!act.empty()) { auto it = act.upper_bound(mp(qry[j].a,INF)); if (it != act.begin()) { it = prev(it); if (it->fi.fi <= qry[j].a && qry[j].b-1 <= it->fi.se) ans[j] += ind-it->se+1; } } vector<int> x; for (int k = i; k < j; k++) { if (qry[k].t == 1 && qry[j].a <= qry[k].a && qry[k].a < qry[j].b) { x.pb(qry[k].a); a[qry[k].a] ^= 1; cur += 2*a[qry[k].a]-1; } ans[j] += (int)(cur == qry[j].b-qry[j].a); } for (auto j: x) a[j] ^= 1; } build(1,n,1); for (auto it: cparr) { sweep cur = it.fi; if (cur.t == 1) upd(1,n,1,cur.a,cur.b,it.se); else ans[cur.val] += segqry(1,n,1,cur.a); } for (int j = i; j <= min(q,i+BLOCK-1); j++) if (qry[j].t == 1) { g(qry[j].a,(1^a[qry[j].a])-a[qry[j].a]); a[qry[j].a] ^= 1; } else { cparr.erase({2, qry[j].a, qry[j].b-1, j}); printf("%d\n", ans[j]); } } //cerr << clock() - tim << "\n";; return 0; }

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:80:10: warning: unused variable 'tim' [-Wunused-variable]
  clock_t tim = clock();
          ^~~
street_lamps.cpp:107:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q; scanf("%d %d", &n, &q);
            ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str+1);
  ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &qry[j].a);
    ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &qry[j].a, &qry[j].b);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...