// #define _GLIBCXX_DEBUG // for STL debug (optional) #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} typedef pair pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; int N, L; void set_push(set< pair > &S, int pos, int idx) { S.emplace(pos + L, idx); S.emplace(pos + 2*L, idx); S.emplace(pos + 3*L, idx); } void set_erase(set< pair > &S, int pos, int idx) { S.erase(make_pair(pos + L, idx)); S.erase(make_pair(pos + 2*L, idx)); S.erase(make_pair(pos + 3*L, idx)); } signed main() { scanf("%lld%lld", &N, &L); vector x(N), y(N); set< pair > sx, sy; for(int i=0; i 寿司 -> お茶 なので // 今いるところから最も近い寿司をまず求め、 // それ以降で最も近いお茶を探すと良い // 実際に採用する寿司は、決めたお茶の左にある中で最も近いものにする // お茶に関しても同様 int ini_x_pos, ini_x_idx; tie(ini_x_pos, ini_x_idx) = *sx.lower_bound(make_pair(pos, 0)); int tmp_y_pos, tmp_y_idx; tie(tmp_y_pos, tmp_y_idx) = *sy.lower_bound(make_pair(ini_x_pos, 0)); int tmp_x_pos, tmp_x_idx; tie(tmp_x_pos, tmp_x_idx) = *sx.lower_bound(make_pair(tmp_y_pos, 0)); int nxt_y_pos, nxt_y_idx; tie(nxt_y_pos, nxt_y_idx) = *(--sy.lower_bound(make_pair(tmp_x_pos, 0))); int nxt_x_pos, nxt_x_idx; tie(nxt_x_pos, nxt_x_idx) = *(--sx.lower_bound(make_pair(tmp_y_pos, 0))); ans += nxt_y_pos - pos; pos = nxt_y_pos; while(pos < L) pos += L; while(pos > 2*L) pos -= L; // fprintf(stderr, "take: x = %lld, y = %lld\n", nxt_x_idx, nxt_y_idx); set_erase(sx, x[nxt_x_idx], nxt_x_idx); set_erase(sy, y[nxt_y_idx], nxt_y_idx); } cout << ans << endl; return 0; }