Submission #230696

#	Time	Username	Problem	Language	Result	Execution time	Memory
230696		AlexLuchianov	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3375 ms	303136 KiB

street_lamps

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 300000 + 5;
int sol[1 + nmax];

class FenwickTree{
private:
  vector<int> aib;
  vector<pair<int, pair<int,int>>> events;
  int n;

  void _update(int pos, int val){
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] += val;
  }
  int _query(int pos){
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }

public:
  void initialize(){
    vector<int> temp;
    for(int i = 0; i < events.size(); i++)
      temp.push_back(events[i].second.first);
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    n = temp.size();
    aib.resize(1 + n);
    for(int i = 0; i < events.size(); i++) {
      int x = 0;
      for(int jump = (1 << 20); 0 < jump; jump /= 2)
        if(x + jump < temp.size() && temp[x + jump] <= events[i].second.first)
          x += jump;
      events[i].second.first = x + 1;
    }
  }

  void update(int x, int val){
    events.push_back({1, {x, val}});
  }
  void query(int x, int ptr){
    events.push_back({2, {x, ptr}});
  }

  void solve(){
    for(int i = 0; i < events.size(); i++){
      if(events[i].first == 1)
        _update(events[i].second.first, events[i].second.second);
      else
        sol[events[i].second.second] += _query(events[i].second.first);
    }
  }
};

class SegmentTree{
private:
  vector<FenwickTree> aint;
public:
  SegmentTree(int n = 0){
    aint.resize(1 + 4 * n);
  }
  void update(int node, int from, int to, int x, int y, int val){
    aint[node].update(y, val);
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        update(node * 2, from, mid, x, y, val);
      else
        update(node * 2 + 1, mid + 1, to, x, y, val);
    }
  }
  void query(int node, int from, int to, int x, int y, int x2, int id){
    if(from == x && to == y)
      aint[node].query(x2, id);
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        query(node * 2, from, mid, x, y, x2, id);
      else if(mid + 1 <= x && mid + 1 <= y)
        query(node * 2 + 1, mid + 1, to, x, y, x2, id);
      else {
        query(node * 2, from, mid, x, mid, x2, id);
        query(node * 2 + 1, mid + 1, to, mid + 1, y, x2, id);
      }
    }
  }
  void clearall(int node, int from, int to){
    aint[node].initialize();
    aint[node].solve();
    if(from < to){
      int mid = (from + to) / 2;
      clearall(node * 2, from, mid);
      clearall(node * 2 + 1, mid + 1, to);
    }
  }
};

char s[5 + nmax];

struct Interval{
  int x;
  int y;
  int time;
  bool operator < (Interval const &a) const {
    return x < a.x;
  }
  Interval operator + (Interval const &a) const {
    return {x, a.y, time};
  }
};

set<Interval> myset;

SegmentTree aint;

int lim;

void _toggle(int x, int time){
  if(s[x] == '0'){
    s[x] = '1';
    set<Interval>::iterator it = myset.lower_bound({x + 1, 0, 0}), it2;
    it2 = it;
    it2--;
    Interval newp = *it2 + *it;
    aint.update(1, 1, lim, it->y, it->x, time - it->time);
    aint.update(1, 1, lim, it2->y, it2->x, time - it2->time);
    newp.time = time;
    myset.erase(it);
    myset.erase(it2);
    myset.insert(newp);
  } else {
    s[x] = '0';
    set<Interval>::iterator it = myset.lower_bound({x + 1, 0, 0});
    it--;
    aint.update(1, 1, lim, it->y, it->x, time - it->time);
    int f1 = it->x, f2 = it->y;
    myset.erase(it);
    myset.insert({f1, x, time});
    myset.insert({x + 1, f2, time});
  }
}

void _query(int x, int y, int id, int time){
  set<Interval>::iterator it = myset.lower_bound({x + 1, 0, 0});
  it--;
  if(it->x <= x && y <= it->y)
    sol[id] += time - it->time;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  cin >> n >> q;
  lim = n + 1;
  int last = 1;
  for(int i = 1; i <= n; i++) {
    cin >> s[i];
    if(s[i] == '0') {
      myset.insert({last, i, 0});
      last = i + 1;
    }
  }
  myset.insert({last, n + 1, 0});

  aint = SegmentTree(lim);

  int ptr = 0;
  for(int i = 1; i <= q; i++){
    string op;
    cin >> op;
    if(op == "toggle") {
      int x;
      cin >> x;
      _toggle(x, i);
    } else {
      int x, y;
      cin >> x >> y;
      ++ptr;
      aint.query(1, 1, lim, y, lim, x, ptr);
      _query(x, y, ptr, i);
    }
  }

  aint.clearall(1, 1, lim);
  for(int i = 1; i <= ptr; i++)
    cout << sol[i] << '\n';

  return 0;
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void FenwickTree::initialize()':
street_lamps.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < events.size(); i++)
                    ~~^~~~~~~~~~~~~~~
street_lamps.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < events.size(); i++) {
                    ~~^~~~~~~~~~~~~~~
street_lamps.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(x + jump < temp.size() && temp[x + jump] <= events[i].second.first)
            ~~~~~~~~~^~~~~~~~~~~~~
street_lamps.cpp: In member function 'void FenwickTree::solve()':
street_lamps.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < events.size(); i++){
                    ~~^~~~~~~~~~~~~~~

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