oj.uz

Submission #855826

# Submission time Handle Problem Language Result Execution time Memory
855826 2023-10-02T01:52:35 Z NeroZein Street Lamps (APIO19_street_lamps) C++17
40 / 100
 1318 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int INF = 1e9; 

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int, 3>> se; 
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') {
      continue;
    }
    int j = i;
    while (j + 1 < n && s[j + 1] == '1') {
      j++; 
    }
    se.insert({i, j, 0}); 
    i = j; 
  }
  vector<map<int, int>> tmp(n); 
  auto edit_set = [&](int i, int t) {
    if (s[i] == '1') {
      array<int, 3> key = {i, INF, INF};
      auto f = se.upper_bound(key);
      --f;
      for (int x = (*f)[0]; x <= (*f)[1]; x++) {
        for (int y = x; y <= (*f)[1]; y++) {
          tmp[x][y] += t - (*f)[2]; 
          //deb(x) deb(y) deb(i) deb(tmp[0][1]) cout << '\n';
        }
      }
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        se.erase(f); 
        int l = (*f)[0], r = (*f)[1]; 
        se.insert({l, i - 1, t});
        se.insert({i + 1, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        int l = (*f)[0];
        se.erase(f);
        se.insert({l, i - 1, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        int r = (*f)[1];
        se.erase(f);
        se.insert({i + 1, r, t}); 
      } else {
        se.erase(f); 
      }
    } else {
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto pr = se.upper_bound(key);
        --pr;
        key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        int l = (*pr)[0], r = (*nx)[1];
        for (int x = (*pr)[0]; x <= (*pr)[1]; ++x) {
          for (int y = x; y <= (*pr)[1]; ++y) {
            tmp[x][y] += t - (*pr)[2]; 
          }
        }
        for (int x = (*nx)[0]; x <= (*nx)[1]; ++x) {
          for (int y = x; y <= (*nx)[1]; ++y) {
            tmp[x][y] += t - (*nx)[2]; 
          }
        }
        se.erase(pr);
        se.erase(nx);
        se.insert({l, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto pr = se.upper_bound(key);
        --pr;
        int l = (*pr)[0], r = i; 
        for (int x = (*pr)[0]; x <= (*pr)[1]; ++x) {
          for (int y = x; y <= (*pr)[1]; ++y) {
            tmp[x][y] += t - (*pr)[2]; 
          }
        }
        se.erase(pr); 
        se.insert({l, r, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        for (int x = (*nx)[0]; x <= (*nx)[1]; ++x) {
          for (int y = x; y <= (*nx)[1]; ++y) {
            tmp[x][y] += t - (*nx)[2]; 
          }
        }
        int l = i, r = (*nx)[1];
        se.erase(nx); 
        se.insert({l, r, t}); 
      } else {
        se.insert({i, i, t}); 
      }
    }
    s[i] ^= 1; 
  }; 
  vector<vector<pair<int, int>>> vec(n);
  for (int i = 1; i <= q; ++i) {
    string qs;
    cin >> qs;
    if (qs == "query") {
      int l, r;
      cin >> l >> r;
      --l, r -= 2; 
      int ans = 0; 
      array<int, 3> key = {l, INF, INF}; 
      auto f = se.upper_bound(key);
      if (f != se.begin()) {
        --f; 
        if ((*f)[0] <= l && (*f)[1] >= r) {
          ans += i - (*f)[2];
        }
      }
      cout << ans + tmp[l][r] << '\n'; 
    } else {
      int ind;
      cin >> ind;
      edit_set(ind - 1, i); 
    }
  }
  return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1244 KB Output is correct
2 Correct 101 ms 1364 KB Output is correct
3 Correct 153 ms 6208 KB Output is correct
4 Correct 312 ms 56040 KB Output is correct
5 Runtime error 1291 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16212 KB Output is correct
2 Correct 32 ms 13904 KB Output is correct
3 Correct 43 ms 14684 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 1318 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 295 ms 47204 KB Output is correct
6 Correct 306 ms 57576 KB Output is correct
7 Correct 329 ms 60900 KB Output is correct
8 Correct 389 ms 62516 KB Output is correct
9 Correct 151 ms 7768 KB Output is correct
10 Correct 96 ms 3408 KB Output is correct
11 Correct 118 ms 7768 KB Output is correct
12 Correct 109 ms 3596 KB Output is correct
13 Correct 118 ms 7636 KB Output is correct
14 Correct 97 ms 3412 KB Output is correct
15 Correct 158 ms 42356 KB Output is correct
16 Correct 170 ms 43868 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 500 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 95 ms 1244 KB Output is correct
9 Correct 101 ms 1364 KB Output is correct
10 Correct 153 ms 6208 KB Output is correct
11 Correct 312 ms 56040 KB Output is correct
12 Runtime error 1291 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -