제출 #187210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
187210		MiricaMatei	가로등 (APIO19_street_lamps)	C++14	100 / 100	3365 ms	188368 KiB

street_lamps

#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);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20