Submission #986484

#	Time	Username	Problem	Language	Result	Execution time	Memory
986484		huutuan	New Home (APIO18_new_home)	C++14	100 / 100	4736 ms	608740 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10, inf=1e9;

long long stk[N*64];
int stk_size;

vector<pair<pair<int, int>, pair<int, int>>> vq[N];
int ans[N];
vector<pair<int, int>> vpos;
vector<int> vtime;

struct SegmentTree1{
   int n;
   pair<int, int> t[N*2];
   void init(int _n){
      n=_n;
      for (int i=0; i<=n*2; ++i) t[i]={-inf, -inf};
   }
   void update(int pos, pair<int, int> val){
      --pos;
      pos+=n;
      stk[++stk_size]=(((long long)pos)<<32)|(t[pos].first&((1ll<<32)-1));
      stk[++stk_size]=(((long long)pos)<<32)|(t[pos].second&((1ll<<32)-1));
      t[pos]=val;
      for (; pos>1; pos>>=1){
         stk[++stk_size]=(((long long)(pos>>1))<<32)|(t[pos>>1].first&((1ll<<32)-1));
         stk[++stk_size]=(((long long)(pos>>1))<<32)|(t[pos>>1].second&((1ll<<32)-1));
         t[pos>>1].first=max(t[pos].first, t[pos^1].first);
         t[pos>>1].second=max(t[pos].second, t[pos^1].second);
      }
   }
   int getl(int l, int r){
      --l;
      int res=-inf;
      for (l+=n, r+=n; l<r; l>>=1, r>>=1){
         if (l&1) res=max(res, t[l++].first);
         if (r&1) res=max(res, t[--r].first);
      }
      return res;
   }
   int getr(int l, int r){
      --l;
      int res=-inf;
      for (l+=n, r+=n; l<r; l>>=1, r>>=1){
         if (l&1) res=max(res, t[l++].second);
         if (r&1) res=max(res, t[--r].second);
      }
      return res;
   }
} st1;

struct SegmentTree2{
   int n;
   vector<pair<int, pair<int, int>>> t[N*4];
   void init(int _n){
      n=_n;
   }
   void update(int k, int l, int r, int L, int R, pair<int, pair<int, int>> val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         t[k].push_back(val);
         return;
      }
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
   }
   void dfs(int k, int l, int r){
      int size=stk_size;
      for (auto &i:t[k]){
         #ifdef sus
         // cout << "update l " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
         // cout << "update r " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
         #endif
         st1.update(i.first, {i.second.first+i.second.second, i.second.second-i.second.first});
      }
      if (l==r){
         for (auto &i:vq[l]){
            ans[i.second.first]=max(st1.getl(1, i.first.first)-i.second.second, st1.getr(i.first.second, st1.n)+i.second.second)/2;
         }
      }else{
         int mid=(l+r)>>1;
         dfs(k<<1, l, mid);
         dfs(k<<1|1, mid+1, r);
      }
      while (stk_size!=size){
         st1.t[stk[stk_size]>>32].second=(int)(stk[stk_size]&((1ll<<32)-1));
         --stk_size;
         st1.t[stk[stk_size]>>32].first=(int)(stk[stk_size]&((1ll<<32)-1));
         --stk_size;
      }
   }
} st2;

int n, q, k;
vector<pair<int, int>> v[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> k >> q;
   vtime.push_back(-inf*2); vpos.emplace_back(-inf*2, -1);
   vector<pair<int, pair<int, int>>> check;
   {
      vector<array<int, 4>> mp, mp2;
      for (int i=1; i<=n; ++i){
         int x, t, l, r;
         cin >> x >> t >> l >> r; x*=2;
         mp.push_back({x, t, l, r});
      }
      sort(mp.begin(), mp.end());
      for (int i=0; i<(int)mp.size(); ){
         int j=i;
         while (j+1<(int)mp.size() && mp[i][0]==mp[j+1][0] && mp[i][1]==mp[j+1][1]) ++j;
         for (; i<=j; ++i){
            if (mp2.size() && mp2.back()[0]==mp[i][0] && mp2.back()[1]==mp[i][1] && mp2.back()[3]+1>=mp[i][2]){
               mp2.back()[3]=max(mp2.back()[3], mp[i][3]);
            }else mp2.push_back(mp[i]);
         }
      }
      for (auto &i:mp2){
         int x=i[0], t=i[1], l=i[2], r=i[3];
         v[t].emplace_back(l, x);
         v[t].emplace_back(r+1, -x);
         check.push_back({l, {1, t}});
         check.push_back({r+1, {-1, t}});
      }
   }
   vector<vector<int>> events;
   for (int i=1; i<=k; ++i){
      set<int> st;
      unordered_map<int, int> mp;
      sort(v[i].begin(), v[i].end());
      for (auto &j:v[i]){
         int pos=abs(j.second), t=j.first;
         auto it=st.lower_bound(pos);
         if (j.second>0){
            if (st.size()){
               int x=0, y=0;
               if (it==st.begin()) x=-*it, y=*it*2;
               else if (it==st.end()) x=inf+*prev(it), y=inf;
               else x=(*it+*prev(it))>>1, y=(*it-*prev(it))>>1; 
               events.push_back({mp[x], t-1, x, y});
               mp.erase(x);
            }
            {
               int x=0;
               if (it==st.begin()) x=-pos;
               else x=(pos+*prev(it))>>1;
               mp[x]=t;
            }
            {
               int x=0;
               if (it==st.end()) x=inf+pos;
               else x=(*it+pos)>>1;
               mp[x]=t;
            }
            st.emplace_hint(it, pos);
         }else{
            {
               int x=0, y=0;
               if (it==st.begin()) x=-pos, y=pos*2;
               else x=(pos+*prev(it))>>1, y=(pos-*prev(it))>>1;
               events.push_back({mp[x], t-1, x, y});
               mp.erase(x);
            }
            {
               int x=0, y=0;
               if (next(it)==st.end()) x=inf+pos, y=inf;
               else x=(*next(it)+pos)>>1, y=(*next(it)-pos)>>1;
               events.push_back({mp[x], t-1, x, y});
               mp.erase(x);
            }
            if ((int)st.size()>1){
               int x=0;
               if (it==st.begin()) x=-*next(it);
               else if (next(it)==st.end()) x=inf+*prev(it);
               else x=(*next(it)+*prev(it))>>1;
               mp[x]=t;
            }
            st.erase(it);
         }
      }
   }
   for (int i=0; i<(int)events.size(); ++i){
      vpos.emplace_back(events[i][2], i);
   }
   sort(vpos.begin(), vpos.end());
   vector<pair<int, int>> query(q);
   for (auto &i:query) cin >> i.first >> i.second, vtime.push_back(i.second), i.first*=2;
   sort(vtime.begin(), vtime.end()); vtime.resize(unique(vtime.begin(), vtime.end())-vtime.begin());
   for (int i=1; i<=q; ++i){
      int pl=lower_bound(vpos.begin(), vpos.end(), make_pair(query[i-1].first, -inf))-vpos.begin();
      int pr=lower_bound(vpos.begin(), vpos.end(), make_pair(query[i-1].first, inf))-vpos.begin()-1;
      vq[lower_bound(vtime.begin(), vtime.end(), query[i-1].second)-vtime.begin()].push_back({{pr, pl}, {i, query[i-1].first}});
      check.push_back({query[i-1].second, {2, i}});
   }
   st1.init((int)vpos.size()-1);
   st2.init((int)vtime.size()-1);
   for (int i=0; i<(int)events.size(); ++i){
      events[i][0]=lower_bound(vtime.begin(), vtime.end(), events[i][0])-vtime.begin();
      events[i][1]=upper_bound(vtime.begin(), vtime.end(), events[i][1])-vtime.begin()-1;
      if (events[i][0]<=events[i][1]) st2.update(1, 1, st2.n, events[i][0], events[i][1], {lower_bound(vpos.begin(), vpos.end(), make_pair(events[i][2], i))-vpos.begin(), {events[i][2], events[i][3]}});
   }
   st2.dfs(1, 1, st2.n);
   sort(check.begin(), check.end());
   vector<int> cnt(k+1); int cnt0=k;
   for (auto &i:check){
      if (abs(i.second.first)==1){
         cnt0-=!cnt[i.second.second];
         cnt[i.second.second]+=i.second.first;
         cnt0+=!cnt[i.second.second];
      }else{
         if (cnt0) ans[i.second.second]=-1;
      }
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
   return 0;
}

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