Submission #1043314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043314		vjudge1	New Home (APIO18_new_home)	C++17	0 / 100	1920 ms	1048576 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
int S = 1, E = 1e8 + 1;

struct node
{
  ll first, delta;
  node *lc, *rc;
  node()
  {
    lc = rc = NULL;
    first = delta = 0;
  }
  void update(int l, int r, int f, int d, int s = S, int e = E)
  {
    if(r <= s || e <= l) return;
    if(l <= s && e <= r)
      {
	first += f;
	delta += d;
	return;
      }
    int mid = (s + e) / 2;
    if(l < mid)
      { // this means I have some work on left child
	if(lc == NULL) lc = new node();
	lc -> update(l, r, f, d, s, mid);
      }
    
    if(mid < r)
      {
	if(rc == NULL) rc = new node();
	rc -> update(l, r, f, d, mid, e);
      }
  }
  
  ll get(int p, int s = S, int e = E)
  {
    if(p < s || e <= p) return 0;
    ll ans = first + (p - s) * delta;
    int mid = (s + e) / 2;
    if(lc != NULL) ans += lc -> get(p, s, mid);
    if(rc != NULL) ans += rc -> get(p, mid, e);
    return ans;
  }
};

const int Q =  3 * 1e5 + 10, N = Q, T = Q;
node *seg[N];
ll 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)
{
  // cerr << "query : " << l << endl;
  if(Closed > 0)
    {
      ans[i] = -1;
      return;
    }
  ans[i] = 0;
  for(int j = 1; j <= k; j++)
    ans[i] = max(ans[i], seg[j]->get(l));
  
}

void update(int l, int r, int f, int d, int t) {
  seg[t]->update(l, r, f, d);
  // cerr << "update" << l << ' ' << r << ' ' << f << ' ' << d << endl;
}

void Add(int x, int t)
{
  // cerr << "add " << x << ' ' << t << endl;
  if(st[t].empty())
    {
      Closed--;
      st[t].insert(x);
      update(x, E, 0, 1, t);
      if(S < x)
	update(S, x, x - S, -1, t);
      return;
    }

  auto it = st[t].upper_bound(x);
  if(it == st[t].end())
    {
      it--;
      update(x, E, 0, 1, t);
    }
  else
    {
      int mid = (*it + x + 1) / 2;
      update(x, mid, 0, 1, t);
      update(mid, *it, *it - mid, -1, t);

      if(it != st[t].begin())
	{
	  int e = *it;
	  it--;
	  mid = (*it + e) / 2;
	  update(mid, e, mid - e, 1, t);
	}
      else
	update(S, *it, S - *it, 1, t);
    }

  it = st[t].upper_bound(x);
  if(it == st[t].begin())
    {
      update(S, x, x - S, -1, t);
    }
  else
    {
      it--;
      int mid = (x + *it + 1) / 2;
      update(*it, mid, 0, 1, t);
      update(mid, x, x - mid, -1, t);
      int s = *it;
      it++;
      if(it == st[t].end())
	update(s, E, 0, -1, t);
      else
	{
	  mid = (s + *it + 1) / 2;
	  update(s, mid, 0, -1, t);
	}
    }

  st[t].insert(x);  
}

void remove(int x, int t)
{
  // cerr << "rem " << x << ' ' << t << endl;
  st[t].erase(st[t].find(x));
  if(st[t].empty())
    {
      Closed++;
      update(x, E, 0, -1, t);
      if(S < x)
	update(S, x, S - x, +1, t);
      return;
    }


  auto it = st[t].upper_bound(x);
  if(it == st[t].end())
    {
      it--;
      update(x, E, 0, -1, t);
    }
  else
    {
      int mid = (*it + x + 1) / 2;
      update(x, mid, 0, -1, t);
      update(mid, *it, mid - *it, +1, t);

      if(it != st[t].begin())
	{
	  int e = *it;
	  it--;
	  mid = (*it + e) / 2;
	  update(mid, e, e - mid, -1, t);
	}
      else
	update(S, *it, *it - S, -1, t);
    }

  it = st[t].upper_bound(x);
  if(it == st[t].begin())
    {
      update(S, x, S - x, +1, t);
    }
  else
    {
      it--;
      int mid = (x + *it + 1) / 2;
      update(*it, mid, 0, -1, t);
      update(mid, x, mid - x, +1, t);
      int s = *it;
      it++;
      if(it == st[t].end())
	update(s, E, 0, 1, t);
      else
	{
	  mid = (s + *it + 1) / 2;
	  update(s, mid, 0, 1, t);
	}
    }
}



int main()
{
  cin >> n >> k >> q;
  Closed = k;

  for(int i = 1; i <= k; i ++)
    seg[i] = new node();
  
  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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20