oj.uz

Submission #230691

# Submission time Handle Problem Language Result Execution time Memory
230691 2020-05-11T07:10:07 Z AlexLuchianov Street Lamps (APIO19_street_lamps) C++14
60 / 100
 5000 ms 307520 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <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];

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 5 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 36868 KB Output is correct
2 Correct 458 ms 43928 KB Output is correct
3 Correct 856 ms 64188 KB Output is correct
4 Correct 2744 ms 197124 KB Output is correct
5 Correct 2882 ms 193932 KB Output is correct
6 Correct 2867 ms 210380 KB Output is correct
7 Correct 1726 ms 159952 KB Output is correct
8 Correct 1276 ms 142224 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 1681 ms 148092 KB Output is correct
6 Correct 2295 ms 179404 KB Output is correct
7 Correct 2880 ms 209836 KB Output is correct
8 Correct 3670 ms 234072 KB Output is correct
9 Correct 565 ms 55496 KB Output is correct
10 Correct 467 ms 52956 KB Output is correct
11 Correct 575 ms 55620 KB Output is correct
12 Correct 467 ms 52680 KB Output is correct
13 Correct 567 ms 56088 KB Output is correct
14 Correct 465 ms 52932 KB Output is correct
15 Correct 1779 ms 156444 KB Output is correct
16 Correct 1323 ms 138804 KB Output is correct

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 5 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 363 ms 36868 KB Output is correct
9 Correct 458 ms 43928 KB Output is correct
10 Correct 856 ms 64188 KB Output is correct
11 Correct 2744 ms 197124 KB Output is correct
12 Correct 2882 ms 193932 KB Output is correct
13 Correct 2867 ms 210380 KB Output is correct
14 Correct 1726 ms 159952 KB Output is correct
15 Correct 1276 ms 142224 KB Output is correct
16 Correct 10 ms 1024 KB Output is correct
17 Correct 9 ms 896 KB Output is correct
18 Correct 8 ms 896 KB Output is correct
19 Correct 6 ms 768 KB Output is correct
20 Execution timed out 5013 ms 307520 KB Time limit exceeded
21 Halted 0 ms 0 KB -