Submission #1049185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049185		abczz	Treatment Project (JOI20_treatment)	C++17	100 / 100	217 ms	102952 KiB

treatment

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long

using namespace std;

ll n, m, f, cur, dp[100000], X[100000];
bool ok[100000];
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
array <ll, 4> A[100000];

struct SegTree{
  vector <array<ll, 2> > V[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      V[id].push_back({X[l], l});
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < V[id*2].size() && j < V[id*2+1].size()) {
      if (V[id*2][i][0] >= V[id*2+1][j][0]) V[id].push_back(V[id*2][i++]);
      else V[id].push_back(V[id*2+1][j++]);
    }
    while (i < V[id*2].size()) V[id].push_back(V[id*2][i++]);
    while (j < V[id*2+1].size()) V[id].push_back(V[id*2+1][j++]);
  }
  void query(ll id, ll l, ll r, ll ql, ll qr, ll x) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      while (!V[id].empty() && V[id].back()[0] <= x) {
        if (!ok[V[id].back()[1]]) {
          //cout << A[V[id].back()[1]][1] << " " << A[V[id].back()[1]][2] << "*" << endl;
          dp[V[id].back()[1]] = cur + A[V[id].back()[1]][3];
          ok[V[id].back()[1]] = 1;
          pq.push({dp[V[id].back()[1]], V[id].back()[1]});
        }
        V[id].pop_back();
      }
      return;
    }
    ll mid = (l+r)/2;
    query(id*2, l, mid, ql, qr, x);
    query(id*2+1, mid+1, r, ql, qr, x);
  }
}STA, STB;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  f = 1e18;
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    for (int j=0; j<4; ++j) {
      cin >> A[i][j];
    }
  }
  sort(A, A+m);
  for (int i=0; i<m; ++i) X[i] = A[i][1]+A[i][0];
  STA.build(1, 0, m-1);
  for (int i=0; i<m; ++i) X[i] = A[i][1]-A[i][0];
  STB.build(1, 0, m-1);
  for (int i=0; i<m; ++i) {
    if (A[i][1] == 1) {
      ok[i] = 1;
      dp[i] = A[i][3];
      pq.push({dp[i], i});
    }
  }
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    auto x = A[u];
    pq.pop();
    if (x[2] == n) f = min(f, dp[u]);
    cur = dp[u];
    STA.query(1, 0, m-1, u, m-1, x[2]+x[0]+1);
    STB.query(1, 0, m-1, 0, u, x[2]-x[0]+1);
  }
  if (f >= 1e18) cout << "-1\n";
  else cout << f << '\n';
}

Compilation message (stderr)

treatment.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
treatment.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (i < V[id*2].size() && j < V[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~
treatment.cpp:26:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while (i < V[id*2].size() && j < V[id*2+1].size()) {
      |                                  ~~^~~~~~~~~~~~~~~~~~
treatment.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (i < V[id*2].size()) V[id].push_back(V[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~
treatment.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while (j < V[id*2+1].size()) V[id].push_back(V[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61