oj.uz

Submission #230688

# Submission time Handle Problem Language Result Execution time Memory
230688 2020-05-11T06:51:25 Z AlexLuchianov Street Lamps (APIO19_street_lamps) C++14
60 / 100
 3996 ms 524292 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;
int sol[1 + nmax];

class FenwickTree{
private:
  vector<int> aib;
  vector<pair<int, pair<int,int>>> events;
  map<int,int> code;
  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());
    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:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < events.size(); i++)
                    ~~^~~~~~~~~~~~~~~
street_lamps.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < temp.size(); i++)
                    ~~^~~~~~~~~~~~~
street_lamps.cpp:45: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:57: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 4 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 512 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 367 ms 37840 KB Output is correct
2 Correct 466 ms 45124 KB Output is correct
3 Correct 904 ms 70760 KB Output is correct
4 Correct 3173 ms 437312 KB Output is correct
5 Correct 3108 ms 443416 KB Output is correct
6 Correct 3277 ms 464172 KB Output is correct
7 Correct 1885 ms 304932 KB Output is correct
8 Correct 1475 ms 286700 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1920 KB Output is correct
2 Correct 10 ms 1664 KB Output is correct
3 Correct 8 ms 1408 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Runtime error 3583 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Correct 8 ms 1408 KB Output is correct
3 Correct 8 ms 1536 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 1923 ms 328576 KB Output is correct
6 Correct 2619 ms 419456 KB Output is correct
7 Correct 3168 ms 472180 KB Output is correct
8 Correct 3996 ms 501804 KB Output is correct
9 Correct 575 ms 59084 KB Output is correct
10 Correct 477 ms 56008 KB Output is correct
11 Correct 587 ms 59084 KB Output is correct
12 Correct 467 ms 55620 KB Output is correct
13 Correct 589 ms 59468 KB Output is correct
14 Correct 482 ms 55892 KB Output is correct
15 Correct 2016 ms 339316 KB Output is correct
16 Correct 1555 ms 321992 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 4 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 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 367 ms 37840 KB Output is correct
9 Correct 466 ms 45124 KB Output is correct
10 Correct 904 ms 70760 KB Output is correct
11 Correct 3173 ms 437312 KB Output is correct
12 Correct 3108 ms 443416 KB Output is correct
13 Correct 3277 ms 464172 KB Output is correct
14 Correct 1885 ms 304932 KB Output is correct
15 Correct 1475 ms 286700 KB Output is correct
16 Correct 11 ms 1920 KB Output is correct
17 Correct 10 ms 1664 KB Output is correct
18 Correct 8 ms 1408 KB Output is correct
19 Correct 6 ms 1152 KB Output is correct
20 Runtime error 3583 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -