Submission #1043319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043319		vjudge1	New Home (APIO18_new_home)	C++17	12 / 100	5071 ms	114056 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int S = 1, E = 1e8 + 1;
const int Q =  3 * 1e5 + 10, N = Q, T = Q;
int ans[Q], Closed = 0;
map<int, vector<pair<int,int> > > add, rem, qry;
vector<int> events;
multiset<int> st[T];
int n, k, q;

void query(int l, int i)
{
  if(Closed > 0)
    {
      ans[i] = -1;
      return;
    }
  
  ans[i] = 0;
  for(int j = 1; j <= k; j++)
    {
      auto it = st[j].upper_bound(l);
      int d = E;
      if(it != st[j].end())
	d = min(d, *it - l);
      if(it != st[j].begin())
	{
	  it--;
	  d = min(d, l - *it);
	}
      ans[i] = max(ans[i], d);
    }
}

void Add(int x, int t) {
  if(st[t].empty()) Closed--;
  st[t].insert(x);
}

void remove(int x, int t)
{
  st[t].erase(st[t].find(x));
  if(st[t].empty())
    Closed++;
}


int main()
{
  cin >> n >> k >> q;
  Closed = k;
  
  for(int i = 0; i < n; i ++)
    {
      int x, t, a, b;
      cin >> x >> t >> a >> b;
      
      events.push_back(a);
      events.push_back(b);

      add[a].push_back({x, t});
      rem[b].push_back({x, t});
    }

  for(int i = 0; i < q; i ++)
    {
      int l, y;
      cin >> l >> y;
      events.push_back(y);
      qry[y].push_back({l, i});
    }

  sort(events.begin(), events.end());
  events.resize(unique(events.begin(), events.end()) - events.begin());

  for(int e : events)
    {
      // cerr << endl;
      // cerr << "Event time : " << e << endl;
      if(add.find(e) != add.end())
	{
	  vector<pair<int,int> > &vec = add[e];
	  for(auto [x, t] : vec)
	    Add(x, t);
	}

      if(qry.find(e) != qry.end())
	{
	  vector<pair<int,int> > &vec = qry[e];
	  for(auto [l, i] : vec)
	    query(l, i);
	}

      if(rem.find(e) != rem.end())
	{
	  vector<pair<int,int> > &vec = rem[e];
	  for(auto [x, t] : vec)
	    remove(x, t);
	}
    }
  

  for(int i = 0; i < q; i ++)
    cout << ans[i] << '\n';
  return 0;
}

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