| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56937 |
2018-07-13T08:58:14 Z |
윤교준(#1636) |
None (JOI15_walls) |
C++11 |
|
536 ms |
16096 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const bool debug = 0;
const int MAXN = 200005;
const int MAXQ = 200005;
multiset<pii> EV;
set<int> CH;
ll CHL, CMX;
int A[MAXN], B[MAXN], L[MAXN], O[MAXN];
int C[MAXQ];
ll Ans[MAXN];
int N, Q;
pii f(int a, int b) { return pii(abs(C[a] - C[b]), min(a, b)); }
void process() {
for(int i = 1; i < Q; i++)
EV.insert(pii(abs(C[i+1] - C[i]), i));
for(int i = 1; i <= Q; i++) CH.insert(i);
for(int i = 1; i < Q; i++) CHL += abs(C[i+1] - C[i]);
CMX = *max_element(C+1, C+Q+1);
iota(O, O+N+1, 0);
sort(O+1, O+N+1, [&](int a, int b) {
return L[a] < L[b];
});
for(int oi = 1, i; oi <= N; oi++) {
i = O[oi];
for(int idx, l; !EV.empty();) {
tie(l, idx) = *EV.begin();
if(L[i] < l) break;
int tidx = -1;
{
auto it = CH.lower_bound(idx);
it++;
tidx = *it;
}
int pidx = -1;
{
auto it = CH.lower_bound(tidx);
it++;
if(CH.end() != it)
pidx = *it;
}
int didx = -1;
{
auto it = CH.lower_bound(idx);
if(CH.begin() != it) {
it--;
didx = *it;
}
}
if(C[idx] < C[tidx]) {
if(0 < pidx) EV.erase(f(tidx, pidx));
EV.erase(f(tidx, idx));
CH.erase(tidx);
if(0 < pidx) CHL -= abs(C[pidx] - C[tidx]);
CHL -= abs(C[tidx] - C[idx]);
if(0 < pidx && 0 < didx) {
EV.erase(f(idx, didx));
CH.erase(idx);
CHL -= abs(C[idx] - C[didx]);
EV.insert(f(pidx, didx));
CHL += abs(C[pidx] - C[didx]);
} else if(0 < pidx) {
EV.insert(f(pidx, idx));
CHL += abs(C[pidx] - C[idx]);
}
} else {
EV.erase(f(tidx, idx));
if(0 < didx) EV.erase(f(idx, didx));
CH.erase(idx);
CHL -= abs(C[tidx] - C[idx]);
if(0 < didx) CHL -= abs(C[idx] - C[didx]);
if(0 < pidx && 0 < didx) {
EV.erase(f(pidx, tidx));
CH.erase(tidx);
CHL -= abs(C[pidx] - C[tidx]);
EV.insert(f(pidx, didx));
CHL += abs(C[pidx] - C[didx]);
} else if(0 < didx) {
EV.insert(f(tidx, didx));
CHL += abs(C[tidx] - C[didx]);
}
}
}
if(debug) {
printf("SZ %d :: ", sz(CH));
for(int v : CH) printf("%d ", v);
puts("");
printf("CHL = %lld\n", CHL);
ll sum = 0;
vector<int> V;
for(int v : CH) V.eb(v);
for(int i = 1; i < sz(V); i++)
sum += abs(C[V[i-1]] - C[V[i]]);
printf("REAL CHL = %lld\n", sum);
}
ll &ret = Ans[i];
int X = A[i];
if(debug) {
printf("i=%d, X=%d\n", i, X);
}
if(1 < sz(CH)) {
int ridx = *CH.begin(), pidx = -1;
{
auto it = CH.begin();
it++;
pidx = *it;
}
ret = CHL - ll(sz(CH) - 1) * L[i];
if(debug) {
printf("ridx=%d, pidx=%d, def ret=%lld\n", ridx, pidx, ret);
}
if(C[ridx] < C[pidx]) ret += abs(C[ridx] - X);
else ret += abs(ll(C[ridx]) - L[i] - X);
if(debug) printf("dist = %lld\n", abs(ll(C[ridx] - L[i] - X)));
} else {
ll ms = CMX - L[i];
int ridx = *CH.begin(), rx = C[ridx];
if(rx < ms) exit(-1);
if(rx < X) ret = X - rx;
else if(ms <= X) ret = 0;
else ret = ms - X;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];
for(int i = 1; i <= Q; i++) cin >> C[i];
for(int i = 1; i <= N; i++) L[i] = B[i] - A[i];
{
vector<int> V;
V.eb(C[1]);
for(int i = 2; i <= Q; i++)
if(V.back() != C[i]) V.eb(C[i]);
Q = sz(V);
for(int i = 0; i < Q; i++)
C[i+1] = V[i];
}
if(1 < Q) {
if(C[2] < C[1]) {
for(int i = 1; i <= Q; i++) C[i] = -C[i];
for(int i = 1; i <= N; i++) A[i] = -B[i];
}
vector<int> V;
V.eb(C[1]); V.eb(C[2]);
for(int i = 3; i <= Q; i++) {
for(; 1 < sz(V) && ((befv(V) < V.back()) == (V.back() < C[i])); V.pop_back());
V.eb(C[i]);
}
Q = sz(V);
for(int i = 0; i < Q; i++)
C[i+1] = V[i];
}
if(debug) {
printf("Q=%d\n", Q);
for(int i = 1; i <= Q; i++) printf("%d ", C[i]);
puts("");
}
process();
for(int i = 1; i <= N; i++) printf("%lld\n", Ans[i]);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1144 KB |
Output is correct |
| 2 |
Incorrect |
536 ms |
16096 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
16096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1144 KB |
Output is correct |
| 2 |
Incorrect |
536 ms |
16096 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
