Submission #658966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658966	2022-11-15T16:17:02 Z	600Mihnea	New Home (APIO18_new_home)	C++17	10 / 100	354 ms	47672 KB

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});
  }

  sort(rgh.begin(), rgh.end(), [&] (U a, U b) {
    return a.pos < b.pos;
  });

  {
    int mx = -((int) 1e9 + 7);
    int pt = 0;
    for (int i = 0; i < q; i++) {
      int x = qs[i].first;
      while (pt < (int) rgh.size() && rgh[pt].pos <= x) {
        mx = max(mx, rgh[pt++].x);
      }
      sol[i] = max(sol[i], mx - x);
    }
  }
  sort(lft.begin(), lft.end(), [&] (U a, U b) {
    return a.pos > b.pos;
  });

  {
    int mn = ((int) 1e9 + 7);
    int pt = 0;
    for (int i = q - 1; i >= 0; i--) {
      int x = qs[i].first;
      while (pt < (int) lft.size() && x <= lft[pt].pos) {
        mn = min(mn, lft[pt++].x);
      }
      sol[i] = max(sol[i], x - mn);
    }
  }


  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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7372 KB	Output is correct
2	Incorrect	4 ms	7252 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7372 KB	Output is correct
2	Incorrect	4 ms	7252 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	27224 KB	Output is correct
2	Correct	264 ms	37024 KB	Output is correct
3	Correct	338 ms	47596 KB	Output is correct
4	Correct	354 ms	41400 KB	Output is correct
5	Correct	286 ms	39616 KB	Output is correct
6	Correct	280 ms	36844 KB	Output is correct
7	Correct	253 ms	47672 KB	Output is correct
8	Correct	298 ms	41100 KB	Output is correct
9	Correct	286 ms	40004 KB	Output is correct
10	Correct	270 ms	38448 KB	Output is correct
11	Correct	270 ms	37128 KB	Output is correct
12	Correct	260 ms	38576 KB	Output is correct