| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677441 |
2023-01-03T11:15:50 Z |
onjo0127 |
None (JOI15_walls) |
C++11 |
|
3000 ms |
18564 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using ll = long long;
ll ans[200009];
int N, M, A[200009], B[200009], L[200009], R[200009], V[200009];
bool C[200009];
struct fenwick {
ll F[200009];
ll get(int x) {
++x;
ll s = 0;
for(int i=x; i>=1; i-=(i&-i)) s += F[i];
return s;
}
void upd(int x, int y) {
++x;
for(int i=x; i<=M; i+=(i&-i)) F[i] += y;
}
} F1, F2;
int dst(int l, int r, int x) {
if(x < l) return l-x;
if(l <= x && x <= r) return 0;
if(r < x) return x-r;
}
int main() {
vector<int> W;
scanf("%d%d", &N, &M);
for(int i=1; i<=N; i++) {
scanf("%d%d", &A[i], &B[i]);
W.push_back(i);
}
sort(W.begin(), W.end(), [&](int p, int q) { return B[p] - A[p] < B[q] - A[q]; });
vector<int> P;
while(M--) {
int x; scanf("%d", &x);
int K = P.size();
if(K <= 1) P.push_back(x);
else {
if(P[K-2] < P[K-1] && P[K-1] <= x) P.pop_back();
else if(P[K-2] > P[K-1] && P[K-1] >= x) P.pop_back();
P.push_back(x);
}
}
M = P.size();
set<int> S;
priority_queue<tiii> pq;
L[0] = R[0] = P[0]; C[0] = 1;
for(int i=0; i<M; i++) {
S.insert(i);
if(i) {
V[i] = max(P[i] - P[i-1], P[i-1] - P[i]);
F1.upd(i, V[i]);
F2.upd(i, +1);
L[i] = min(L[i-1], P[i]);
R[i] = max(R[i-1], P[i]);
pq.push({-V[i], i-1, i});
}
}
for(auto& it: W) {
while(pq.size()) {
int g, a, b; tie(g, a, b) = pq.top(); g = -g;
if(C[a] || C[b]) {
pq.pop();
continue;
}
if(g > B[it] - A[it]) break;
pq.pop();
C[b] = 1; F1.upd(b, -V[b]); F2.upd(b, -1); S.erase(b);
auto nt = S.upper_bound(b);
if(nt != S.end()) {
C[a] = 1; F1.upd(a, -V[a]); F2.upd(a, -1); S.erase(a);
nt = S.upper_bound(b);
auto pt = prev(nt);
F1.upd(*nt, V[a] - V[b]); V[*nt] += V[a] - V[b];
pq.push({-V[*nt], *pt, *nt});
}
}
int l = 0, r = M-1, f = -1;
while(l <= r) {
int m = l+r >> 1;
if(L[m] < A[it] || B[it] < R[m]) r = m-1, f = m;
else l = m+1;
}
if(f == -1) continue;
int x = f;
while(1) {
ans[it] += dst(A[it], B[it], P[x]);
int d = 0;
if(P[x] < A[it]) d = P[x] - A[it];
if(B[it] < P[x]) d = P[x] - B[it];
A[it] += d; B[it] += d;
auto nt = S.upper_bound(x);
if(nt == S.end()) break;
x = *nt;
}
while(++x < M) {
ans[it] += dst(A[it], B[it], P[x]);
int d = 0;
if(P[x] < A[it]) d = P[x] - A[it];
if(B[it] < P[x]) d = P[x] - B[it];
A[it] += d; B[it] += d;
}
/*
if(nt != S.end()) {
int d = 0;
if(P[f] < A[it]) d = P[f] - A[it];
if(B[it] < P[f]) d = P[f] - B[it];
ans[it] += dst(A[it] + d, B[it] + d, P[*nt]);
ans[it] += F1.get(M-1) - F1.get(*nt) - (F2.get(M-1) - F2.get(*nt)) * (B[it] - A[it]);
}
*/
}
for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
return 0;
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:87:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int m = l+r >> 1;
| ~^~
walls.cpp: In function 'int dst(int, int, int)':
walls.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
29 | }
| ^
walls.cpp: In function 'int main()':
walls.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d%d", &A[i], &B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
walls.cpp:41:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
852 KB |
Output is correct |
| 2 |
Correct |
123 ms |
13616 KB |
Output is correct |
| 3 |
Correct |
184 ms |
18564 KB |
Output is correct |
| 4 |
Correct |
180 ms |
18548 KB |
Output is correct |
| 5 |
Correct |
175 ms |
18400 KB |
Output is correct |
| 6 |
Incorrect |
120 ms |
18556 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
1964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
852 KB |
Output is correct |
| 2 |
Correct |
123 ms |
13616 KB |
Output is correct |
| 3 |
Correct |
184 ms |
18564 KB |
Output is correct |
| 4 |
Correct |
180 ms |
18548 KB |
Output is correct |
| 5 |
Correct |
175 ms |
18400 KB |
Output is correct |
| 6 |
Incorrect |
120 ms |
18556 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
