이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define re return
#define fi first
#define mp make_pair
#define se second
#define sz(a) (int)a.size()
#define prev previ
#define tm tmmm
#define div divv
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll CMAX = ll(1e9);
const int szk = 80000;
ll n, m1, m2, t, bad[2000100][2], dp[2000100][2], dp2[2000100][2];
vector<pair<int, int> > pq;
int main() {
iostream::sync_with_stdio(0), cin.tie(0);
pq.push_back(mp(1, -1));
cin >> n >> m1 >> m2 >> t;
pq.push_back(mp(n, -1));
forn (i, m1) {
int x;
cin >> x;
pq.push_back(mp(x, 0));
if (x < n)
pq.push_back(mp(x + 1, -1));
}
forn (i, m2) {
int x;
cin >> x;
pq.push_back(mp(x, 1));
if (x < n)
pq.push_back(mp(x + 1, -1));
}
sort(pq.begin(), pq.end());
int qxx = 0;
vector<int> c;
forn (i, sz(pq)) {
if (i == 0 || pq[i].fi != pq[i - 1].fi) {
c.push_back(pq[i].fi);
qxx++;
}
if (pq[i].se != -1) {
bad[sz(c) - 1][pq[i].se] = 1;
}
}
forn (i, sz(c)) {
dp[i][0] = dp[i][1] = -ll(1e18);
//dp2[i][0] = dp2[i][1] = -ll(1e18);
}
if (bad[0][0] == 0) {
dp[0][0] = dp2[0][0] = 1;
}
if (bad[0][1] == 0) {
dp[0][1] = dp2[0][0] = 1;
}
//cout << dp[0][1] << " " << dp[0][0] << "\n";
for (int i = 1; i < sz(c); i++) {
forn (j, 2) {
if (bad[i][j] == 0) {
dp[i][j] = dp[i - 1][j] + c[i] - c[i - 1];
}
if (bad[i][j]) {
if (dp[i - 1][j] + c[i] - c[i - 1] - t >= 1)
dp[i][j] = dp[i - 1][j] + c[i] - c[i - 1] - t;
}
}
ll k1 = min(dp[i][0],t), k2 = min(dp[i][1], t);
if (bad[i][1] == 0)
dp[i][1] = max(dp[i][1], k1);
if (bad[i][0] == 0)
dp[i][0] = max(dp[i][0], k2);
//cout << dp[i][0] << " " << dp[i][1] << "\n";
}
if (dp[sz(c) - 1][0] < 0 && dp[sz(c) - 1][1] < 0) {
cout << "No\n";
exit(0);
}
cout << "Yes\n";
vector<pair<int, int> > qx;
vector<int> cp;
vector<pair<int, int> > ps;
int x = sz(c) - 1, y = 0;
if (dp[sz(c) - 1][1] >= 0)
y = 1;
while (x > 0) {
qx.push_back(mp(c[x], y));
cp.push_back(bad[x][y]);
if (bad[x][y] == 0 && dp[x][y] == dp[x - 1][y] + c[x] - c[x - 1]) {
x--;
continue;
}
if (bad[x][y] == 1) {
ps.push_back(mp(c[x], y));
x--;
continue;
}
y ^= 1;
continue;
}
vector<int> bl;
qx.push_back(mp(c[x], y));
if (y == 1) {
qx.push_back(mp(0, 1));
qx.push_back(mp(0, 0));
//bl.push_back(1);
cp.push_back(0);
cp.push_back(0);
}
bl.push_back(0);
reverse(qx.begin(), qx.end());
reverse(cp.begin(), cp.end());
vector<int> nms;
forn (i, sz(qx)) {
if (i && qx[i].se != qx[i - 1].se) {
bl.push_back(bl.back() + 1);
nms.push_back(qx[i].fi);
} else
if(i)bl.push_back(bl.back());
}
int qi = sz(cp);
forn (i, sz(cp)) {
if (cp[i]) {
qi = i;
break;
}
}
vector<pair<int, int> > anss;
int hv = 1;
for (int i = 0; i < sz(qx); i++) {
if (qx[i].fi == 0) continue;
int psx = qx[i].fi, psy = qx[i].se;
ll c = 0;
//cout << hv << " " << qx[i].fi << " " << qx[i].se << " " << cp[i] << "\n";
while (qi < sz(cp) && bl[qi] == bl[i]) {
psx += max(t - hv, 0LL);
c += max(t - hv, 0LL);
hv = 0;
anss.push_back(mp(psx, psy + 1));
qi++;
while (qi < sz(cp) && cp[qi] == 0) qi++;
}
if (i + 1 < sz(qx))
hv+= qx[i + 1].fi - qx[i].fi-c;
assert(hv >= 0 || (i + 1 < sz(qx) && qx[i + 1].se == psy));
}
cout << sz(nms) << "\n";
for (int v : nms) cout << v << " ";
cout << "\n";
cout << sz(anss) << "\n";
for (auto v : anss) cout << v.fi << " " << v.se << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |