oj.uz

Submission #926134

# Submission time Handle Problem Language Result Execution time Memory
926134 2024-02-12T15:21:09 Z myst6 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 2863 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Node;
struct Node2;

const int s1 = 10'000'000;
const int s2 = 10'000'000;

vector<Node> node(s1); int next1 = 1;
vector<Node2> node2(s2); int next2 = 1;

int n;

struct Node {
  int left, right;
  pair<ll,int> val;
  Node() : left(0), right(0), val({0,0}) {}
  void update(int v, int xl, int xr, int add) {
    if (v < xl || v > xr) return;
    val.first += add;
    val.second += 1;
    if (xl != xr) {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = next1++;
        node[left].update(v, xl, xm, add);
      } else {
        if (!right) right = next1++;
        node[right].update(v, xm+1, xr, add);
      }
    }
  }
  pair<ll,int> query(int l, int r, int xl, int xr) {
    if (l > r) return {0, 0};
    if (l == xl && r == xr) {
      return val;
    } else {
      pair<ll,int> ans = {0, 0};
      int xm = (xl + xr) / 2;
      if (left) {
        pair<ll,int> leftans = node[left].query(l, min(r, xm), xl, xm);
        ans.first += leftans.first;
        ans.second += leftans.second;
      }
      if (right) {
        pair<ll,int> rightans = node[right].query(max(l, xm+1), r, xm+1, xr);
        ans.first += rightans.first;
        ans.second += rightans.second;
      }
      return ans;
    }
  }
};

struct Node2 {
  int left, right;
  int val;
  Node2() : left(0), right(0), val(0) {}
  void update(int v, int w, int xl, int xr, int add) {
    if (v < xl || v > xr) return;
    if (!val) val = next1++;
    node[val].update(w, 0, n-1, add);
    if (xl != xr) {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = next2++;
        node2[left].update(v, w, xl, xm, add);
      } else {
        if (!right) right = next2++;
        node2[right].update(v, w, xm+1, xr, add);
      }
    }
  }
  pair<ll,int> query(int l1, int r1, int l2, int r2, int xl, int xr) {
    if (l1 > r1) return {0, 0};
    if (l1 == xl && r1 == xr) {
      return node[val].query(l2, r2, 0, n-1);
    } else {
      pair<ll,int> ans = {0, 0};
      int xm = (xl + xr) / 2;
      if (left) {
        pair<ll,int> leftans = node2[left].query(l1, min(r1, xm), l2, r2, xl, xm);
        ans.first += leftans.first;
        ans.second += leftans.second;
      }
      if (right) {
        pair<ll,int> rightans = node2[right].query(max(l1, xm+1), r1, l2, r2, xm+1, xr);
        ans.first += rightans.first;
        ans.second += rightans.second;
      }
      return ans;
    }
  }
};

// lamp turns on => at most 2 segments destryod and 1 segment added
// lamp turns off => 1 segment destroyed and at most 2 segments added
// count number of x=<a ^ y>=b
// (t,a,b,1) => a and b were connected at t
// (t,a,b,-1) => a and b were disconnected at t
// now for each query, just need to find sum of t of a1<=a2, b2>=b1, t1<t2
// and if the number of '1' events is one less thaan the '-1' events, 
// pretend there's (t2,a,b,-1)

// O(10^6) updates and O(5*10^5) queries, might not be fast enough.



int main() {
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int,2>> segments;
  vector<array<int,4>> updates;
  for (int i=0; i<n; i++) {
    if (s[i] == '1') {
      int l = i;
      while (i < n-1 && s[i+1] == '1') i++;
      segments.insert({l, i});
      updates.push_back({0, l, i, +1});
    }
  }
  for (int t=1; t<=q; t++) {
    string type;
    cin >> type;
    if (type == "toggle") {
      int i;
      cin >> i;
      i--;
      if (s[i] == '0') {
        int l = i, r = i;
        auto right = segments.lower_bound({i, i});
        if (right != segments.end() && right->at(0) == i+1) {
          r = right->at(1);
          updates.push_back({t, i+1, r, -1});
          segments.erase(right);
        }
        auto left = segments.lower_bound({i, i});
        if (left != segments.begin()) --left;
        if (left != segments.end() && left->at(1) == i-1) {
          l = left->at(0);
          updates.push_back({t, l, i-1, -1});
          segments.erase(left);
        }
        segments.insert({l, r});
        updates.push_back({t, l, r, +1});
        s[i] = '1';
      } else {
        auto it = prev(segments.lower_bound({i+1, i+1}));
        int l = it->at(0), r = it->at(1);
        segments.erase(it);
        updates.push_back({t, l, r, -1});
        if (l < i) {
          segments.insert({l, i-1});
          updates.push_back({t, l, i-1, +1});
        }
        if (r > i) {
          segments.insert({i+1, r});
          updates.push_back({t, i+1, r, +1});
        }
        s[i] = '0';
      }
    } else {
      int a, b;
      cin >> a >> b;
      updates.push_back({t, a-1, b-2, 0});
    }
  }
  sort(updates.begin(), updates.end());
  Node2 on, off;
  for (array<int,4> upd : updates) {
    if (upd[3] == -1) {
      off.update(upd[1], upd[2], 0, n-1, upd[0]);
    } else if (upd[3] == 1) {
      on.update(upd[1], upd[2], 0, n-1, upd[0]);
    } else {
      pair<ll,int> pOff = off.query(0, upd[1], upd[2], n-1, 0, n-1);
      pair<ll,int> pOn = on.query(0, upd[1], upd[2], n-1, 0, n-1);
      ll offSum = pOff.first;
      ll onSum = pOn.first;
      if (pOn.second > pOff.second) offSum += upd[0];
      // cout << upd[0] << "," << upd[1] << "," << upd[2] << "\n";
      // cout << pOff.first << "," << pOff.second << "\n";
      // cout << pOn.first << "," << pOn.second << "\n";
      // cout << offSum << "," << onSum << "\n";
      cout << max(0LL, offSum - onSum) << "\n";
    }
  }
  return 0;
}

/*
5 2
11011
query 1 2
query 1 2
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 352596 KB Output is correct
2 Correct 63 ms 352592 KB Output is correct
3 Correct 56 ms 352596 KB Output is correct
4 Correct 60 ms 352688 KB Output is correct
5 Correct 58 ms 352596 KB Output is correct
6 Correct 56 ms 352644 KB Output is correct
7 Correct 56 ms 352656 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 362576 KB Output is correct
2 Correct 419 ms 365348 KB Output is correct
3 Correct 840 ms 365148 KB Output is correct
4 Runtime error 2785 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 352592 KB Output is correct
2 Correct 59 ms 352616 KB Output is correct
3 Correct 58 ms 352636 KB Output is correct
4 Correct 59 ms 352596 KB Output is correct
5 Runtime error 2863 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 352648 KB Output is correct
2 Correct 58 ms 352592 KB Output is correct
3 Correct 60 ms 352596 KB Output is correct
4 Correct 64 ms 352588 KB Output is correct
5 Runtime error 1123 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 352596 KB Output is correct
2 Correct 63 ms 352592 KB Output is correct
3 Correct 56 ms 352596 KB Output is correct
4 Correct 60 ms 352688 KB Output is correct
5 Correct 58 ms 352596 KB Output is correct
6 Correct 56 ms 352644 KB Output is correct
7 Correct 56 ms 352656 KB Output is correct
8 Correct 351 ms 362576 KB Output is correct
9 Correct 419 ms 365348 KB Output is correct
10 Correct 840 ms 365148 KB Output is correct
11 Runtime error 2785 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -