| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677539 |
2023-01-03T14:39:09 Z |
onjo0127 |
None (JOI15_walls) |
C++17 |
|
3000 ms |
18596 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];
vector<int> E = {0};
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]);
if(L[i-1] != L[i] || R[i-1] != R[i]) {
int K = E.size();
if(K <= 1) E.push_back(i);
else {
if(P[E[K-2]] < P[E[K-1]] && P[E[K-1]] <= P[i]) E.pop_back();
else if(P[E[K-2]] > P[E[K-1]] && P[E[K-1]] >= P[i]) E.pop_back();
E.push_back(i);
}
}
pq.push({-V[i], i-1, i});
}
}
for(auto& it: E) C[it] = 1;
int k = 0;
for(auto& it: W) {
while(pq.size() && S.size() > 3) {
int g, a, b; tie(g, a, b) = pq.top(); g = -g;
if(g > B[it] - A[it]) break;
pq.pop();
if(*S.rbegin() == b && !C[b]) {
C[b] = 1; F1.upd(b, -V[b]); F2.upd(b, -1); S.erase(b);
continue;
}
if(C[a] || C[b]) continue;
C[a] = 1; F1.upd(a, -V[a]); F2.upd(a, -1); S.erase(a);
C[b] = 1; F1.upd(b, -V[b]); F2.upd(b, -1); S.erase(b);
auto nt = S.upper_bound(b), pt = prev(nt);
F1.upd(*nt, V[a] - V[b]); V[*nt] += V[a] - V[b];
pq.push({-V[*nt], *pt, *nt});
}
while(k+1 < E.size() && max(P[E[k+1]] - P[E[k]], P[E[k]] - P[E[k+1]]) <= B[it] - A[it]) ++k;
k = max(0, k-1);
int x = E[k];
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;
}
/*
ans[it] = dst(A[it], B[it], P[E[k]]);
auto nt = S.upper_bound(E[k]);
if(nt != S.end()) {
int d = 0;
if(P[E[k]] < A[it]) d = P[E[k]] - A[it];
if(B[it] < P[E[k]]) d = P[E[k]] - 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:95:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | while(k+1 < E.size() && max(P[E[k+1]] - P[E[k]], P[E[k]] - P[E[k+1]]) <= B[it] - A[it]) ++k;
| ~~~~^~~~~~~~~~
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 |
117 ms |
13620 KB |
Output is correct |
| 3 |
Correct |
172 ms |
18524 KB |
Output is correct |
| 4 |
Correct |
146 ms |
18516 KB |
Output is correct |
| 5 |
Incorrect |
171 ms |
18596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
1968 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 |
117 ms |
13620 KB |
Output is correct |
| 3 |
Correct |
172 ms |
18524 KB |
Output is correct |
| 4 |
Correct |
146 ms |
18516 KB |
Output is correct |
| 5 |
Incorrect |
171 ms |
18596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
