Submission #658964

#	Time	Username	Problem	Language	Result	Execution time	Memory
658964		600Mihnea	New Home (APIO18_new_home)	C++17	0 / 100	5103 ms	39564 KiB

new_home

bool home = 0;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 3e5 + 7;
const int INF = (int) 1e9 + 7;
int n;
int k;
int q;

struct T {
  int x;
  int t;
  int a;
  int b;
};

T v[N];
vector<int> gs[N];

struct Q {
  int x;
  int t;
};

bool operator < (Q a, Q b) {
  return a.t < b.t;
}

struct U {
  int pos;
  int x;
};

int main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("input.txt", "r", stdin);
  }

  cin >> n >> k >> q;

  for (int i = 1; i <= n; i++) {
    cin >> v[i].x >> v[i].t >> v[i].a >> v[i].b;
    v[i].x *= 2;
    gs[v[i].t].push_back(i);
  }

  vector<pair<int, int>> qs(q);
  vector<int> inv(q);

  for (int iq = 0; iq < q; iq++) {
    int t;
    cin >> qs[iq].first >> t;
    qs[iq].first *= 2;
    qs[iq].second = iq;
  }

  sort(qs.begin(), qs.end());

  for (int i = 0; i < q; i++) {
    inv[qs[i].second] = i;
  }

  vector<int> sol(q, 0);

  vector<U> lft, rgh;

  for (int tp = 1; tp <= k; tp++) {
    if (gs[tp].empty()) {
      continue;
    }
    sort(gs[tp].begin(), gs[tp].end(), [&] (int i, int j) {
      return v[i].x < v[j].x;
    });
    for (int i = 0; i + 1 < (int) gs[tp].size(); i++) {
      T cur = v[gs[tp][i]];
      T nxt = v[gs[tp][i + 1]];
      lft.push_back({(cur.x + nxt.x) / 2, cur.x});
      rgh.push_back({(cur.x + nxt.x) / 2, nxt.x});
    }
    rgh.push_back({-(int) 2e8, v[gs[tp][0]].x});
    lft.push_back({+(int) 2e8, v[gs[tp].back()].x});
  }

  for (int i = 0; i < q; i++) {
    int x = qs[i].first;
    for (auto &it : lft) {
      if (x <= it.pos) {
        sol[i] = max(sol[i], x - it.x);
      }
    }
    for (auto &it : rgh) {
      if (it.pos <= x) {
        sol[i] = max(sol[i], it.x - x);
      }
    }
  }

  for (int i = 0; i < q; i++) {
    cout << sol[inv[i]] / 2 << "\n";
  }
  return 0;

  for (int iq = 1; iq <= q; iq++) {
    int x, t;
    cin >> x >> t;
    qs.push_back({x, iq});
    int sol = -INF;
    for (int tp = 1; tp <= k; tp++) {
      int nr = INF;
      for (auto &i : gs[tp]) {
        if (v[i].a <= t && t <= v[i].b) {
          nr = min(nr, abs(x - v[i].x));
        }
      }
      sol = max(sol, nr);
    }
    if (sol == INF) {
      sol = -1;
    }
    cout << sol << "\n";
  }

  return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:42:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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