| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 545059 |
2022-04-03T13:20:57 Z |
Asymmetry |
Fire (JOI20_ho_t5) |
C++17 |
|
437 ms |
46624 KB |
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
struct pytanie {
int l, r, id;
};
struct SegTree {
struct node {
long long A, B;
};
vector<node> st;
int com;
SegTree(int n) {
com = 1;
while (com < n) {
com <<= 1;
}
st.resize(com << 1);
--com;
}
void wstaw(int x, long long A, long long B) {
x += com;
st[x] = {A, B};
x >>= 1;
while (x) {
st[x] = {st[x * 2].A + st[x * 2 + 1].A, st[x * 2].B + st[x * 2 + 1].B};
x >>= 1;
}
}
long long pytaj(int a, int b, int tm) {
a += com;
b += com + 1;
long long ret = 0;
while (a < b) {
if (a & 1) {
ret += st[a].A * tm + st[a].B;
++a;
}
if (b & 1) {
ret += st[b - 1].A * tm + st[b - 1].B;
}
a >>= 1;
b >>= 1;
}
return ret;
}
};
struct nod {
int lf, rg;
};
const int N = 201000;
int n, q, com;
int t[N];
int lf[N]; // następny na lewo większy
int rg[N]; // następny na prawo większy równy
int slp[N]; // aktualny slope
long long odp[N];
vector<pytanie> pyt[N]; // zapytania po czasie
vector<int> zgon[N]; // kto właśnie znika
vector<int> slope[N]; // komu maleje slope w tym momencie
vector<nod> ts;
int kiedy_zgon(int x) { // pierwszy moment nieistnienia x
if (lf[x] == 0) {
return 1e9;
}
return rg[x] - lf[x] - 1;
}
pair<int, int> aktualny(int x, int tm) { // aktualny przedział pożaru x w momencie tm
int l = x;
if (lf[x]) {
l = max(l, lf[x] + tm + 1);
}
int r = min(rg[x] - 1, x + tm);
return {l, r};
}
void update(int x) {
int l = x << 1;
int r = l ^ 1;
ts[x] = {min(ts[l].lf, ts[r].lf), max(ts[l].rg, ts[r].rg)};
}
// pożar, który posiada w sobie p w momencie tm
int fin(int x, int l, int r, int tm, int p) {
if (l == r) {
return l;
}
if (ts[x * 2].lf > ts[x * 2].rg) {
return fin(x * 2 + 1, (l + r) / 2 + 1, r, tm, p);
}
auto lf = aktualny(ts[x * 2].rg, tm);
if (lf.second < p) {
return fin(x * 2 + 1, (l + r) / 2 + 1, r, tm, p);
}
return fin(x * 2, l, (l + r) / 2, tm, p);
}
void zgas(int x) {
x += com;
ts[x] = {(int)1e9, (int)-1e9};
x >>= 1;
while (x) {
update(x);
x >>= 1;
}
}
int main() {
scanf("%d%d", &n, &q);
com = 1;
while (com < n) {
com <<= 1;
}
ts.resize(com << 1);
--com;
SegTree st(n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &t[i]);
st.wstaw(i, t[i], t[i]);
ts[i + com] = {i, i};
slp[i] = 1;
}
for (int i = n + 1; i <= com + 1; ++i) {
ts[i + com] = {(int)1e9, (int)-1e9};
}
for (int i = com; i; --i) {
update(i);
}
t[0] = 1e9 + 7;
t[n + 1] = 1e9 + 7;
for (int i = 1; i <= n; ++i) {
lf[i] = i - 1;
while (t[i] >= t[lf[i]]) {
lf[i] = lf[lf[i]];
}
}
for (int i = n; i; --i) {
rg[i] = i + 1;
while (t[i] > t[rg[i]]) {
rg[i] = rg[rg[i]];
}
}
for (int i = 1; i <= n; ++i) {
int x = kiedy_zgon(i);
//~ debug(i, x);
if (x <= n) {
zgon[x].push_back(i);
}
if (lf[i]) {
slope[i - lf[i] - 1].push_back(i);
}
slope[rg[i] - i - 1].push_back(i);
}
//~ for (int i = 0; i <= n; ++i) {
//~ debug(i, slope[i]);
//~ }
//~ for (int i = 0; i <= n; ++i) {
//~ for (int j = 1; j <= n; ++j) {
//~ debug(i, j, aktualny(j, i));
//~ }
//~ }
for (int i = 1; i <= q; ++i) {
int a, b, c;
scanf("%d%d%d", &c, &a, &b);
pyt[c].push_back({a, b, i});
}
for (int tm = 0; tm <= n; ++tm) {
//~ debug(tm);
for (int i : zgon[tm]) {
//~ debug("ZGON", i);
zgas(i);
st.wstaw(i, 0, 0);
}
for (int i : slope[tm]) {
if (slp[i] == 1) { // zamiana na stały
auto x = aktualny(i, tm);
//~ debug(i, x);
st.wstaw(i, 0, (x.second - x.first + 1) * t[i]);
}
else { // zamiana na malejący
auto x = aktualny(i, tm);
//~ debug(i, x);
st.wstaw(i, -t[i], (long long)(tm + x.second - x.first + 1) * t[i]);
}
--slp[i];
//~ debug(i, slp[i]);
}
//~ for (int i = 1; i <= n; ++i) {
//~ printf("%lld ", st.pytaj(i, i, tm));
//~ }
//~ printf("\n");
for (auto i : pyt[tm]) {
int poc = fin(1, 1, com + 1, tm, i.l);
int kon = fin(1, 1, com + 1, tm, i.r);
auto p = aktualny(poc, tm);
auto k = aktualny(kon, tm);
//~ debug(i.l, i.r, i.id, poc, kon, p, k);
odp[i.id] = st.pytaj(poc, kon, tm) - (long long)(i.l - p.first) * t[poc] - (long long)(k.second - i.r) * t[kon];
}
}
for (int i = 1; i <= q; ++i) {
printf("%lld\n", odp[i]);
}
return 0;
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | scanf("%d", &t[i]);
| ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
189 | scanf("%d%d%d", &c, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
14468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
240 ms |
45776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
291 ms |
46624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
42500 KB |
Output is correct |
| 2 |
Correct |
423 ms |
42460 KB |
Output is correct |
| 3 |
Correct |
399 ms |
42872 KB |
Output is correct |
| 4 |
Correct |
415 ms |
42772 KB |
Output is correct |
| 5 |
Correct |
379 ms |
42736 KB |
Output is correct |
| 6 |
Correct |
408 ms |
42496 KB |
Output is correct |
| 7 |
Correct |
378 ms |
42724 KB |
Output is correct |
| 8 |
Correct |
417 ms |
42716 KB |
Output is correct |
| 9 |
Correct |
371 ms |
42816 KB |
Output is correct |
| 10 |
Correct |
395 ms |
42656 KB |
Output is correct |
| 11 |
Correct |
402 ms |
42852 KB |
Output is correct |
| 12 |
Correct |
437 ms |
42796 KB |
Output is correct |
| 13 |
Correct |
366 ms |
42740 KB |
Output is correct |
| 14 |
Correct |
409 ms |
42764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
14468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
