Submission #216895

#	Time	Username	Problem	Language	Result	Execution time	Memory
216895		eriksuenderhauf	Treatment Project (JOI20_treatment)	C++11	100 / 100	385 ms	32344 KiB

treatment

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
#define st first
#define nd second
#define ar(n) array<ll,(n)>
using namespace std;
typedef long long ll;
const ll inf = 1e16 + 7;
const int M = 200005;
ar(4) a[M], b[M];
priority_queue<ar(2), vector<ar(2)>, greater<ar(2)>> pq;
ll n, m, t=1, dp[M];
vector<pii> seg[M];
int vis[M];

void setE(int idx, int i, int j) {
  for (++i; i < M; i += i & -i)
    seg[i].pb({j, idx});
}

void updE(int i, int j, ll v) {
  for (++i; i > 0; i -= i & -i) {
    while (!seg[i].empty()) {
      int k = seg[i].back().nd;
      if (vis[k]) {
        seg[i].pop_back();
        continue;
      }
      if (seg[i].back().st < j)
        break;
      pq.push({v + a[k][3], k});
      vis[k] = 1;
      seg[i].pop_back();
    }
  }
}

int main() {
  scanf("%lld %lld", &n, &m);
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < 4; j++)
      scanf("%lld", &a[i][j]);
    t = max(t, a[i][0]);
  }
  vector<ll> cH, cV;
  for (int i = 1; i <= m; i++) {
    dp[i] = inf;
    b[i][0] = a[i][0]+a[i][1]-1;
    b[i][1] = a[i][0]-a[i][2]+n;

    b[i][2] = a[i][0]+a[i][2]-1;
    b[i][3] = a[i][0]-a[i][1]+n;
    if (a[i][1] == 1) {
      b[i][3] = n+t-1;
      dp[i] = a[i][3];
      pq.push({dp[i], i});
    }
    if (a[i][2] == n)
      b[i][2] = n+t-1;
    cH.pb(b[i][0]);
    cH.pb(b[i][2]+1);
    cV.pb(b[i][1]-1);
    cV.pb(b[i][3]);
  }
  sort(cH.begin(), cH.end());
  sort(cV.begin(), cV.end());
  cH.erase(unique(cH.begin(), cH.end()), cH.end());
  cV.erase(unique(cV.begin(), cV.end()), cV.end());
  for (int i = 1; i <= m; i++) {
    b[i][0] = lower_bound(cH.begin(), cH.end(), b[i][0]) - cH.begin() + 1;
    b[i][2] = lower_bound(cH.begin(), cH.end(), b[i][2]+1) - cH.begin() + 1;
    b[i][1] = lower_bound(cV.begin(), cV.end(), b[i][1]-1) - cV.begin() + 1;
    b[i][3] = lower_bound(cV.begin(), cV.end(), b[i][3]) - cV.begin() + 1;
    if (dp[i] == inf)
      setE(i, b[i][0], b[i][3]);
  }
  for (int i = 0; i < M; i++)
    sort(seg[i].begin(), seg[i].end());
  ll ans = inf;
  while (!pq.empty()) {
    auto it = pq.top(); pq.pop();
    dp[it[1]] = it[0];
    if (a[it[1]][2] == n) {
      ans = min(ans, it[0]);
      continue;
    }
    updE(b[it[1]][2], b[it[1]][1], it[0]);
  }
  ans = ans == inf ? -1 : ans;
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
treatment.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &a[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~~

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