Submission #1067385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067385		juicy	버스 (JOI14_bus)	C++17	100 / 100	150 ms	17288 KiB

bus

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, M = 3e5 + 5, inf = 1e9;

int n, m, q;
int s[M], t[M], x[M], y[M], dp[M], best[N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  vector<array<int, 3>> events;
  for (int i = 1; i <= m; ++i) {
    cin >> s[i] >> t[i] >> x[i] >> y[i];
    events.push_back({x[i], 1, i});
    events.push_back({y[i], 0, i});
  }
  sort(events.begin(), events.end());
  fill(best + 1, best + n + 1, -inf);
  vector<array<int, 2>> cands;
  for (auto [_, type, i] : events) {
    if (!type) {
      best[t[i]] = max(best[t[i]], dp[i]);
      if (t[i] == n && dp[i] != -inf) {
        cands.push_back({y[i], dp[i]});
      } 
    } else {
      if (s[i] == 1) {
        dp[i] = x[i];
      } else {
        dp[i] = best[s[i]];
      }
    }
  }
  for (int i = 1; i < cands.size(); ++i) {
    cands[i][1] = max(cands[i][1], cands[i - 1][1]);
  }
  auto qry = [&](int x) {
    int it = lower_bound(cands.begin(), cands.end(), array<int, 2>{x, inf}) - cands.begin();
    return it == 0 ? -1 : cands[it - 1][1];
  };
  cin >> q;
  while (q--) {
    int x; cin >> x;
    cout << qry(x) << "\n";
  }
  return 0;
}

Compilation message (stderr)

bus.cpp: In function 'int main()':
bus.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 1; i < cands.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50