oj.uz

Submission #230693

# Submission time Handle Problem Language Result Execution time Memory
230693 2020-05-11T07:13:22 Z AlexLuchianov Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 281988 KB 
#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];

unordered_map<int,int> code;

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;
    code.clear();
    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());
    for(int i = 0; i < temp.size(); i++)
      code[temp[i]] = 1 + i;
    n = temp.size();
    aib.resize(1 + n);
    for(int i = 0; i < events.size(); i++)
      events[i].second.first = code[events[i].second.first];
  }

  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

street_lamps.cpp: In member function 'void FenwickTree::initialize()':
street_lamps.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < events.size(); i++)
                    ~~^~~~~~~~~~~~~~~
street_lamps.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < temp.size(); i++)
                    ~~^~~~~~~~~~~~~
street_lamps.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < events.size(); i++)
                    ~~^~~~~~~~~~~~~~~
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.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 36012 KB Output is correct
2 Correct 389 ms 42944 KB Output is correct
3 Correct 695 ms 63312 KB Output is correct
4 Execution timed out 5106 ms 172884 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1024 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Execution timed out 5096 ms 281988 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 768 KB Output is correct
2 Correct 8 ms 768 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Execution timed out 5104 ms 138600 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 314 ms 36012 KB Output is correct
9 Correct 389 ms 42944 KB Output is correct
10 Correct 695 ms 63312 KB Output is correct
11 Execution timed out 5106 ms 172884 KB Time limit exceeded
12 Halted 0 ms 0 KB -