Submission #400174

#	Time	Username	Problem	Language	Result	Execution time	Memory
400174		tmbao	New Home (APIO18_new_home)	C++14	0 / 100	1248 ms	421468 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

enum EventType {
  ADD, REMOVE,
};

struct Event {
  int pos, store, time;
  EventType type;
};

struct Query {
  int index, pos, time;
};

struct SegmentTree {
  string name;
  int size;
  vector<multiset<int>> data;

  void resize(int _size) {
    data.resize(_size * 3);
    size = _size;
  }

  void addInternal(int i, int u, int v, int l, int r, int val) {
    if (v < l || r < u) {
      return;
    }
    if (l <= u && v <= r) {
      data[i].insert(val);
      return;
    }
    int mid = (u + v) / 2;
    addInternal(i * 2, u, mid, l, r, val);
    addInternal(i * 2 + 1, mid + 1, v, l, r, val);
  }

  void removeInternal(int i, int u, int v, int l, int r, int val) {
    if (v < l || r < u) {
      return;
    }
    if (l <= u && v <= r) {
      data[i].erase(data[i].find(val));
      return;
    }
    propagate(i, val);
    int mid = (u + v) / 2;
    removeInternal(i * 2, u, mid, l, r, val);
    removeInternal(i * 2 + 1, mid + 1, v, l, r, val);
  }

  void add(int l, int r, int val) {
    // cout << name << "+" << l << " " << r << " " << val << endl;
    addInternal(1, 1, size, l + 1, r + 1, val);
  }

  void remove(int l, int r, int val) {
    // cout << name << "-" << l << " " << r << " " << val << endl;
    removeInternal(1, 1, size, l + 1, r + 1, val);
  }

  int getMin(int u) {
    // cout << "g " << u << endl;
    return getMinInternal(1, 1, size, u + 1);
  }

  int getMax(int u) {
    // cout << "g " << u << endl;
    return getMaxInternal(1, 1, size, u + 1);
  }

  int getMinInternal(int i, int l, int r, int u) {
    if (u < l || r < u) {
      return INF;
    }
    int ret = INF;
    if (data[i].size() > 0) {
      ret = *data[i].begin();
    }
    if (l < r) {
      int mid = (l + r) / 2;
      ret = min(ret, getMinInternal(i * 2, l, mid, u));
      ret = min(ret, getMinInternal(i * 2 + 1, mid + 1, r, u));
    }
    return ret;
  }

  int getMaxInternal(int i, int l, int r, int u) {
    if (u < l || r < u) {
      return -INF;
    }
    int ret = -INF;
    if (data[i].size() > 0) {
      ret = *data[i].rbegin();
    }
    if (l < r) {
      int mid = (l + r) / 2;
      ret = max(ret, getMaxInternal(i * 2, l, mid, u));
      ret = max(ret, getMaxInternal(i * 2 + 1, mid + 1, r, u));
    }
    return ret;
  }

  void propagate(int i, int val) {
    if (data[i].find(val) != data[i].end()) {
      data[i * 2].insert(val);
      data[i * 2 + 1].insert(val);
      data[i].erase(data[i].find(val));
    }
  }
} segTreeMin, segTreeMax;

void removeSegment(int prev, int next, const vector<int>& allPositions) {
  if (prev == -1 && next == allPositions.size()) {
    return;
  }
  if (prev == -1) {
    segTreeMax.remove(0, next, allPositions[next]);
    return;
  }
  if (next == allPositions.size()) {
    segTreeMin.remove(prev, allPositions.size() - 1, allPositions[prev]);
    return;
  }
  int midVal = (allPositions[prev] + allPositions[next]) / 2;
  int mid = distance(
    allPositions.begin(), upper_bound(allPositions.begin(), allPositions.end(), midVal));
  segTreeMin.remove(prev, mid - 1, allPositions[prev]);
  segTreeMax.remove(mid, next, allPositions[next]);
}

void insertSegment(int prev, int next, const vector<int>& allPositions) {
  if (prev == -1) {
    segTreeMax.add(0, next, allPositions[next]);
    return;
  }
  if (next == allPositions.size()) {
    segTreeMin.add(prev, allPositions.size() - 1, allPositions[prev]);
    return;
  }
  int midVal = (allPositions[prev] + allPositions[next]) / 2;
  int mid = distance(
    allPositions.begin(), upper_bound(allPositions.begin(), allPositions.end(), midVal));
  segTreeMin.add(prev, mid - 1, allPositions[prev]);
  segTreeMax.add(mid, next, allPositions[next]);
}

void insertPosition(int prev, int curr, int next, const vector<int>& allPositions) {
  // cout << prev << " " << curr << " " << next << endl;
  if (curr == allPositions.size() - 1 && prev <= 0) {
    insertSegment(-1, curr, allPositions);    
    return;
  }
  if (curr == 0 && next >= allPositions.size() - 1) {
    insertSegment(curr, allPositions.size(), allPositions);
    return;
  }
  removeSegment(prev, next, allPositions);
  insertSegment(prev, curr, allPositions);
  insertSegment(curr, next, allPositions);
}

void removePosition(int prev, int curr, int next, const vector<int>& allPositions) {
  removeSegment(prev, curr, allPositions); 
  removeSegment(curr, next, allPositions);
  insertSegment(prev, next, allPositions);
}

bool cmpQuery(const Query& q1, const Query& q2) {
  return q1.time < q2.time;
}

bool compEvent(const Event& e1, const Event& e2) {
  return e1.time < e2.time;
}

int main() {
  int n, q, k;
  cin >> n >> k >> q;
  
  vector<Event> events;
  vector<Query> queries;
  vector<int> allPositions;
  for (int i = 0; i < n; ++i) {
    int x, t, a, b;
    cin >> x >> t >> a >> b;
    events.push_back({x, t - 1, a, EventType::ADD});
    events.push_back({x, t - 1, b + 1, EventType::REMOVE});
    allPositions.push_back(x);
  }

  for (int i = 0; i < q; ++i) {
    int l, y;
    cin >> l >> y;
    queries.push_back({i, l, y});
    allPositions.push_back(l);
  }

  allPositions.push_back(-INF);
  allPositions.push_back(INF);
  for (int i = 0; i < k; ++i) {
    events.push_back({INF, i, 0, EventType::ADD});
    events.push_back({-INF, i, 0, EventType::ADD});
  }

  // Compress pos
  sort(allPositions.begin(), allPositions.end());
  allPositions.resize(
    distance(allPositions.begin(), unique(allPositions.begin(), allPositions.end())));

  segTreeMin.resize(allPositions.size()); segTreeMin.name = "segTreeMin";
  segTreeMax.resize(allPositions.size()); segTreeMax.name = "segTreeMax";
  
  for (Event &event : events) {
    event.pos = distance(
      allPositions.begin(), lower_bound(allPositions.begin(), allPositions.end(), event.pos));
  }
  for (Query &query : queries) {
    query.pos = distance(
      allPositions.begin(), lower_bound(allPositions.begin(), allPositions.end(), query.pos));
  }

  sort(events.begin(), events.end(), compEvent);
  sort(queries.begin(), queries.end(), cmpQuery);


  vector<multiset<int>> storePos;
  storePos.resize(k);
  int noStoresAvailable = 0;

  vector<int> answer;
  answer.resize(q);

  for (int i = 0, j = 0; i < queries.size(); ++i) {
    Query query = queries[i];
    for (; j < events.size() && events[j].time <= query.time; ++j) {
      Event event = events[j];
      switch (event.type) {
        case ADD: {
          if (storePos[event.store].size() == 2) {
            noStoresAvailable++;
          }
          auto it = storePos[event.store].lower_bound(event.pos);
          if (it == storePos[event.store].end() || (*it) != event.pos) {
            int prevValue = -1;
            if (it != storePos[event.store].end() && it != storePos[event.store].begin()) {
              auto prevIt = prev(it);
              prevValue = *prevIt;
            }
            int nextValue = allPositions.size();
            auto nextIt = storePos[event.store].upper_bound(event.pos);
            if (it != storePos[event.store].end() && nextIt != storePos[event.store].end()) {
              nextValue = *nextIt;
            }
            insertPosition(prevValue, event.pos, nextValue, allPositions);
          }

          storePos[event.store].insert(event.pos);
          break;
        }          
        case REMOVE: {
          if (storePos[event.store].size() == 3) {
            noStoresAvailable--;
          }
          auto it = storePos[event.store].lower_bound(event.pos);
          if (next(it) != storePos[event.store].end() && (*next(it)) != (*it)) {
            int prevValue = -1;
            if (it != storePos[event.store].begin()) {
              auto prevIt = prev(it);
              prevValue = *prevIt;
            }
            int nextValue = allPositions.size();
            auto nextIt = storePos[event.store].upper_bound(event.pos);
            if (nextIt != storePos[event.store].end()) {
              nextValue = *nextIt;
            }
            removePosition(prevValue, event.pos, nextValue, allPositions);
          }

          storePos[event.store].erase(it);
          break;
        }
      }
    }

    if (noStoresAvailable < k) {
      answer[query.index] = -1;
    } else {
      int left = segTreeMin.getMin(query.pos);
      int right = segTreeMax.getMax(query.pos);
      int result = min(allPositions[query.pos] - left, right - allPositions[query.pos]);
      answer[query.index] = result;
    }
  }

  for (int i = 0; i < q; ++i) {
    cout << answer[i] << endl;
  }
  
  return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void removeSegment(int, int, const std::vector<int>&)':
new_home.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   if (prev == -1 && next == allPositions.size()) {
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:125:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   if (next == allPositions.size()) {
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void insertSegment(int, int, const std::vector<int>&)':
new_home.cpp:141:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   if (next == allPositions.size()) {
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void insertPosition(int, int, int, const std::vector<int>&)':
new_home.cpp:154:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   if (curr == allPositions.size() - 1 && prev <= 0) {
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:158:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |   if (curr == 0 && next >= allPositions.size() - 1) {
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:238:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |   for (int i = 0, j = 0; i < queries.size(); ++i) {
      |                          ~~^~~~~~~~~~~~~~~~
new_home.cpp:240:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |     for (; j < events.size() && events[j].time <= query.time; ++j) {
      |            ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20