Submission #1216339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216339		mychecksedad	New Home (APIO18_new_home)	C++20	47 / 100	5110 ms	564928 KiB

new_home

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 3e6+100, M = 1e5+10, K = 52, MX = 30;


int n, k, q, TT[N];
array<int, 4> a[N];
multiset<int> T[N], S[N];
void build(int sz){
  for(int i =0 ; i <= 2*sz+2; ++i) TT[i] = 0;
  TT[2*sz + 1] = MOD;
}
void add(int v, int x){
  v += k;
  TT[v] += x;
  for(v >>= 1; v; v >>= 1) TT[v] = min(TT[v<<1], TT[v<<1|1]); 
}

void put(int l, int r, int ql, int qr, int k, int val, bool flag){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    if(flag) T[k].insert(val);
    else T[k].erase(T[k].find(val));
    return;
  }
  int mid = l+r>>1;
  put(l, mid, ql, qr, k<<1, val, flag);
  put(mid+1, r, ql, qr, k<<1|1, val, flag);
}

pii get(int l, int r, int p, int k){
  if(l == r){
    if(T[k].empty()) return {MOD, -MOD};
    return pii{(*T[k].begin()), *prev(T[k].end())};
  }
  auto v = T[k].empty() ? pii{MOD, -MOD} : pii{(*T[k].begin()), *prev(T[k].end())};
  int mid = l+r>>1;
  pii q;
  if(p <= mid){
    q = get(l, mid, p, k<<1);
  }else{
    q = get(mid + 1, r, p, k<<1|1);
  }
  return pii{min(v.ff, q.ff), max(v.ss, q.ss)};
}

void solve(){
  cin >> n >> k >> q;
  vector<int> X;
  vector<pii> A, B;
  vector<array<int, 3>> Q;
  vi ANS(q + 1);
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    X.pb(a[i][0]);
    A.pb({a[i][2], i});
    B.pb({a[i][3], i});
  }
  for(int i = 1; i <= q; ++i){
    int l, y; cin >> l >> y;
    Q.pb({y, l, i});
    X.pb(l);
  }
  sort(all(Q));
  sort(all(A));
  sort(all(B));

  sort(all(X));
  X.erase(unique(all(X)), X.end());
  int m = X.size();
  build(k); 



  function<int(int)> POS = [&](int x){
    return int(upper_bound(all(X), x) - X.begin());
  };

  function<int(int)> POS2 = [&](int x){
    return int(lower_bound(all(X), x) - X.begin() + 1);
  };

  function<void(int, int, int)> PUT = [&](int l, int r, bool flag){
    int mid = l+r>>1;
    // cerr << POS(l+1) << ' ' << POS(mid) << ' ' << POS2(mid+1) << ' ' << POS(r-1) << " wtf\n";
    put(1, m, POS2(l+1), POS(mid), 1, l, flag);
    put(1, m, POS2(mid+1), POS(r-1), 1, r, flag);
  };

  for(int i = 1; i <= k; ++i){
    S[i].insert(-MOD);
    S[i].insert(MOD);
    PUT(-MOD, MOD, true);
  }

  int ptr = 0, pt = 0, last_y = -1;
  for(auto [y, poss, idx]: Q){
    while(ptr < B.size() && B[ptr].ff < y){
      // pop things
      int id = B[ptr].ss;
      int tp = a[id][1];
      int pos = a[id][0];
      if(a[id][2] > last_y){
        ++ptr;
        continue;
      }


      // cerr << "pop: " << id << ' ' << pos << ' ' << y << '\n';

      put(1, m, POS(pos), POS(pos), 1, pos, false);
      S[tp].erase(S[tp].find(pos));
      auto it = S[tp].lower_bound(pos);

      int L = -MOD, R = MOD;
      {
        int l = (*prev(it));
        int r = pos;
        PUT(l, r, false);
        L = l;
      }

      {  
        int r = (*it);
        int l = pos;
        PUT(l, r, false);
        R = r;
      }

      PUT(L, R, true);

      add(tp, -1);

      ++ptr;
    }
    while(pt < A.size() && A[pt].ff <= y){
      // push things
      int id = A[pt].ss;
      int tp = a[id][1];
      int pos = a[id][0];
      if(a[id][3] < y){
        ++pt;
        continue;
      }

      // cerr << "push: " << y << ' ' << id << ' ' << pos << '\n';

      put(1, m, POS(pos), POS(pos), 1, pos, true);
      auto it = S[tp].insert(pos);

      int L = -MOD, R = MOD;
      {
        int l = (*prev(it));
        int r = pos;
        PUT(l, r, true);
        L = l;
      }

      {  
        int r = (*next(it));
        int l = pos;
        PUT(l, r, true);
        R = r;
      }

      // for(int x: S[tp]) cerr << x <<  ' '; cerr << '\n';
      // cerr << L << ' ' << R << '\n';

      PUT(L, R, false);



      add(tp, 1);
      ++pt;
    }
    // cerr << y << ' ' << poss << ' ' << idx << '\n';
    if(TT[1] == 0) ANS[idx] = -1;
    else{
      auto v = get(1, m, POS(poss), 1);
      ANS[idx] = max({0, poss - v.ff, v.ss - poss});
    }
    last_y = y;
  }

  // cout << "AC";

  for(int i = 1; i <= q; ++i){
    cout << (ANS[i] > 100000000 ? -1 : ANS[i]) << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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