| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56921 |
2018-07-13T07:42:42 Z |
윤교준(#1636) |
None (JOI15_walls) |
C++11 |
|
1209 ms |
59008 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;
struct BIT {
BIT() { init(); }
int d[MAXQ];
void init() { fill(d, d+MAXQ, -INF); }
void upd(int x, int r) {
for(x += 2; x < MAXQ; x += rb(x))
upmax(d[x], r);
}
int get(int x) {
int r = -INF; for(x += 2; x; x -= rb(x))
upmax(r, d[x]);
return r;
}
} bit;
multiset<pii> EV;
set<int> CH;
ll CHL;
int A[MAXN], B[MAXN], L[MAXN], O[MAXN];
int C[MAXQ];
ll Ans[MAXN];
int N, Q;
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]);
for(int i = 1; i <= Q; i++) bit.upd(i, C[i]);
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];
if(debug) {
printf("oi=%d, i=%d, L=%d : at %d\n", oi, i, L[i], A[i]);
}
for(int idx, l, X; !EV.empty();) {
tie(l, idx) = *EV.begin();
if(L[i] < l) break;
X = (idx & 1) ? C[idx] : (C[idx] - l);
vector<int> V; V.eb(idx);
bool flag = false;
for(auto it = CH.lower_bound(idx);;) {
it++; if(CH.end() == it) break;
int uidx = *it, s, e;
e = C[uidx]; s = e-l;
if(X < s || e < X) {
flag = true;
V.eb(uidx);
break;
}
V.eb(uidx);
}
if(debug) {
printf("idx=%d, l=%d, X=%d\n", idx, l, X);
for(int v : V) printf("%d ", v);
puts("");
}
for(int i = 1, n = sz(V), a, b; i < n; i++) {
a = V[i-1]; b = V[i];
EV.erase(pii(abs(C[a] - C[b]), a));
if(!flag || i+1 < n) CH.erase(b);
CHL -= abs(C[a] - C[b]);
}
int didx = -1, uidx = -1;
{
auto it = CH.lower_bound(idx);
if(CH.begin() != it) {
it--;
didx = *it;
}
}
{
auto it = CH.lower_bound(idx);
it++;
if(CH.end() != it) {
uidx = *it;
}
}
if(debug) {
printf("didx=%d, uidx=%d\n", didx, uidx);
printf("CHL = %lld\n", CHL);
}
if(0 < didx && 0 < uidx) {
CH.erase(idx);
CHL -= abs(C[idx] - C[didx]);
EV.erase(pii(abs(C[idx] - C[didx]), didx));
CHL += abs(C[uidx] - C[didx]);
EV.insert(pii(abs(C[uidx] - C[didx]), didx));
} else if(didx < 0 && 0 < uidx) {
CH.erase(idx);
}
}
int ridx = *CH.begin();
int ms = bit.get(ridx) - L[i];
ll &ret = Ans[i];
ret = CHL - ll(sz(CH)-1) * L[i];
if(debug) {
printf("ridx=%d, sz=%d, ms=%d\n", ridx, sz(CH), ms);
}
if(C[ridx] < ms) ret += abs(A[i] - ms) + abs(ms - C[ridx]);
else if(1 < sz(CH)) ret += abs(C[ridx] - A[i]);
else {
ms = bit.get(Q) - L[i];
if(C[ridx] < A[i]) ret = A[i] - C[ridx];
else if(ms <= A[i]) ret = 0;
else ret = ms - A[i];
}
}
}
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 |
8 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
337 ms |
14592 KB |
Output is correct |
| 3 |
Correct |
598 ms |
20980 KB |
Output is correct |
| 4 |
Correct |
453 ms |
20980 KB |
Output is correct |
| 5 |
Correct |
534 ms |
20980 KB |
Output is correct |
| 6 |
Correct |
347 ms |
20980 KB |
Output is correct |
| 7 |
Correct |
30 ms |
20980 KB |
Output is correct |
| 8 |
Correct |
34 ms |
20980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
20980 KB |
Output is correct |
| 2 |
Correct |
503 ms |
20980 KB |
Output is correct |
| 3 |
Correct |
168 ms |
20980 KB |
Output is correct |
| 4 |
Correct |
1209 ms |
35496 KB |
Output is correct |
| 5 |
Correct |
634 ms |
35496 KB |
Output is correct |
| 6 |
Correct |
900 ms |
43760 KB |
Output is correct |
| 7 |
Correct |
733 ms |
43760 KB |
Output is correct |
| 8 |
Correct |
841 ms |
52348 KB |
Output is correct |
| 9 |
Correct |
116 ms |
52348 KB |
Output is correct |
| 10 |
Incorrect |
365 ms |
59008 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
337 ms |
14592 KB |
Output is correct |
| 3 |
Correct |
598 ms |
20980 KB |
Output is correct |
| 4 |
Correct |
453 ms |
20980 KB |
Output is correct |
| 5 |
Correct |
534 ms |
20980 KB |
Output is correct |
| 6 |
Correct |
347 ms |
20980 KB |
Output is correct |
| 7 |
Correct |
30 ms |
20980 KB |
Output is correct |
| 8 |
Correct |
34 ms |
20980 KB |
Output is correct |
| 9 |
Correct |
35 ms |
20980 KB |
Output is correct |
| 10 |
Correct |
503 ms |
20980 KB |
Output is correct |
| 11 |
Correct |
168 ms |
20980 KB |
Output is correct |
| 12 |
Correct |
1209 ms |
35496 KB |
Output is correct |
| 13 |
Correct |
634 ms |
35496 KB |
Output is correct |
| 14 |
Correct |
900 ms |
43760 KB |
Output is correct |
| 15 |
Correct |
733 ms |
43760 KB |
Output is correct |
| 16 |
Correct |
841 ms |
52348 KB |
Output is correct |
| 17 |
Correct |
116 ms |
52348 KB |
Output is correct |
| 18 |
Incorrect |
365 ms |
59008 KB |
Output isn't correct |
