| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 826514 | caganyanmaz | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG = 10;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e10;
struct SegTree
{
vector<int> data;
vector<int> lazy;
int n;
SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
void push(int l, int r, int index)
{
data[index] += lazy[index];
if (data[index] > INF)
data[index] = INF;
if (r - l > 1)
{
lazy[index<<1] += lazy[index];
lazy[(index<<1)|1] += lazy[index];
}
lazy[index] = 0;
}
void updater(int l, int r, int index, int ss, int ee, int val)
{
push(l, r, index);
if (ss >= r || l >= ee)
return;
if (ee >= r && l >= ss)
{
lazy[index] += val;
push(l, r, index);
return;
}
int m = l+r>>1;
updater(l, m, index<<1, ss, ee, val);
updater(m, r, (index<<1)|1, ss, ee, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
void updatep(int l, int r, int index, int i, int val)
{
push(l, r, index);
if (i >= r || l > i)
return;
if (r - l == 1)
{
data[index] = min(data[index], val);
return;
}
int m = l+r>>1;
updatep(l, m, index<<1, i, val);
updatep(m, r, (index<<1)|1, i, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
int query(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (l >= ee || ss >= r)
return INF;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
int lval = query(l, m, index<<1, ss, ee);
int rval = query(m, r, (index<<1)|1, ss, ee);
return min(lval, rval);
}
void clear() { lazy.clear(); data.clear(); }
void updater(int ss, int ee, int val) { updater(0, n, 1, ss, ee, val); }
void updatep(int i, int val) { updatep(0, n, 1, i, val); }
int query(int ss, int ee) { return query(0, n, 1, ss, ee); }
};
deque<int> r, b;
long long subtask2()
{
int m = r.back();
int sum = 0;
for (int i : r)
sum += m - i;
for (int i : b)
sum += i - m;
if (r.size() > b.size())
sum += (b[0] - m) * (r.size() - b.size());
return sum;
}
long long min_total_length(vector<int32_t> rr, vector<int32_t> bb)
{
for (int i : rr)
r.push_back(i);
for (int i : bb)
b.push_back(i);
if (r.back() < b[0])
return subtask2();
int g = 200;
if (rr.size() > 200 || bb.size() > 200)
g = 9;
int current = 0;
//fill(dp.begin(), dp.begin() + g, INF);
//dp[0] = 0;
if (r[0] > b[0])
swap(r, b);
int mnr = -INF;
SegTree st(1);
SegTree st2(1);
st.updatep(0, 0);
debug(r, b);
while (r.size() || b.size())
{
vector<int> v;
assert(v.size() < g);
while (r.size() && (b.empty() || r[0] < b[0]))
{
v.pb(r[0]);
r.pop_front();
}
st2.clear();
st2 = SegTree(v.size()+1);
int rb = b[0], lb = v[0];
int lsum = 0, rsum = 0;
for (int j = 0; j < v.size(); j++)
rsum += rb - v[j];
for (int i = v.size(); i >= 0; i--) // How many we're putting to right
{
//j for (int j = v.size()-i; j < v.size(); j++)
// rsum += rb - v[j];
debug(i, st.query(0, st.n), lsum, rsum);
st2.updatep(i, st.query(0, st.n) + lsum + rsum);
st.updater(0, v.size()-i+1, lb - mnr);
if (i > 0)
{
lsum += v[v.size()-i] - lb;
rsum -= rb- v[v.size()-i];
}
//for (int j = g-1; j >= 0; j--) // How many is coming from right
//{
// if (j < v.size()-i) // We need to take more
// dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
// else
// dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);#include <bits/stdc++.h>
#define DEBUGGING
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG = 10;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e10;
struct SegTree
{
vector<int> data;
vector<int> lazy;
int n;
SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
void push(int l, int r, int index)
{
data[index] += lazy[index];
if (data[index] > INF)
data[index] = INF;
if (r - l > 1)
{
lazy[index<<1] += lazy[index];
lazy[(index<<1)|1] += lazy[index];
}
lazy[index] = 0;
}
void updater(int l, int r, int index, int ss, int ee, int val)
{
push(l, r, index);
if (ss >= r || l >= ee)
return;
if (ee >= r && l >= ss)
{
lazy[index] += val;
push(l, r, index);
return;
}
int m = l+r>>1;
updater(l, m, index<<1, ss, ee, val);
updater(m, r, (index<<1)|1, ss, ee, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
void updatep(int l, int r, int index, int i, int val)
{
push(l, r, index);
if (i >= r || l > i)
return;
if (r - l == 1)
{
data[index] = min(data[index], val);
return;
}
int m = l+r>>1;
updatep(l, m, index<<1, i, val);
updatep(m, r, (index<<1)|1, i, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
int query(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (l >= ee || ss >= r)
return INF;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
int lval = query(l, m, index<<1, ss, ee);
int rval = query(m, r, (index<<1)|1, ss, ee);
return min(lval, rval);
}
void clear() { lazy.clear(); data.clear(); }
void updater(int ss, int ee, int val) { updater(0, n, 1, ss, ee, val); }
void updatep(int i, int val) { updatep(0, n, 1, i, val); }
int query(int ss, int ee) { return query(0, n, 1, ss, ee); }
};
deque<int> r, b;
long long subtask2()
{
int m = r.back();
int sum = 0;
for (int i : r)
sum += m - i;
for (int i : b)
sum += i - m;
if (r.size() > b.size())
sum += (b[0] - m) * (r.size() - b.size());
return sum;
}
long long min_total_length(vector<int32_t> rr, vector<int32_t> bb)
{
for (int i : rr)
r.push_back(i);
for (int i : bb)
b.push_back(i);
if (r.back() < b[0])
return subtask2();
int g = 200;
if (rr.size() > 200 || bb.size() > 200)
g = 9;
int current = 0;
//fill(dp.begin(), dp.begin() + g, INF);
//dp[0] = 0;
if (r[0] > b[0])
swap(r, b);
int mnr = -INF;
SegTree st(1);
SegTree st2(1);
st.updatep(0, 0);
debug(r, b);
while (r.size() || b.size())
{
vector<int> v;
assert(v.size() < g);
while (r.size() && (b.empty() || r[0] < b[0]))
{
v.pb(r[0]);
r.pop_front();
}
st2.clear();
st2 = SegTree(v.size()+1);
int rb = b[0], lb = v[0];
int lsum = 0, rsum = 0;
for (int j = 0; j < v.size(); j++)
rsum += rb - v[j];
for (int i = v.size(); i >= 0; i--) // How many we're putting to right
{
//j for (int j = v.size()-i; j < v.size(); j++)
// rsum += rb - v[j];
debug(i, st.query(0, st.n), lsum, rsum);
st2.updatep(i, st.query(0, st.n) + lsum + rsum);
st.updater(0, v.size()-i+1, lb - mnr);
if (i > 0)
{
lsum += v[v.size()-i] - lb;
rsum -= rb- v[v.size()-i];
}
//for (int j = g-1; j >= 0; j--) // How many is coming from right
//{
// if (j < v.size()-i) // We need to take more
// dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
// else
// dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);
// We might need to give more as well (but it has 0 contribution so it doesn't matter)
//}
}
mnr = v.back();
swap(r, b);
swap(st, st2);
debug(r, b);
}
return st.query(0, 1);
}
// We might need to give more as well (but it has 0 contribution so it doesn't matter)
//}
}
mnr = v.back();
swap(r, b);
swap(st, st2);
debug(r, b);
}
return st.query(0, 1);#include <bits/stdc++.h>
#define DEBUGGING
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG = 10;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e10;
struct SegTree
{
vector<int> data;
vector<int> lazy;
int n;
SegTree(int _n) : n(_n), data(_n<<2, INF), lazy(_n<<2) {}
void push(int l, int r, int index)
{
data[index] += lazy[index];
if (data[index] > INF)
data[index] = INF;
if (r - l > 1)
{
lazy[index<<1] += lazy[index];
lazy[(index<<1)|1] += lazy[index];
}
lazy[index] = 0;
}
void updater(int l, int r, int index, int ss, int ee, int val)
{
push(l, r, index);
if (ss >= r || l >= ee)
return;
if (ee >= r && l >= ss)
{
lazy[index] += val;
push(l, r, index);
return;
}
int m = l+r>>1;
updater(l, m, index<<1, ss, ee, val);
updater(m, r, (index<<1)|1, ss, ee, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
void updatep(int l, int r, int index, int i, int val)
{
push(l, r, index);
if (i >= r || l > i)
return;
if (r - l == 1)
{
data[index] = min(data[index], val);
return;
}
int m = l+r>>1;
updatep(l, m, index<<1, i, val);
updatep(m, r, (index<<1)|1, i, val);
data[index] = min(data[index<<1], data[(index<<1)|1]);
}
int query(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (l >= ee || ss >= r)
return INF;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
int lval = query(l, m, index<<1, ss, ee);
int rval = query(m, r, (index<<1)|1, ss, ee);
return min(lval, rval);
}
void clear() { lazy.clear(); data.clear(); }
void updater(int ss, int ee, int val) { updater(0, n, 1, ss, ee, val); }
void updatep(int i, int val) { updatep(0, n, 1, i, val); }
int query(int ss, int ee) { return query(0, n, 1, ss, ee); }
};
deque<int> r, b;
long long subtask2()
{
int m = r.back();
int sum = 0;
for (int i : r)
sum += m - i;
for (int i : b)
sum += i - m;
if (r.size() > b.size())
sum += (b[0] - m) * (r.size() - b.size());
return sum;
}
long long min_total_length(vector<int32_t> rr, vector<int32_t> bb)
{
for (int i : rr)
r.push_back(i);
for (int i : bb)
b.push_back(i);
if (r.back() < b[0])
return subtask2();
int g = 200;
if (rr.size() > 200 || bb.size() > 200)
g = 9;
int current = 0;
//fill(dp.begin(), dp.begin() + g, INF);
//dp[0] = 0;
if (r[0] > b[0])
swap(r, b);
int mnr = -INF;
SegTree st(1);
SegTree st2(1);
st.updatep(0, 0);
debug(r, b);
while (r.size() || b.size())
{
vector<int> v;
assert(v.size() < g);
while (r.size() && (b.empty() || r[0] < b[0]))
{
v.pb(r[0]);
r.pop_front();
}
st2.clear();
st2 = SegTree(v.size()+1);
int rb = b[0], lb = v[0];
int lsum = 0, rsum = 0;
for (int j = 0; j < v.size(); j++)
rsum += rb - v[j];
for (int i = v.size(); i >= 0; i--) // How many we're putting to right
{
//j for (int j = v.size()-i; j < v.size(); j++)
// rsum += rb - v[j];
debug(i, st.query(0, st.n), lsum, rsum);
st2.updatep(i, st.query(0, st.n) + lsum + rsum);
st.updater(0, v.size()-i+1, lb - mnr);
if (i > 0)
{
lsum += v[v.size()-i] - lb;
rsum -= rb- v[v.size()-i];
}
//for (int j = g-1; j >= 0; j--) // How many is coming from right
//{
// if (j < v.size()-i) // We need to take more
// dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
// else
// dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);
// We might need to give more as well (but it has 0 contribution so it doesn't matter)
//}
}
mnr = v.back();
swap(r, b);
swap(st, st2);
debug(r, b);
}
return st.query(0, 1);
}
}