제출 #187210

#제출 시각아이디문제언어결과실행 시간메모리
187210MiricaMatei가로등 (APIO19_street_lamps)C++14
100 / 100
3365 ms188368 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 300005; const int MAXQ = 300005; struct Aib { int n; vector<int>aib; Aib(int _n = 0) { n = _n; aib.resize(n + 5); for (int i = 1; i <= n; ++i) aib[i] = 0; } void rsz(int _n) { n = _n; aib.resize(n + 5); for (int i = 1; i <= n; ++i) aib[i] = 0; } void update(int pos, int val) { if (pos < 0) return ; for (; pos <= n; pos += (pos & -pos)) aib[pos] += val; } int query(int pos) { int ans = 0; for (; pos; pos -= (pos & -pos)) ans += aib[pos]; return ans; } }gen; struct Toggle { int t, pos; } q1[MAXQ]; struct Query { int t, a, b; } q2[MAXQ]; struct Node { vector<int>qry; Aib a; } aint[4 * MAXN]; char s[MAXN], qt[10]; int v[MAXN]; int ans[MAXQ]; pair<int, int>bs(int pos, int n) { int l = 1, r = pos - 1, last1 = pos; while (l <= r) { int mid = (l + r) / 2; if (gen.query(pos - 1) - gen.query(mid - 1) == pos - mid) { last1 = mid; r = mid - 1; } else { l = mid + 1; } } int last2 = pos; l = pos + 1, r = n; while (l <= r) { int mid = (l + r) / 2; if (gen.query(mid) - gen.query(pos) == mid - pos) { last2 = mid; l = mid + 1; } else { r = mid - 1; } } return {last1, last2}; } void add(int node, int l, int r, int k) { aint[node].qry.push_back(q2[k].b); if (l == r) return ; int mid = (l + r) / 2; if (q2[k].a <= mid) add(2 * node, l, mid, k); else add(2 * node + 1, mid + 1, r, k); } void build(int node, int l, int r) { if ((int)(aint[node].qry.size()) == 0) return ; sort(aint[node].qry.begin(), aint[node].qry.end()); aint[node].a.rsz((int)(aint[node].qry.size())); if (l == r) return ; int mid = (l + r) / 2; build(2 * node, l, mid); build(2 * node + 1, mid + 1, r); } void update(int node, int l, int r, int a, int b, int x, int val) { if ((int)(aint[node].qry.size()) == 0) return ; if (a <= l && r <= b) { int l1 = 0, r1 = (int)(aint[node].qry.size()) - 1; int last1 = -1, last2 = -2; while (l1 <= r1) { int mid1 = (l1 + r1) / 2; if (aint[node].qry[mid1] >= b) { last1 = mid1; r1 = mid1 - 1; } else { l1 = mid1 + 1; } } l1 = 0, r1 = (int)(aint[node].qry.size()) - 1; while (l1 <= r1) { int mid1 = (l1 + r1) / 2; if (aint[node].qry[mid1] <= x) { last2 = mid1; l1 = mid1 + 1; } else { r1 = mid1 - 1; } } if (last1 != -1 && last2 != -2) { aint[node].a.update(last1 + 1, val); aint[node].a.update(last2 + 2, -val); } return ; } if (l == r) return ; int mid = (l + r) / 2; if (a <= mid) update(2 * node, l, mid, a, b, x, val); if (b > mid) update(2 * node + 1, mid + 1, r, a, b, x, val); } int query(int node, int l, int r, int k) { if ((int)(aint[node].qry.size()) == 0) return 0; int l1 = 0, r1 = (int)(aint[node].qry.size()) - 1, last = -1; while (l1 <= r1) { int mid1 = (l1 + r1) / 2; if (aint[node].qry[mid1] <= q2[k].b) { last = mid1; l1 = mid1 + 1; } else { r1 = mid1 - 1; } } int ans = aint[node].a.query(last + 1); if (l == r) return ans; int mid = (l + r) / 2; if (q2[k].a <= mid) ans += query(2 * node, l, mid, k); else ans += query(2 * node + 1, mid + 1, r, k); return ans; } int main() { //freopen("date.in", "r", stdin); //freopen("date.out", "w", stdout); int n, q; scanf("%d%d ", &n, &q); scanf("%s", s + 1); int k1 = 0, k2 = 0; for (int i = 1; i <= q; ++i) { scanf("%s", qt); if (qt[0] == 't') { k1++; scanf("%d ", &q1[k1].pos); q1[k1].t = i; } else { k2++; scanf("%d%d ", &q2[k2].a, &q2[k2].b); q2[k2].b--; q2[k2].t = i; add(1, 1, n, k2); } } build(1, 1, n); gen.rsz(n); for (int i = 1; i <= n; ++i) { if (s[i] == '1') { gen.update(i, 1); v[i] = 1; } } for (int i = 1, j = 1; i <= k1 || j <= k2; ) { if (i <= k1 && (j > k2 || q1[i].t < q2[j].t)) { int val; if (v[q1[i].pos] == 1) { val = i + j - 1; v[q1[i].pos] = 0; gen.update(q1[i].pos, -1); } else { val = -(i + j - 1); v[q1[i].pos] = 1; gen.update(q1[i].pos, 1); } pair<int, int>interval = bs(q1[i].pos, n); update(1, 1, n, interval.first, q1[i].pos, interval.second, val); i++; } else { ans[j] = query(1, 1, n, j); int x = gen.query(q2[j].b) - gen.query(q2[j].a - 1); if (gen.query(q2[j].b) - gen.query(q2[j].a - 1) == q2[j].b - q2[j].a + 1) ans[j] += i + j - 1; j++; } } for (int i = 1; i <= k2; ++i) printf("%d\n", ans[i]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:219:11: warning: unused variable 'x' [-Wunused-variable]
       int x = gen.query(q2[j].b) - gen.query(q2[j].a - 1);
           ^
street_lamps.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d ", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", qt);
     ~~~~~^~~~~~~~~~
street_lamps.cpp:182:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d ", &q1[k1].pos);
       ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:186:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d ", &q2[k2].a, &q2[k2].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...