oj.uz

Submission #874151

# Submission time Handle Problem Language Result Execution time Memory
874151 2023-11-16T10:51:59 Z abczz Street Lamps (APIO19_street_lamps) C++14
100 / 100
 854 ms 135112 KB 
#include <iostream>
#include <map>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <ll> V;
vector <array<ll, 4>> Q;
map <ll, array<ll, 2> > mp;
array <ll, 2> bit[300001];
vector <ll> U;
ll n, q, a, b, t, F[300001];

void update(ll x, array<ll, 2> y) {
  while (x <= n) {
    U.push_back(x);
    bit[x] = {bit[x][0]+y[0], bit[x][1]+y[1]};
    x += x&-x;
  }
}

array<ll, 2> query(ll x) {
  array<ll, 2> ret = {0, 0};
  while (x) {
    ret = {ret[0]+bit[x][0], ret[1]+bit[x][1]};
    x -= x&-x;
  }
  return ret;
}

bool ok;
string S, T;

void cdq(ll l, ll r) {
  if (l == r) return;
  vector <array<ll, 4> > tmp;
  ll mid = (l+r)/2, i = l, j = mid+1;
  cdq(l, mid);
  cdq(mid+1, r);
  while (i <= mid && j <= r) {
    if (Q[i][1] <= Q[j][1]) {
      tmp.push_back(Q[i]);
      if (!Q[i][0]) {
        ++i;
        continue;
      }
      if (Q[i][0] == 1) update(n-Q[i][2], {1, -Q[i][3]});
      else update(n-Q[i][2], {-1, Q[i][3]});
      ++i;
    }
    else {
      tmp.push_back(Q[j]);
      if (Q[j][0]) {
        ++j;
        continue;
      }
      auto [x, y] = query(n-Q[j][2]);
      F[Q[j][3]] += y + x * Q[j][3];
      ++j;
    }
  }
  while (i <= mid) {
    tmp.push_back(Q[i]);
    ++i;
  }
  while (j <= r) {
    tmp.push_back(Q[j]);
    if (Q[j][0]) {
      ++j;
      continue;
    }
    auto [x, y] = query(n-Q[j][2]);
    F[Q[j][3]] += y + x * Q[j][3];
    ++j;
  }
  for (auto x : U) bit[x] = {0, 0};
  U.clear();
  j = 0;
  for (i=l; i<=r; ++i) {
    swap(Q[i], tmp[j++]);
  }
}

int main() {
  cin >> n >> q >> S;
  V.push_back(0);
  for (int i=0; i+1<S.length(); ++i) {
    if (S[i] != S[i+1]) V.push_back(i+1);
  }
  for (int i=0; i<V.size(); ++i) {
    if (S[V[i]] == '0') continue;
    if (i == V.size()-1) mp[V[i]] = {n-1, 0};
    else mp[V[i]] = {V[i+1]-1, 0};
  }
  while (q--) {
    ++t;
    F[t] = -1;
    cin >> T >> a;
    if (T == "toggle") {
      --a;
      ok = 0;
      if (S[a] == '0') {
        S[a] = '1';
        auto it = mp.lower_bound(a);
        if (it != mp.begin()) {
          auto pv = prev(it);
          if (pv->second[0] == a-1 && it != mp.end() && a+1 == it->first) {
            Q.push_back({1, pv->first, pv->second[0], pv->second[1]});
            Q.push_back({2, pv->first, pv->second[0], t});
            Q.push_back({1, it->first, it->second[0], it->second[1]});
            Q.push_back({2, it->first, it->second[0], t});
            auto r = it->second[0];
            mp.erase(it);
            mp[pv->first] = {r, t};
            ok = 1;
          }
          else if (pv->second[0] == a-1) {
            Q.push_back({1, pv->first, pv->second[0], pv->second[1]});
            Q.push_back({2, pv->first, pv->second[0], t});
            mp[pv->first] = {a, t};
            ok = 1;
          }
        }
        if (ok) continue;
        if (it != mp.end() && a+1 == it->first) {
          Q.push_back({1, it->first, it->second[0], it->second[1]});
          Q.push_back({2, it->first, it->second[0], t});
          auto r = it->second[0];
          mp.erase(it);
          mp[a] = {r, t};
        }
        else mp[a] = {a, t};
      }
      else {
        S[a] = '0';
        auto it = prev(mp.lower_bound(a+1));
        Q.push_back({1, it->first, it->second[0], it->second[1]});
        Q.push_back({2, it->first, it->second[0], t});
        if (it->first == a && it->second[0] == a) mp.erase(it);
        else if (it->first == a) {
          auto r = it->second[0];
          mp.erase(it);
          mp[a+1] = {r, t};
        }
        else if (it->second[0] == a) mp[it->first] = {a-1, t};
        else {
          auto r = it->second[0];
          mp[it->first] = {a-1, t};
          mp[a+1] = {r, t};
        }
      }
    }
    else {
      F[t] = 0;
      cin >> b;
      --a, b -= 2;
      Q.push_back({0, a, b, t});
    }
  }
  for (auto [x, y] : mp) {
    Q.push_back({1, x, y[0], y[1]});
  }
  sort(Q.begin(), Q.end(), [](auto a, auto b) {
    return a[3] < b[3] || (a[3] == b[3] && a[0] > b[0]);
  });
  cdq(0, Q.size()-1);
  for (int i=1; i<=t; ++i) {
    if (F[i] >= 0) cout << F[i] << '\n';
  }
}

Compilation message

street_lamps.cpp: In function 'void cdq(long long int, long long int)':
street_lamps.cpp:60:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |       auto [x, y] = query(n-Q[j][2]);
      |            ^
street_lamps.cpp:75:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     auto [x, y] = query(n-Q[j][2]);
      |          ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for (int i=0; i+1<S.length(); ++i) {
      |                 ~~~^~~~~~~~~~~
street_lamps.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
street_lamps.cpp:95:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     if (i == V.size()-1) mp[V[i]] = {n-1, 0};
      |         ~~^~~~~~~~~~~~~
street_lamps.cpp:163:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |   for (auto [x, y] : mp) {
      |             ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 57500 KB Output is correct
2 Correct 406 ms 59808 KB Output is correct
3 Correct 459 ms 63040 KB Output is correct
4 Correct 743 ms 118032 KB Output is correct
5 Correct 716 ms 113972 KB Output is correct
6 Correct 724 ms 123192 KB Output is correct
7 Correct 368 ms 47692 KB Output is correct
8 Correct 405 ms 48680 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 803 ms 122440 KB Output is correct
6 Correct 819 ms 135112 KB Output is correct
7 Correct 711 ms 111596 KB Output is correct
8 Correct 403 ms 49832 KB Output is correct
9 Correct 191 ms 27908 KB Output is correct
10 Correct 216 ms 42692 KB Output is correct
11 Correct 221 ms 41652 KB Output is correct
12 Correct 361 ms 45980 KB Output is correct
13 Correct 406 ms 49072 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 467 ms 77132 KB Output is correct
6 Correct 573 ms 84160 KB Output is correct
7 Correct 721 ms 121164 KB Output is correct
8 Correct 854 ms 126560 KB Output is correct
9 Correct 440 ms 60716 KB Output is correct
10 Correct 424 ms 88748 KB Output is correct
11 Correct 444 ms 59264 KB Output is correct
12 Correct 436 ms 86588 KB Output is correct
13 Correct 421 ms 59296 KB Output is correct
14 Correct 422 ms 86432 KB Output is correct
15 Correct 375 ms 46384 KB Output is correct
16 Correct 390 ms 49348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 377 ms 57500 KB Output is correct
9 Correct 406 ms 59808 KB Output is correct
10 Correct 459 ms 63040 KB Output is correct
11 Correct 743 ms 118032 KB Output is correct
12 Correct 716 ms 113972 KB Output is correct
13 Correct 724 ms 123192 KB Output is correct
14 Correct 368 ms 47692 KB Output is correct
15 Correct 405 ms 48680 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 803 ms 122440 KB Output is correct
21 Correct 819 ms 135112 KB Output is correct
22 Correct 711 ms 111596 KB Output is correct
23 Correct 403 ms 49832 KB Output is correct
24 Correct 191 ms 27908 KB Output is correct
25 Correct 216 ms 42692 KB Output is correct
26 Correct 221 ms 41652 KB Output is correct
27 Correct 361 ms 45980 KB Output is correct
28 Correct 406 ms 49072 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 2 ms 2652 KB Output is correct
31 Correct 2 ms 2652 KB Output is correct
32 Correct 2 ms 2652 KB Output is correct
33 Correct 467 ms 77132 KB Output is correct
34 Correct 573 ms 84160 KB Output is correct
35 Correct 721 ms 121164 KB Output is correct
36 Correct 854 ms 126560 KB Output is correct
37 Correct 440 ms 60716 KB Output is correct
38 Correct 424 ms 88748 KB Output is correct
39 Correct 444 ms 59264 KB Output is correct
40 Correct 436 ms 86588 KB Output is correct
41 Correct 421 ms 59296 KB Output is correct
42 Correct 422 ms 86432 KB Output is correct
43 Correct 375 ms 46384 KB Output is correct
44 Correct 390 ms 49348 KB Output is correct
45 Correct 223 ms 42128 KB Output is correct
46 Correct 245 ms 47272 KB Output is correct
47 Correct 389 ms 53400 KB Output is correct
48 Correct 721 ms 117640 KB Output is correct
49 Correct 253 ms 43460 KB Output is correct
50 Correct 254 ms 44804 KB Output is correct
51 Correct 293 ms 45260 KB Output is correct
52 Correct 270 ms 44124 KB Output is correct
53 Correct 274 ms 44792 KB Output is correct
54 Correct 276 ms 44908 KB Output is correct