Submission #985895

#	Time	Username	Problem	Language	Result	Execution time	Memory
985895		huutuan	New Home (APIO18_new_home)	C++14	0 / 100	5116 ms	411944 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10, inf=1e9;
vector<pair<pair<int, int>, pair<int, int>>> vq[N];
int ans[N];
vector<int> vpos, vtime;

struct SegmentTree1{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, -inf);
   }
   void update(int k, int l, int r, int pos, int val){
      if (r<pos || pos<l) return;
      if (l==r){
         t[k]=val;
         return;
      }
      int mid=(l+r)>>1;
      update(k<<1, l, mid, pos, val);
      update(k<<1|1, mid+1, r, pos, val);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return -inf;
      if (L<=l && r<=R) return t[k];
      int mid=(l+r)>>1;
      return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} stl, str;

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){
      for (auto &i:t[k]){
         // cout << "update l " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
         // cout << "update r " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
         stl.update(1, 1, stl.n, i.first, i.second.first+i.second.second);
         str.update(1, 1, str.n, i.first, i.second.second-i.second.first);
      }
      if (l==r){
         for (auto &i:vq[l]){
            ans[i.second.first]=max(stl.get(1, 1, stl.n, 1, i.first.first)-i.second.second, str.get(1, 1, str.n, i.first.second, str.n)+i.second.second)/2;
         }
      }else{
         int mid=(l+r)>>1;
         dfs(k<<1, l, mid);
         dfs(k<<1|1, mid+1, r);
      }
      for (auto &i:t[k]){
         stl.update(1, 1, stl.n, i.first, 0);
         str.update(1, 1, str.n, i.first, 0);
      }
   }
} st;

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.push_back(-inf*2);
   vector<pair<int, pair<int, int>>> check;
   map<pair<int, int>, vector<pair<int, int>>> mp;
   for (int i=1; i<=n; ++i){
      int x, t, l, r;
      cin >> x >> t >> l >> r; x*=2;
      mp[{x, t}].emplace_back(l, r);
   }
   for (auto &i:mp){
      sort(i.second.begin(), i.second.end());
      vector<pair<int, int>> vv;
      for (auto &j:i.second){
         if (vv.size() && vv.back().second+1>=j.first) vv.back().second=max(vv.back().second, j.second);
         else vv.push_back(j);
      }
      i.second.swap(vv);
   }
   for (auto &i:mp){
      int x=i.first.first, t=i.first.second;
      for (auto &j:i.second){
         int l=j.first, r=j.second;
         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;
      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 (auto &i:events){
      vpos.push_back(i[2]);
   }
   sort(vpos.begin(), vpos.end()); vpos.resize(unique(vpos.begin(), vpos.end())-vpos.begin());
   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(), query[i-1].first)-vpos.begin();
      int pr=upper_bound(vpos.begin(), vpos.end(), query[i-1].first)-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}});
   }
   stl.init((int)vpos.size()-1);
   str.init((int)vpos.size()-1);
   st.init((int)vtime.size()-1);
   for (auto &i:events){
      i[0]=lower_bound(vtime.begin(), vtime.end(), i[0])-vtime.begin();
      i[1]=upper_bound(vtime.begin(), vtime.end(), i[1])-vtime.begin()-1;
      st.update(1, 1, st.n, i[0], i[1], {lower_bound(vpos.begin(), vpos.end(), i[2])-vpos.begin(), {i[2], i[3]}});
   }
   st.dfs(1, 1, st.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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20