| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677514 |
2023-01-03T13:50:20 Z |
mjhmjh1104 |
None (JOI15_walls) |
C++17 |
|
753 ms |
28876 KB |
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const bool debug = false;
struct Item {
int a;
int b;
int i;
int fi;
int se;
bool operator< (const Item &O) const {
return b - a < O.b - O.a;
}
};
pair<long long, long long> operator+ (const pair<long long, long long> &a, const pair<long long, long long> &b) {
return { a.first + b.first, a.second + b.second };
}
pair<long long, long long> lazy1[524288], lazy2[524288];
void propagate1(int i, int b, int e) {
if (b != e) {
lazy1[i * 2 + 1] = lazy1[i * 2 + 1] + lazy1[i];
lazy1[i * 2 + 2] = lazy1[i * 2 + 2] + lazy1[i];
lazy1[i] = { 0, 0 };
}
}
pair<long long, long long> query1(int i, int b, int e, int p) {
propagate1(i, b, e);
if (p < b || e < p) return { 0, 0 };
if (b == e) return lazy1[i];
int m = (b + e) / 2;
return query1(i * 2 + 1, b, m, p) + query1(i * 2 + 2, m + 1, e, p);
}
void substitute1(int i, int b, int e, int p, long long v) {
propagate1(i, b, e);
if (p < b || e < p) return;
if (b == e) {
lazy1[i] = { v, 0 };
return;
}
int m = (b + e) / 2;
substitute1(i * 2 + 1, b, m, p, v);
substitute1(i * 2 + 2, m + 1, e, p, v);
}
void update1(int i, int b, int e, int l, int r, long long v1, long long v2) {
propagate1(i, b, e);
if (r < l || r < b || e < l) return;
if (l <= b && e <= r) {
lazy1[i] = lazy1[i] + make_pair(v1, v2);
return;
}
int m = (b + e) / 2;
update1(i * 2 + 1, b, m, l, r, v1, v2);
update1(i * 2 + 2, m + 1, e, l, r, v1, v2);
}
void propagate2(int i, int b, int e) {
if (b != e) {
lazy2[i * 2 + 1] = lazy2[i * 2 + 1] + lazy2[i];
lazy2[i * 2 + 2] = lazy2[i * 2 + 2] + lazy2[i];
lazy2[i] = { 0, 0 };
}
}
pair<long long, long long> query2(int i, int b, int e, int p) {
propagate2(i, b, e);
if (p < b || e < p) return { 0, 0 };
if (b == e) return lazy2[i];
int m = (b + e) / 2;
return query2(i * 2 + 1, b, m, p) + query2(i * 2 + 2, m + 1, e, p);
}
void substitute2(int i, int b, int e, int p, long long v) {
propagate2(i, b, e);
if (p < b || e < p) return;
if (b == e) {
lazy2[i] = { v, 0 };
return;
}
int m = (b + e) / 2;
substitute2(i * 2 + 1, b, m, p, v);
substitute2(i * 2 + 2, m + 1, e, p, v);
}
void update2(int i, int b, int e, int l, int r, long long v1, long long v2) {
propagate2(i, b, e);
if (r < l || r < b || e < l) return;
if (l <= b && e <= r) {
lazy2[i] = lazy2[i] + make_pair(v1, v2);
return;
}
int m = (b + e) / 2;
update2(i * 2 + 1, b, m, l, r, v1, v2);
update2(i * 2 + 2, m + 1, e, l, r, v1, v2);
}
long long query1(int x, int l) {
pair<long long, long long> t = query1(0, 0, 262143, x);
return t.first + t.second * l;
}
long long query2(int x, int l) {
pair<long long, long long> t = query2(0, 0, 262143, x);
return t.first + t.second * l;
}
void update1(int p, long long v) {
substitute1(0, 0, 262143, p, v);
}
void update2(int p, long long v) {
substitute2(0, 0, 262143, p, v);
}
void update1(int l, int r, long long uA, long long uB) {
update1(0, 0, 262143, l, r, uA, uB);
}
void update2(int l, int r, long long uA, long long uB) {
update2(0, 0, 262143, l, r, uA, uB);
}
void update(int l, int r, long long uA, long long uB, int y) {
if (debug) printf("UPDATE: [%d,%d], %lld, %lld\n", l, r, uA, uB);
if (y) update2(l, r, uA, uB);
else update1(l, r, uA, uB);
}
int n, m, p[200006];
vector<Item> v, v1, v2;
long long res[200006];
// stick, x, [l, r]
void sum_left(int s, int x, int l, int r, int y) {
if (debug) puts("SUM_LEFT");
if (x <= s) update(l, r, s - x, 0, y);
else update(l, r, x - s, -1, y);
}
void sum_right(int s, int x, int l, int r, int y) {
if (debug) puts("SUM_RIGHT");
if (x >= s) update(l, r, x - s, 0, y);
else update(l, r, s - x, -1, y);
}
void process(vector<Item> &v, vector<pair<int, pair<int, bool>>> &st, int x, int y) {
if (debug) puts("PROCESS");
if (v.empty()) return;
int n = (int)v.size();
int a = v[0].a, b = v[0].b;
if (st.back().second.second) {
a = st.back().first;
b = a + (v[0].b - v[0].a);
} else {
b = st.back().first;
a = b - (v[0].b - v[0].a);
}
if (a <= x && x <= b) return;
int l = 0, r = n - 1;
while (l < r) {
int m = (l + r + 1) / 2;
int a, b;
{
int L = 0, R = (int)st.size() - 1;
while (L < R) {
int M = (L + R + 1) / 2;
if (st[M].second.first >= m) L = M;
else R = M - 1;
}
if (st[L].second.second) {
a = st[L].first;
b = a + (v[m].b - v[m].a);
} else {
b = st[L].first;
a = b - (v[m].b - v[m].a);
}
}
if (a <= x && x <= b) r = m - 1;
else l = m;
}
if (debug) printf("! SIZE=%d\n", (int)st.size());
int k = (int)st.size() - 1, lt = 0;
while (k >= 0 && st[k].second.first <= l) {
if (st[k].second.second) sum_left(st[k].first, x, lt, st[k].second.first, y);
else sum_right(st[k].first, x, lt, st[k].second.first, y);
lt = st[k].second.first + 1;
k--;
st.pop_back();
}
if (k >= 0) {
if (st[k].second.second) sum_left(st[k].first, x, lt, l, y);
else sum_right(st[k].first, x, lt, l, y);
}
if (x < a) st.push_back({ x, { l, true } });
else st.push_back({ x, { l, false } });
if (debug) {
printf("lt=%d, l=%d\n", lt, l);
puts("st:");
for (auto &i: st) printf("%d / %d / %d\n", i.first, i.second.first, i.second.second ? 1 : 0);
}
}
int main() {
scanf("%d%d", &n, &m);
v.resize(n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &v[i].a, &v[i].b);
v[i].i = i;
v[i].fi = v[i].se = (int)1e9;
}
for (int i = 0; i < m; i++) scanf("%d", p + i);
vector<pair<int, int>> queries1, queries2;
vector<pair<int, pair<bool, int>>> queries;
for (int i = 0; i < n; i++) {
// v[i].a 미만 중 첫번: v[i].fi
queries1.push_back({ v[i].a, i });
// v[i].b 초과 중 첫번: v[i].se
queries2.push_back({ v[i].b, i });
}
{
sort(queries1.rbegin(), queries1.rend());
int k = 0;
for (int i = 0; i < m; i++) {
while (k < (int)queries1.size() && p[i] < queries1[k].first) {
v[queries1[k].second].fi = i;
k++;
}
}
}
{
sort(queries2.begin(), queries2.end());
int k = 0;
for (int i = 0; i < m; i++) {
while (k < (int)queries2.size() && p[i] > queries2[k].first) {
v[queries2[k].second].se = i;
k++;
}
}
}
sort(v.begin(), v.end());
for (auto &i: v) {
if (i.fi < i.se) {
queries.push_back({ i.fi, { true, (int)v1.size() } });
v1.push_back(i);
}
if (i.fi > i.se) {
queries.push_back({ i.se, { false, (int)v2.size() } });
v2.push_back(i);
}
}
sort(queries.begin(), queries.end());
vector<pair<int, pair<int, bool>>> st1, st2; // pos, idx, stick to left?
st1.push_back({ (int)1e9, { n - 1, true } });
st2.push_back({ (int)-1e9, { n - 1, false } });
if (debug) printf("v1=%d / v2=%d\n", (int)v1.size(), (int)v2.size());
int k = 0;
for (int i = 0; i < m; i++) {
process(v1, st1, p[i], 0);
process(v2, st2, p[i], 1);
while (k < (int)queries.size() && queries[k].first <= i) {
if (queries[k].second.first) update1(queries[k].second.second, v1[queries[k].second.second].a - p[i]);
else update2(queries[k].second.second, p[i] - v2[queries[k].second.second].b);
k++;
}
}
for (int i = 0; i < (int)v1.size(); i++) res[v1[i].i] = query1(i, v1[i].b - v1[i].a);
for (int i = 0; i < (int)v2.size(); i++) res[v2[i].i] = query2(i, v2[i].b - v2[i].a);
sort(v.begin(), v.end(), [](const Item &a, const Item &b) {
return a.i < b.i;
});
for (int i = 0; i < n; i++) {
if (debug) printf("\nFI=%d / SE=%d\n", v[i].fi, v[i].se);
if (v[i].fi == (int)1e9 && v[i].se == (int)1e9) puts("0");
else printf("%lld\n", res[i]);
}
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
214 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | scanf("%d%d", &v[i].a, &v[i].b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:221:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
221 | for (int i = 0; i < m; i++) scanf("%d", p + i);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
408 KB |
Output is correct |
| 2 |
Correct |
47 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
54 ms |
1120 KB |
Output is correct |
| 4 |
Correct |
58 ms |
1124 KB |
Output is correct |
| 5 |
Correct |
66 ms |
1252 KB |
Output is correct |
| 6 |
Correct |
68 ms |
1068 KB |
Output is correct |
| 7 |
Correct |
26 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
69 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
2904 KB |
Output is correct |
| 2 |
Correct |
219 ms |
3616 KB |
Output is correct |
| 3 |
Correct |
249 ms |
26056 KB |
Output is correct |
| 4 |
Correct |
483 ms |
27016 KB |
Output is correct |
| 5 |
Correct |
474 ms |
26876 KB |
Output is correct |
| 6 |
Correct |
469 ms |
27040 KB |
Output is correct |
| 7 |
Correct |
488 ms |
26852 KB |
Output is correct |
| 8 |
Correct |
467 ms |
27104 KB |
Output is correct |
| 9 |
Correct |
179 ms |
19680 KB |
Output is correct |
| 10 |
Correct |
489 ms |
27064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
408 KB |
Output is correct |
| 2 |
Correct |
47 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
54 ms |
1120 KB |
Output is correct |
| 4 |
Correct |
58 ms |
1124 KB |
Output is correct |
| 5 |
Correct |
66 ms |
1252 KB |
Output is correct |
| 6 |
Correct |
68 ms |
1068 KB |
Output is correct |
| 7 |
Correct |
26 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
69 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
42 ms |
2904 KB |
Output is correct |
| 10 |
Correct |
219 ms |
3616 KB |
Output is correct |
| 11 |
Correct |
249 ms |
26056 KB |
Output is correct |
| 12 |
Correct |
483 ms |
27016 KB |
Output is correct |
| 13 |
Correct |
474 ms |
26876 KB |
Output is correct |
| 14 |
Correct |
469 ms |
27040 KB |
Output is correct |
| 15 |
Correct |
488 ms |
26852 KB |
Output is correct |
| 16 |
Correct |
467 ms |
27104 KB |
Output is correct |
| 17 |
Correct |
179 ms |
19680 KB |
Output is correct |
| 18 |
Correct |
489 ms |
27064 KB |
Output is correct |
| 19 |
Correct |
673 ms |
27356 KB |
Output is correct |
| 20 |
Correct |
691 ms |
27388 KB |
Output is correct |
| 21 |
Correct |
670 ms |
27424 KB |
Output is correct |
| 22 |
Correct |
648 ms |
28792 KB |
Output is correct |
| 23 |
Correct |
753 ms |
28876 KB |
Output is correct |
| 24 |
Correct |
714 ms |
28800 KB |
Output is correct |
| 25 |
Correct |
232 ms |
23072 KB |
Output is correct |
| 26 |
Correct |
346 ms |
27088 KB |
Output is correct |
| 27 |
Correct |
669 ms |
28408 KB |
Output is correct |
