Submission #59891

#	Time	Username	Problem	Language	Result	Execution time	Memory
59891		dukati8	New Home (APIO18_new_home)	C++14	5 / 100	5100 ms	93904 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
int main() {
  int n,q,k;
  cin >> n >> k >> q;
  vector<vector<int> > stores(n);
  rep (i,0,n) {
    int x,t,a,b;
    cin >> x >> t >> a >> b;
    stores[i]={a,b,x,t};
  }
  vector< vector<int> > queries(q);
  rep (i,0,q) {
    int l,y;
    cin >> l >> y;
    queries[i]={y,l,i};
  }
  sort(queries.begin(),queries.end());
  vector<int> answers(q);
  sort(all(stores));
  vector< set<vector<int> > > types(k);
  int numtaken=0;
  set<vector<int> > takenstores;
  rep (i,0,q) {
    int l,y,index;
    l=queries[i][1];
    y=queries[i][0];
    index=queries[i][2];
    while(numtaken<n && y>=stores[numtaken][0]) {
      int x,t,a,b;
      x=stores[numtaken][2];
      t=stores[numtaken][3];
      a=stores[numtaken][0];
      b=stores[numtaken][1];
      takenstores.insert({b,a,x,t});
      types[t-1].insert({x,a,b,t});
      numtaken++;
    }
    while (!takenstores.empty() && (*takenstores.begin())[0]<y) {
      auto it = takenstores.begin();
      int x,t,a,b;
      x=(*it)[2];
      t=(*it)[3];
      a=(*it)[1];
      b=(*it)[0];
      takenstores.erase(it);
      types[t-1].erase({x,a,b,t});
    }
    int best=0;
    rep (ind,0,k) {
      int temp=1e9;
      if (types[ind].empty()) {best=-1; break;}
      auto it = types[ind].upper_bound({l,0,0,0});
      if (it!=types[ind].end()) {
        temp=(*it)[0]-l;
      }
      if (it!=types[ind].begin()) {
        it ==--it;
        temp=min(temp,l-(*it)[0]);
      }
      best=max(best,temp);
    }
    answers[index]=best;
  }
  rep(i,0,q) {
    cout << answers[i] << endl;
  }
}

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