結果
| 問題 | No.1767 BLUE to RED |
| ユーザー |
 akua
|
| 提出日時 | 2021-11-26 23:59:01 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,180 bytes |
| コンパイル時間 | 1,280 ms |
| コンパイル使用メモリ | 141,572 KB |
| 実行使用メモリ | 24,072 KB |
| 最終ジャッジ日時 | 2024-06-29 18:42:02 |
| 合計ジャッジ時間 | 5,180 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 17 ms
18,944 KB |
| testcase_01 | AC | 17 ms
18,816 KB |
| testcase_02 | AC | 18 ms
18,816 KB |
| testcase_03 | AC | 17 ms
18,816 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | AC | 18 ms
18,688 KB |
| testcase_07 | AC | 17 ms
18,816 KB |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | AC | 188 ms
21,888 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
ソースコード
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
const ll inf=1e18;
//const long long mod=1000000007;
//const long long mod2=998244353;
using ll=long long;
using P= pair<ll, ll>;
const int MAX = 500000;
// 今回採用する大きい素数
const int MOD = 1000000007;
// メモを保管する場所
ll fact[MAX], inv_fact[MAX], inv[MAX];
// メモを計算する
void init() {
// 初期値設定と1はじまりインデックスに直す
fact[0] = 1;
fact[1] = 1;
inv[0] = 1;
inv[1] = 1;
inv_fact[0] = 1;
inv_fact[1] = 1;
// メモの計算
repi(i, 2, MAX){
// 階乗
fact[i] = fact[i - 1] * i % MOD;
// 逆元
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
// 逆元の階乗
inv_fact[i] = inv_fact[i - 1] * inv[i] % MOD;
}
}
// 二項係数の実体
ll nCk(int n, int k) {
ll x = fact[n]; // n!の計算
ll y = inv_fact[n-k]; // (n-k)!の計算
ll z = inv_fact[k]; // k!の計算
if (n < k) return 0; // 例外処理
if (n < 0 || k < 0) return 0; // 例外処理
return x * ((y * z) % MOD) % MOD; //二項係数の計算
}
ll pow_pow(ll x,ll n,ll mod){
if(n==0) return 1;
x%=mod;
ll res=pow_pow(x*x%mod,n/2,mod);
if(n&1)res=res*x%mod;
return res;
}
int extgcd(int a,int b,int &x,int &y){
int d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}else{
x=1;y=0;
}
return d;
}
int mod_inverse(int a,int m){
int x,y;
extgcd(a,m,x,y);
return (m+x%m)%m;
}
struct UnionFind {
vector<int> par, siz;
UnionFind(int n) : par(n, -1) , siz(n, 1) { }
// 根を求める
int root(int x) {
if (par[x] == -1) return x;
else return par[x] = root(par[x]);
}
// x と y が同じグループに属するかどうか (根が一致するかどうか)
bool issame(int x, int y) {
return root(x) == root(y);
}
// x を含むグループと y を含むグループとを併合する
bool unite(int x, int y) {
x = root(x), y = root(y);
if (x == y) return false;
if (siz[x] < siz[y]) swap(x, y);
par[y] = x;
siz[x] += siz[y];
return true;
}
// x を含むグループのサイズ
int size(int x) {
return siz[root(x)];
}
};
struct Edge
{
int to;
ll w;
Edge(int to, ll w) : to(to), w(w) { }
};
//min(x,y)が0以下の場合はmax(x,y)が返される
//ユークリッドの互除法を元に実装
ll gcd(ll x,ll y){
if(x<y) swap(x,y);
//xの方が常に大きい
ll r;
while(y>0){
r=x%y;
x=y;
y=r;
}
return x;
}
//オーバフローしないようにかける順番を気を付ける
ll lcm(ll x,ll y){
return ll(x/gcd(x,y))*y;
}
template<class T> bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
else return false;
}
//using Graph1=vector<vector<Edge> >;
//using Graph=vector<vector<int> >;
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1e9+7;
struct mint {
ll x; // typedef long long ll;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
mint operator+(const mint a) const { return mint(*this) += a;}
mint operator-(const mint a) const { return mint(*this) -= a;}
mint operator*(const mint a) const { return mint(*this) *= a;}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const { return pow(mod-2);}
mint& operator/=(const mint a) { return *this *= a.inv();}
mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
//assert(n < mod);
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
mint p(int n, int k) {
return fact[n]*ifact[n-k];
}
} c(1000005);
const ll INF=1e18;
using Graph=vector<vector<int> >;
class segment_tree {
private:
int sz;
std::vector<int> seg;
std::vector<int> lazy;
void push(int k) {
if (k < sz) {
lazy[k * 2] = max(lazy[k * 2], lazy[k]);
lazy[k * 2 + 1] = max(lazy[k * 2 + 1], lazy[k]);
}
seg[k] = max(seg[k], lazy[k]);
lazy[k] = 0;
}
void update(int a, int b, int x, int k, int l, int r) {
push(k);
if (r <= a || b <= l) return;
if (a <= l && r <= b) {
lazy[k] = x;
push(k);
return;
}
update(a, b, x, k * 2, l, (l + r) >> 1);
update(a, b, x, k * 2 + 1, (l + r) >> 1, r);
seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
}
int range_max(int a, int b, int k, int l, int r) {
push(k);
if (r <= a || b <= l) return 0;
if (a <= l && r <= b) return seg[k];
int lc = range_max(a, b, k * 2, l, (l + r) >> 1);
int rc = range_max(a, b, k * 2 + 1, (l + r) >> 1, r);
return max(lc, rc);
}
public:
segment_tree() : sz(0), seg(), lazy() {};
segment_tree(int N) {
sz = 1;
while (sz < N) {
sz *= 2;
}
seg = std::vector<int>(sz * 2, 0);
lazy = std::vector<int>(sz * 2, 0);
}
void update(int l, int r, int x) {
update(l, r, x, 1, 0, sz);
}
int range_max(int l, int r) {
return range_max(l, r, 1, 0, sz);
}
//cin.tie(0);
//ios_base::sync_with_stdio(false); これらをmain関数の先頭に
};
const int seg_size=200005;
ll seg[seg_size*2];
ll seg_max(int l,int r){
l+=seg_size;
r+=seg_size;
ll maxv=0;
while(l<r){
if(l%2==1){
maxv=max(maxv,seg[l]);
l++;
}
l/=2;
if(r%2==1){
maxv=max(maxv,seg[r-1]);
r--;
}
r/=2;
}
return maxv;
}
void seg_up(int ind,ll v){
ind+=seg_size;
seg[ind]=max(seg[ind],v);
while(true){
if(ind==0)break;
ind/=2;
seg[ind]=max(seg[ind*2],seg[ind*2+1]);
}
}
int main(){
int n,m; cin >> n >> m;
vector<ll> a(n),b(m);
rep(i,n)cin >> a[i];
rep(i,m)cin >> b[i];
ll ans=0;
if(n==1){
if(b[m-1]>a[0] && b[0]<a[0])ans=b[m-1]-b[0];
else if(a[0]<b[0])ans=b[m-1]-a[0];
else ans=a[0]-b[0];
cout << ans << endl;
return 0;
}
rep(i,n-1){
int index1=lower_bound(b.begin(),b.end(),a[i])-b.begin();
int index2=lower_bound(b.begin(),b.end(),a[i+1])-b.begin();
if(index2-1>=m)continue;
if(index1==index2)continue;
vector<ll> now;
now.push_back(a[i]);
for(int k=index1; k<=index2-1; k++){
now.push_back(b[k]);
}
now.push_back(a[i+1]);
int size=now.size();
ll minv=inf;
rep(j,size-1)minv=min(minv,now[j]-a[i]+a[i+1]-now[j+1]);
ans+=minv;
}
cout << ans << endl;
return 0;
}