oj.uz

답안 #230689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230689 2020-05-11T06:56:00 Z AlexLuchianov 가로등 (APIO19_street_lamps) C++14
60 / 100
 4032 ms 524288 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];

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

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 36428 KB Output is correct
2 Correct 465 ms 43624 KB Output is correct
3 Correct 859 ms 69208 KB Output is correct
4 Correct 2988 ms 437716 KB Output is correct
5 Correct 3102 ms 438592 KB Output is correct
6 Correct 3222 ms 459660 KB Output is correct
7 Correct 1875 ms 299140 KB Output is correct
8 Correct 1447 ms 281244 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 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 7 ms 1152 KB Output is correct
5 Runtime error 3607 ms 524288 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1152 KB Output is correct
2 Correct 8 ms 1408 KB Output is correct
3 Correct 9 ms 1536 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 1921 ms 328600 KB Output is correct
6 Correct 2625 ms 414148 KB Output is correct
7 Correct 3142 ms 467604 KB Output is correct
8 Correct 4032 ms 497716 KB Output is correct
9 Correct 572 ms 56136 KB Output is correct
10 Correct 479 ms 53436 KB Output is correct
11 Correct 574 ms 56140 KB Output is correct
12 Correct 475 ms 53188 KB Output is correct
13 Correct 584 ms 56548 KB Output is correct
14 Correct 473 ms 53256 KB Output is correct
15 Correct 1957 ms 334128 KB Output is correct
16 Correct 1528 ms 316440 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 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 371 ms 36428 KB Output is correct
9 Correct 465 ms 43624 KB Output is correct
10 Correct 859 ms 69208 KB Output is correct
11 Correct 2988 ms 437716 KB Output is correct
12 Correct 3102 ms 438592 KB Output is correct
13 Correct 3222 ms 459660 KB Output is correct
14 Correct 1875 ms 299140 KB Output is correct
15 Correct 1447 ms 281244 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 7 ms 1152 KB Output is correct
20 Runtime error 3607 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -