Submission #120573

#	Time	Username	Problem	Language	Result	Execution time	Memory
120573		IOrtroiii	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2997 ms	105108 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int N = 300300;

int n, q;
char s[N];

int t[N << 2];

#define md ((l + r) >> 1)

void modify(int v, int l, int r, int p) {
   if (l == r) {
      t[v] ^= 1;
      return;
   }
   if (p <= md) modify(v << 1, l, md, p);
   else modify(v << 1 | 1, md + 1, r, p);
   t[v] = t[v << 1] + t[v << 1 | 1];
}

int lg[N], rg[N];

int findL(int v, int l, int r, int p) {
   if (l > p || t[v] == r - l + 1) {
      return -1;
   }
   if (l == r) return l;
   int ans = findL(v << 1 | 1, md + 1, r, p);
   if (ans == -1) ans = findL(v << 1, l, md, p);
   return ans;
}

int findR(int v, int l, int r, int p) {
   if (r < p || t[v] == r - l + 1) {
      return -1;
   }
   if (l == r) return l;
   int ans = findR(v << 1, l, md, p);
   if (ans == -1) ans = findR(v << 1 | 1, md + 1, r, p);
   return ans;
}

int get(int v, int l, int r, int L, int R) {
   if (L <= l && r <= R) {
      return t[v];
   }
   int ans = 0;
   if (L <= md) ans += get(v << 1, l, md, L, R);
   if (md < R) ans += get(v << 1 | 1, md + 1, r, L, R);
   return ans;
}
#undef md

vector<int> ps[N];
vector<int> ft[N];

void fake_add(int x, int y) {
   // printf("add %d %d\n", x, y);
   if (x > n || y > n) return;
   for (; x <= n; x += x & -x) {
      ps[x].push_back(y);
   }
}

void fake_get(int x, int y) {
   for (; x > 0; x -= x & -x) {
      ps[x].push_back(y);
   }
}

void build() {
   for (int x = 1; x <= n; ++x) {
      sort(ps[x].begin(), ps[x].end());
      ps[x].resize(unique(ps[x].begin(), ps[x].end()) - ps[x].begin());
      /*
      printf("at %d: ", x);
      for (int y : ps[x]) {
         printf("%d ", y);
      }
      puts("");
      */
      ft[x].assign(ps[x].size() + 1, 0);
   }
}

void add(int x, int y, int val) {
   if (x > n || y > n) return;
   // printf("%d %d\n", x, y);
   for (; x <= n; x += x & -x) {
      int yy = upper_bound(ps[x].begin(), ps[x].end(), y) - ps[x].begin();
      // printf("%d %d\n", x, y);
      for (; yy < ft[x].size(); yy += yy & -yy) {
         ft[x][yy] += val;
      }
   }
}

int get(int x, int y) {
   int ans = 0;
   for (; x > 0; x -= x & -x) {
      int yy = upper_bound(ps[x].begin(), ps[x].end(), y) - ps[x].begin();
      for (; yy > 0; yy -= yy & -yy) {
         ans += ft[x][yy];
      }
   }
   return ans;
}

int lq[N], rq[N];
int ans[N];
int vq[N];
int pq[N];

int main() {
   scanf("%d %d %s", &n, &q, s + 1);
   for (int i = 1; i <= n; ++i) {
      if (s[i] == '1') {
         modify(1, 1, n, i);
      }
   }
   for (int i = 1; i <= q; ++i) {
      char buf[10];
      scanf("%s", buf);
      if (buf[0] == 'q') {
         scanf("%d %d", lq + i, rq + i);
         --rq[i];
         if (get(1, 1, n, lq[i], rq[i]) == rq[i] - lq[i] + 1) {
            ans[i] = i;
         }
         // printf("%d %d\n", lq[i], rq[i]);
         fake_get(lq[i], rq[i]);
      } else {
         int p;
         scanf("%d", &p);
         lg[i] = findL(1, 1, n, p - 1);
         if (lg[i] == -1) {
            lg[i] =  1;
         } else {
            lg[i]++;
         }
         rg[i] = findR(1, 1, n, p + 1);
         if (rg[i] == -1) {
            rg[i] = n;
         } else {
            --rg[i];
         }
         // printf("%d %d\n", lg[i], rg[i]);
         int v = (s[p] == '1' ? i : -i);
         s[p] = '0' + '1' - s[p];
         fake_add(lg[i], p);
         fake_add(lg[i], rg[i] + 1);
         fake_add(p + 1, p);
         fake_add(p + 1, rg[i] + 1);
         modify(1, 1, n, p);
         vq[i] = v;
         pq[i] = p;
      }
   }
   build();
   // return 0;
   for (int i = 1; i <= q; ++i) {
      if (lq[i]) {
         // query
         ans[i] += get(lq[i], rq[i]);
         printf("%d\n", ans[i]);
      } else {
         int v = vq[i];
         int p = pq[i];
         add(lg[i], p, v);
         add(lg[i], rg[i] + 1, -v);
         add(p + 1, p, -v);
         add(p + 1, rg[i] + 1, v);
      }
   }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (; yy < ft[x].size(); yy += yy & -yy) {
              ~~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:118:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %s", &n, &q, s + 1);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:126:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%s", buf);
       ~~~~~^~~~~~~~~~~
street_lamps.cpp:128:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d %d", lq + i, rq + i);
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:137:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d", &p);
          ~~~~~^~~~~~~~~~

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