Submission #916881

#	Time	Username	Problem	Language	Result	Execution time	Memory
916881		duckindog	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	186 ms	27560 KiB

street_lamps

//from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10,
          S = 400;
int n, q;
int a[N];
struct Query {
  int ty, x, y;
  Query() : ty(0), x(0), y(0) {}
  Query(int ty, int x, int y) : ty(ty), x(x), y(y) {}
} Q[N];

string s[N];
void sub1() {
  cin >> s[1];

  for (int i = 1; i <= q; ++i) {
    s[i + 1] = s[i];

    string ty; cin >> ty;
    if (ty == "toggle") {
      int p; cin >> p;
      s[i + 1][p - 1] = (s[i + 1][p - 1] == '0' ? '1' : '0');
    } else {
      int a, b; cin >> a >> b;

      int answer = 0;
      for (int j = 1; j <= i; ++j) {
        bool pass = 1;
        for (int t = a - 1; t < b - 1; ++t)
          if (s[j][t] == '0') pass = 0;
        answer += pass;
      }

      cout << answer << '\n';
    }
  }
}

void sub2() {
  vector<int> cnt(n + 1), t(n + 1);
  for (int i = 1; i <= n; ++i) t[i] = (a[i] == 1);

  for (int i = 1; i <= q; ++i) {
    int ty = Q[i].ty, x = Q[i].x, y = Q[i].y;

    if (!ty) {
      if (a[x] == 1) {
        cnt[x] += i - t[x] + 1;
        t[x] = i + 1;
      } else {
        t[x] = i + 1;
      }
      a[x] = 1 - a[x];
    } else {
      int answer = 0;
      if (a[x]) {
        answer = cnt[x] + i - t[x] + 1;
      } else {
        answer = cnt[x];
      }
      cout << answer << '\n';
    }

  }
}
bool dd[N];
int f[4 * N];
void build(int s, int l, int r) {
  if (l == r) {
    f[s] = (a[l] == 1 ? 1 : 1e8);
    return;
  }
  int mid = l + r >> 1;
  build(s * 2, l, mid); build(s * 2 + 1, mid + 1, r);
  f[s] = max(f[s * 2], f[s * 2 + 1]);
}
void update(int s, int l, int r, int x, int y) {
  if (y < l || y > r) return;
  if (l == r) {
    f[s] = x;
    return;
  }
  int mid = l + r >> 1;
  update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
  f[s] = max(f[s * 2], f[s * 2 + 1]);
}
int query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return 0;
  if (u <= l && r <= v) return f[s];
  int mid = l + r >> 1;
  return max(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  cin >> n >> q;
  if (n <= 100 && q <= 100) {
    sub1();
    return 0;
  }
  for (int i = 1; i <= n; ++i) {
    char x; cin >> x;
    a[i] = (x == '1');
  }

  bool s2 = 1, s3 = 1;
  for (int i = 1; i <= q; ++i) {
    string ty; cin >> ty;
    if (ty == "toggle") {
      int x; cin >> x;
      s3 &= (!dd[x] && !a[x]);
      dd[x] = 1;
      Q[i] = {0, x, 0};
    } else {
      int x, y; cin >> x >> y;
      Q[i] = {1, x, y - 1};
      s2 &= (y - x == 1);
    }
  }

  if (s2) {
    sub2();
    return 0;
  }


  if (s3) {
    build(1, 1, n);
    for (int i = 1; i <= q; ++i) {
      int ty = Q[i].ty, x = Q[i].x, y = Q[i].y;
      if (!ty) {
        update(1, 1, n, i + 1, x);
      } else {
        int answer = query(1, 1, n, x, y);
        cout << max(0, i - answer + 1) << '\n';
      }

    }
  }


}

Compilation message (stderr)

street_lamps.cpp: In function 'void sub2()':
street_lamps.cpp:48:35: warning: unused variable 'y' [-Wunused-variable]
   48 |     int ty = Q[i].ty, x = Q[i].x, y = Q[i].y;
      |                                   ^
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'void update(int, int, int, int, int)':
street_lamps.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'int query(int, int, int, int, int)':
street_lamps.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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