Submission #1154920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154920		Zero_OP	New Home (APIO18_new_home)	C++20	57 / 100	5081 ms	505392 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define sum_of(v) accumluate(all(v), 0ll)
#define max_of(v) *max_element(all(v))
#define min_of(v) *min_element(all(v))
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"
#define inputFile(task) freopen(task, "r", stdin);
#define outputFile(task) freopen(task, "w", stdout);

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;
using ldb = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      inputFile("task.inp");
      outputFile("task.out");
#endif // LOCAL
}

const int MAX = 3e5 + 5;
const int BOUND = 2e8;
const int inf_bound = 1e9 + 1;
const int inf = 1e9 + 9;

int N, K, Q, x[MAX], t[MAX], a[MAX], b[MAX], l[MAX], y[MAX];
vector<tuple<int, int, int>> lines; //[l, r, v]

vi queries_blocks[MAX << 4];
vector<tuple<int, int, int>> events_blocks[MAX << 4];
int result[MAX];

namespace SegmentTree{
      int n, mn[MAX << 5], mx[MAX << 5];
      void init(int _n){
            n = _n;
            for(int i = 1; i < 2 * n; ++i){
                  mn[i] = +inf;
                  mx[i] = -inf;
            }
      }

      void update(int l, int r, int v){
            l += n; r += n+1;
            for(; l < r; l >>= 1, r >>= 1){
                  if(l & 1){
                        minimize(mn[l], v);
                        maximize(mx[l], v);
                        ++l;
                  }

                  if(r & 1){
                        --r;
                        minimize(mn[r], v);
                        maximize(mx[r], v);
                  }
            }
      }

      pi get_min_max(int i){
            i += n;
            int a = inf, b = -inf;
            for(; i > 0; i >>= 1){
                  minimize(a, mn[i]);
                  maximize(b, mx[i]);
            }
            return mp(a, b);
      }
}

void add_query(int id, int l, int r, int pos, int idx){
      queries_blocks[id].pb(idx);
      if(l + 1 == r) return;
      else{
            int mid = l + r >> 1;
            if(pos < mid) add_query(id << 1, l, mid, pos, idx);
            else add_query(id << 1 | 1, mid, r, pos, idx);
      }
}

void add_event(int id, int l, int r, int u, int v, pi range){
      if(u >= v) {
            return;
      }

      if(u <= l && r <= v) {
            if(range.ff == 0 && range.ss == BOUND){
                  events_blocks[id].pb(mt(range.ff, range.ss, inf_bound));
                  return;
            }

            if(range.ff == 0){
                  events_blocks[id].pb(mt(0, range.ss, range.ss));
                  return;
            }

            if(range.ss == BOUND){
                  events_blocks[id].pb(mt(range.ff, BOUND, range.ff));
                  return;
            }

            int mid = (range.ff + range.ss) / 2;
            if(range.ff < mid) events_blocks[id].pb(mt(range.ff+1, mid, (range.ff == 0 ? range.ss : range.ff)));
            if(mid < range.ss) events_blocks[id].pb(mt(mid+1, range.ss, (range.ss == BOUND ? range.ff : range.ss)));
      }
      else{
            int mid = l + r >> 1;
            if(u < mid) add_event(id << 1, l, mid, u, v, range);
            if(mid < v) add_event(id << 1 | 1, mid, r, u, v, range);
      }
}

void dfs(int id, int l, int r){
      if(sz(events_blocks[id])){
            vi ps;
            for(auto [l, r, v] : events_blocks[id]) ps.pb(l), ps.pb(r);
            for(auto it : queries_blocks[id]) ps.pb(::l[it]);
            sort(all(ps)); compact(ps);
            int n = sz(ps);
            SegmentTree::init(n);

            for(auto [l, r, v] : events_blocks[id]){
                  l = lower_bound(all(ps), l) - ps.begin();
                  r = lower_bound(all(ps), r) - ps.begin();
                  SegmentTree::update(l, r, v);
            }

            for(auto idx : queries_blocks[id]){
                  pi cur = SegmentTree::get_min_max(lower_bound(all(ps), ::l[idx]) - ps.begin());
                  if(cur.first == inf || cur.second == -inf) continue;
                  maximize(result[idx], max(abs(cur.ff - ::l[idx]), abs(cur.ss - ::l[idx])));
            }
      }

      if(l + 1 < r){
            int mid = l + r >> 1;
            dfs(id << 1, l, mid);
            dfs(id << 1 | 1, mid, r);
      }
}

int main(){
      setIO();

      cin >> N >> K >> Q;
      FOR(i, 0, N) cin >> x[i] >> t[i] >> a[i] >> b[i], --t[i];
      FOR(i, 0, Q) cin >> l[i] >> y[i];

      vi tm(y, y + Q);
      sort(all(tm)); compact(tm);

      int ts = sz(tm);
      FOR(i, 0, Q){
            y[i] = lower_bound(all(tm), y[i]) - tm.begin();
            add_query(1, 0, ts, y[i], i);
      }

      FOR(i, 0, N){
            a[i] = lower_bound(all(tm), a[i]) - tm.begin();
            b[i] = upper_bound(all(tm), b[i]) - tm.begin();
            if(a[i] == b[i]) continue;
      }

      vi idx(N); iota(all(idx), 0);
      sort(all(idx), [&](int a, int b){ return t[a] < t[b]; });
      int ptr = 0;

      FOR(i, 0, K){
            vector<tuple<int, int, int>> events;
            while(ptr < N && t[idx[ptr]] == i){
                  int id = idx[ptr];
                  if(a[id] < b[id]){
                        events.pb(mt(a[id], +1, id));
                        events.pb(mt(b[id], -1, id));
                  }
                  ++ptr;
            }

            sort(all(events));
            multiset<int> online;
            online.insert(0);
            online.insert(BOUND);
            map<pi, int> mpp;
            mpp[{0, BOUND}] = 0;
            for(auto [t, type, id] : events){
                  int x = ::x[id];
                  if(type == -1){
                        online.erase(online.lower_bound(x));
                        if(online.find(x) == online.end()){
                              auto ub = online.upper_bound(x);
                              auto lb = prev(ub);
                              int L = *lb, R = *ub;
                              assert(L <= R);
                              add_event(1, 0, ts, mpp[mp(L, x)], t, mp(L, x)); mpp.erase(mpp.find({L, x})); //(L, x]
                              add_event(1, 0, ts, mpp[mp(x, R)], t, mp(x, R)); mpp.erase(mpp.find({x, R})); //(x, R]
                              mpp[mp(L, R)] = t;
                        }
                  } else{
                        if(online.find(x) == online.end()){
                              auto ub = online.upper_bound(x); assert(ub != online.end() && ub != online.begin());
                              auto lb = prev(ub);
                              int L = *lb, R = *ub, pre = mpp[mp(L, R)];
                              assert(L <= R);
                              mpp.erase(mpp.find(mp(L, R)));
                              add_event(1, 0, ts, pre, t, mp(L, R)); //(L, R]
                              mpp[mp(L, x)] = t;
                              mpp[mp(x, R)] = t;
                        }
                        online.insert(x);
                  }
            }

            int lst = mpp[{0, BOUND}];
            if(lst < ts) {
                  add_event(1, 0, ts, lst, ts, mp(0, BOUND));
            }
      }

      dfs(1, 0, ts);

      FOR(i, 0, Q){
            if(result[i] > (int)1e8) result[i] = -1;
            cout << result[i] << '\n';
      }

      return 0;
}

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