oj.uz

Submission #120573

# Submission time Handle Problem Language Result Execution time Memory
120573 2019-06-25T04:15:41 Z IOrtroiii Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2997 ms 105108 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 14 ms 14464 KB Output is correct
7 Correct 14 ms 14464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 35600 KB Output is correct
2 Correct 435 ms 42204 KB Output is correct
3 Correct 792 ms 50528 KB Output is correct
4 Correct 2059 ms 88164 KB Output is correct
5 Correct 2012 ms 84704 KB Output is correct
6 Correct 2212 ms 86908 KB Output is correct
7 Correct 1162 ms 52448 KB Output is correct
8 Correct 1161 ms 57572 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14720 KB Output is correct
2 Correct 16 ms 14464 KB Output is correct
3 Correct 15 ms 14720 KB Output is correct
4 Correct 15 ms 14592 KB Output is correct
5 Correct 2997 ms 105108 KB Output is correct
6 Correct 2489 ms 94100 KB Output is correct
7 Correct 2029 ms 82388 KB Output is correct
8 Correct 1252 ms 58936 KB Output is correct
9 Correct 153 ms 22508 KB Output is correct
10 Correct 168 ms 23272 KB Output is correct
11 Correct 178 ms 23008 KB Output is correct
12 Correct 1160 ms 53152 KB Output is correct
13 Correct 1280 ms 58920 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14592 KB Output is correct
2 Correct 15 ms 14592 KB Output is correct
3 Correct 15 ms 14592 KB Output is correct
4 Correct 16 ms 14748 KB Output is correct
5 Correct 1248 ms 58836 KB Output is correct
6 Correct 1674 ms 74964 KB Output is correct
7 Correct 2087 ms 87956 KB Output is correct
8 Correct 2762 ms 102100 KB Output is correct
9 Correct 549 ms 43592 KB Output is correct
10 Correct 435 ms 40648 KB Output is correct
11 Correct 563 ms 44240 KB Output is correct
12 Correct 441 ms 41304 KB Output is correct
13 Correct 560 ms 44220 KB Output is correct
14 Correct 427 ms 40912 KB Output is correct
15 Correct 1224 ms 54240 KB Output is correct
16 Correct 1350 ms 59832 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 14 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 14 ms 14464 KB Output is correct
7 Correct 14 ms 14464 KB Output is correct
8 Correct 311 ms 35600 KB Output is correct
9 Correct 435 ms 42204 KB Output is correct
10 Correct 792 ms 50528 KB Output is correct
11 Correct 2059 ms 88164 KB Output is correct
12 Correct 2012 ms 84704 KB Output is correct
13 Correct 2212 ms 86908 KB Output is correct
14 Correct 1162 ms 52448 KB Output is correct
15 Correct 1161 ms 57572 KB Output is correct
16 Correct 16 ms 14720 KB Output is correct
17 Correct 16 ms 14464 KB Output is correct
18 Correct 15 ms 14720 KB Output is correct
19 Correct 15 ms 14592 KB Output is correct
20 Correct 2997 ms 105108 KB Output is correct
21 Correct 2489 ms 94100 KB Output is correct
22 Correct 2029 ms 82388 KB Output is correct
23 Correct 1252 ms 58936 KB Output is correct
24 Correct 153 ms 22508 KB Output is correct
25 Correct 168 ms 23272 KB Output is correct
26 Correct 178 ms 23008 KB Output is correct
27 Correct 1160 ms 53152 KB Output is correct
28 Correct 1280 ms 58920 KB Output is correct
29 Correct 15 ms 14592 KB Output is correct
30 Correct 15 ms 14592 KB Output is correct
31 Correct 15 ms 14592 KB Output is correct
32 Correct 16 ms 14748 KB Output is correct
33 Correct 1248 ms 58836 KB Output is correct
34 Correct 1674 ms 74964 KB Output is correct
35 Correct 2087 ms 87956 KB Output is correct
36 Correct 2762 ms 102100 KB Output is correct
37 Correct 549 ms 43592 KB Output is correct
38 Correct 435 ms 40648 KB Output is correct
39 Correct 563 ms 44240 KB Output is correct
40 Correct 441 ms 41304 KB Output is correct
41 Correct 560 ms 44220 KB Output is correct
42 Correct 427 ms 40912 KB Output is correct
43 Correct 1224 ms 54240 KB Output is correct
44 Correct 1350 ms 59832 KB Output is correct
45 Correct 143 ms 26260 KB Output is correct
46 Correct 233 ms 30812 KB Output is correct
47 Correct 1087 ms 53968 KB Output is correct
48 Correct 2073 ms 88388 KB Output is correct
49 Correct 183 ms 24808 KB Output is correct
50 Correct 194 ms 24944 KB Output is correct
51 Correct 204 ms 24832 KB Output is correct
52 Correct 228 ms 25868 KB Output is correct
53 Correct 234 ms 25800 KB Output is correct
54 Correct 231 ms 25736 KB Output is correct