Submission #1155153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155153		Zero_OP	New Home (APIO18_new_home)	C++17	57 / 100	5073 ms	791704 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>;

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>> events[MAX << 4];
int result[MAX];

int ts;

void add_query(int pos, int idx){
      pos += ts;
      for(; pos > 0; pos /= 2){
            events[pos].pb(mt(l[idx], 1, idx));
      }
}

void add(int id, const pi& range){
      if(range.ff == 0 && range.ss == BOUND){
            events[id].pb(mt(range.ff, 0, inf_bound));
            events[id].pb(mt(range.ss, 2, inf_bound));
            return;
      }

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

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

      int mid = (range.ff + range.ss) / 2;
      if(range.ff < mid) {
            events[id].pb(mt(range.ff+1, 0, range.ff));
            events[id].pb(mt(mid, 2, range.ff));
      }
      if(mid < range.ss) {
            events[id].pb(mt(mid+1, 0, range.ss));
            events[id].pb(mt(range.ss, 2, range.ss));
      }
}

void add_event(int l, int r, pi range){
      l += ts;
      r += ts;
      for(; l < r; l /= 2, r /= 2){
            if(l & 1){
                  add(l++, range);
            } 
            if(r & 1){
                  add(--r, range);
            }
      }
}

// void add_query(int id, int l, int r, int pos, int idx){
//       events[id].pb(mt(::l[idx], 1, 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[id].pb(mt(range.ff, 0, inf_bound));
//                   events[id].pb(mt(range.ss, 2, inf_bound));
//                   return;
//             }

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

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

//             int mid = (range.ff + range.ss) / 2;
//             if(range.ff < mid) {
//                   events[id].pb(mt(range.ff+1, 0, range.ff));
//                   events[id].pb(mt(mid, 2, range.ff));
//             }
//             if(mid < range.ss) {
//                   events[id].pb(mt(mid+1, 0, range.ss));
//                   events[id].pb(mt(range.ss, 2, 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);
//       }
// }

namespace MaxSolver{
      priority_queue<int> added, deleted;
      void init(){
            priority_queue<int>().swap(added);
            priority_queue<int>().swap(deleted);
      }

      void insert(int x){ added.push(x); }
      void erase(int x){ deleted.push(x); }
      int get(){
            while(!deleted.empty() && added.top() == deleted.top()){
                  added.pop();
                  deleted.pop();
            }

            return (added.empty() ? -inf : added.top());
      }

      bool empty(){
            while(!deleted.empty() && added.top() == deleted.top()){
                  added.pop();
                  deleted.pop();
            }
            return added.empty();
      }
}

namespace MinSolver{
      priority_queue<int, vi, greater<int>> added, deleted;
      void init(){
            priority_queue<int, vi, greater<int>>().swap(added);
            priority_queue<int, vi, greater<int>>().swap(deleted);
      }

      void insert(int x){ added.push(x); }
      void erase(int x){ deleted.push(x); }
      int get(){
            while(!deleted.empty() && added.top() == deleted.top()){
                  added.pop();
                  deleted.pop();
            }

            return (added.empty() ? +inf : added.top());
      }
}

void solve(int id){
      MaxSolver::init();
      MinSolver::init();

      sort(all(events[id]));
      for(auto [t, type, idx] : events[id]){
            if(type == 0){
                  MaxSolver::insert(idx);
                  MinSolver::insert(idx);
            } else if(type == +1){
                  if(MaxSolver::empty()) continue;
                  maximize(result[idx], MaxSolver::get() - t);
                  maximize(result[idx], t - MinSolver::get());
            } else{
                  MinSolver::erase(idx);
                  MaxSolver::erase(idx);
            }
      }
}

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

      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);

      ts = sz(tm);
      FOR(i, 0, Q){
            y[i] = lower_bound(all(tm), y[i]) - tm.begin();
            add_query(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;
                              add_event(mpp[mp(L, x)], t, mp(L, x)); mpp.erase(mpp.find({L, x})); //(L, x]
                              add_event(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);
                              auto lb = prev(ub);
                              int L = *lb, R = *ub, pre = mpp[mp(L, R)];
                              mpp.erase(mpp.find(mp(L, R)));
                              add_event(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(lst, ts, mp(0, BOUND));
            }
      }

      FOR(i, 0, 2*ts) if(!events[i].empty()){
            solve(i);
      }

      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