Submission #1088028

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) //cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

#define INF INT_MAX/2
int tmax = 1e5;

int main() {
  vi wh(2);
  int q;
  scanf("%d %d %d", &wh[0], &wh[1], &q);
  vv<vi> beam;
  beam.resize(2);
  beam[0].reserve(q);
  beam[1].reserve(q);
  rep (i, q) {
    int t, d, x;
    scanf("%d %d %d", &t, &d, &x);
    t -= 1; x -= 1;
    beam[d].push_back({t, x});
  }

  vector<set<int> > all_wh(2);
  rep (i, 2) {
    sort(all(beam[i]));
    rep (j, wh[i]) {
      all_wh[i].insert(j);
    }
  }
  vi dp;
  vi min_dwh(2, INF);
  rep (i, 2) {
    dp.assign(wh[i], 0);
    auto itr_b = lower_bound(all(beam[i]), (vi){0, 0});
    auto itr_e = itr_b;
    rep (t, tmax) {
      itr_b = itr_e;
      itr_e = lower_bound(all(beam[i]), (vi){t+1, 0});
      if (itr_e - itr_b == wh[i]) {
        printf("-1\n");
        return 0;
      } else if (itr_b == itr_e) {
        continue;
      }
      for (auto itr = itr_e - 1; itr >= itr_b; --itr) {
        debug((*itr)[1]);
        all_wh[i].erase((*itr)[1]);
        dp[(*itr)[1]] = INF;
      }
      if (t == tmax-1) {
        break;
      }
      for (auto itr = itr_b; itr < itr_e; ++itr) {
        int target = (*itr)[1];
        int ret = INF;
        int prev_num, next_num;
        auto adj_itr = all_wh[i].lower_bound(target);
        if (adj_itr != end(all_wh[i])) {
          next_num = *(adj_itr);
          ret = min(ret, dp[next_num] + next_num - target);
        }
        if (adj_itr != begin(all_wh[i])) {
          --adj_itr;
          prev_num = *(adj_itr);
          ret = min(ret, dp[prev_num] + target - prev_num);
        }
        assert(ret < INF);
        dp[target] = ret;
        all_wh[i].insert(target);
      }
      debug(dp);
    }
    rep (j, wh[i]) {
      min_dwh[i] = min(min_dwh[i], dp[j]);
    }
  }
  printf("%d\n", min_dwh[0] + min_dwh[1]);

  return 0;
}

Submission Info

Judge Result