oj.uz

답안 #1029599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029599 2024-07-21T05:24:40 Z erray 새 집 (APIO18_new_home) C++17
0 / 100
 365 ms 1048576 KB 
// author: erray
#pragma optimize("Bismillahirrahmanirrahim")
#include <bits/stdc++.h>
 
#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif
 
using namespace std;
 
constexpr int inf = int(3e8);

struct node {
  int L = 0, R = 0;
  int mx = -inf;
  multiset<int> acts;
  void add(int x) {
    acts.insert(x);
    mx = *acts.rbegin();
  }
  void rem(int x) {
    acts.erase(acts.find(x));
    mx = (acts.empty() ? -inf : *acts.rbegin());
  }
};

constexpr int NODES = int(2e7);
node nodes[NODES];
int last_node = 0;

void pull(node& x) {
  x.mx = max(nodes[x.L].mx, nodes[x.R].mx);
}
void branch(node& x) {
  if (x.L == 0) x.L = last_node++;
  if (x.R == 0) x.R = last_node++;
}
 
struct SegTree {
  void modify(int v, int l, int r, int p, int x, int t) {
    if (l == r) {
      if (t) {
        nodes[v].add(x);
      } else {
        nodes[v].rem(x);
      }
      return;
    }
    branch(nodes[v]);
    int mid = (l + r) >> 1;
    if (p <= mid) {
      modify(nodes[v].L, l, mid, p, x, t);
    } else {
      modify(nodes[v].R, mid + 1, r, p, x, t);
    }
    pull(nodes[v]);
  }
  int get(int v, int l, int r, int ll, int rr) {
    if (l >= ll && rr >= r) {
      return nodes[v].mx;
    }
    int mid = (l + r) >> 1;
    int res = -inf;
    if (ll <= mid && nodes[v].R != 0) {
      res = max(res, get(nodes[v].L, l, mid, ll, rr));
    }
    if (mid < rr && nodes[v].R != 0) {
      res = max(res, get(nodes[v].R, mid + 1, r, ll, rr));
    }
    return res;
  }
  int mn, mx;
  int root;
  SegTree(int _mn, int _mx) : mn(_mn), mx(_mx) {
    root = last_node++;
  }
  void modify(int p, int x, int t) {
    modify(root, mn, mx, p, x, t);
  }
  int get(int ll, int rr) {
    return get(root, mn, mx, ll, rr);
  }
};
 
constexpr int POS = int(1e8);
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> X(N), T(N), A(N), B(N);
  for (int i = 0; i < N; ++i) {
    cin >> X[i] >> T[i] >> A[i] >> B[i];
    --T[i];
  }
  vector<int> L(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> L[i] >> Y[i];
  }
  vector<array<int, 2>> events;
  for (int i = 0; i < N; ++i) {
    events.push_back({A[i], i});
    events.push_back({B[i] + 1, ~i}); 
  }
  for (int i = 0; i < Q; ++i) {
    events.push_back({Y[i], i + N});
  }
  debug(events);
  sort(events.begin(), events.end());
  SegTree pref(1, POS), suf(1, POS);
  vector<map<int, int>> acts(K);
  auto Updates = [&](int t, int x) -> vector<array<int, 3>> {
    debug(t, x);
    if (acts[t].empty()) {
      return {};
    }
    vector<array<int, 3>> res;
    auto it = acts[t].lower_bound(x);
    vector<array<int, 2>> regulars;
    if (it != acts[t].end() && it->first == x) {
       if (next(it) == acts[t].end()) {
         res.push_back({t, POS, POS - x});
       } else {
         regulars.push_back({it->first, next(it)->first});
       }
       if (it == acts[t].begin()) {
         res.push_back({t, 1, x - 1});
       } else {
         regulars.push_back({prev(it)->first, it->first});
       }
    } else {
      if (it == acts[t].end()) {
        res.push_back({t, POS, POS - prev(it)->first});
      } else if (it == acts[t].begin()) {
        res.push_back({t, 1, it->first - 1});
      } else {
        regulars.push_back({prev(it)->first, it->first});
      }
    }
    for (auto[l, r] : regulars) {
      int dist = (r - l) / 2, mid = (l + r) / 2;
      if ((l + r) % 2 == 1) {
        res.push_back({t, mid, dist});
        res.push_back({t, mid + 1, dist});
      } else {
        res.push_back({t, mid, dist}); 
      }
    }
    return res;
  };
  auto Rem = [&](vector<array<int, 3>> a) {
    for (auto[t, x, v] : a) {
      pref.modify(x, v + x, 0);
      suf.modify(x, v - x, 0);
    }
  };
  auto Add = [&](vector<array<int, 3>> a) {
    for (auto[t, x, v] : a) {
      pref.modify(x, v + x, 1);
      suf.modify(x, v - x, 1);
    }
  };
  
  vector<int> ans(Q);
  int exists = 0;
  for (auto[foo, t] : events) {
    debug(foo, t);
    if (t < 0) {
      t = ~t;
      debug(T[t]);
      if (--acts[T[t]][X[t]] == 0) {
        Rem(Updates(T[t], X[t])); 
        acts[T[t]].erase(X[t]);
        Add(Updates(T[t], X[t]));
      }
      exists -= (acts[T[t]].empty());    
    } else if (t < N) {
      exists += (acts[T[t]].empty());
      if (!acts[T[t]].count(X[t])) {
        Rem(Updates(T[t], X[t])); 
        acts[T[t]][X[t]] = 0;
        Add(Updates(T[t], X[t]));
      } 
      acts[T[t]][X[t]]++;
    } else {
      t -= N;
      ans[t] = (exists == K ? max(pref.get(1, L[t]) - L[t], suf.get(L[t], POS) + L[t]) : -1);
    }
  }
  for (int i = 0; i < Q; ++i) {
    cout << ans[i] << '\n';
  }
}

Compilation message

new_home.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("Bismillahirrahmanirrahim")
      |

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 365 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 365 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 321 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 357 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 365 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 365 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -