| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 639160 |
2022-09-08T18:37:29 Z |
cadmiumsky |
Fire (JOI20_ho_t5) |
C++14 |
|
739 ms |
33292 KB |
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,int>;
const int nmax = 2e5 + 5;
#define lsb(x) (x & -x)
#define int ll
struct AIB {
int tree[nmax * 2];
int offset, len;
void init(int l, int r) {
offset = -l + 1;
len = r - l + 1;
memset(tree, 0, sizeof(tree[0]) * (len + 1));
}
void upd(int x, int val) {
x += offset;
//cerr << "+ " << x << ' ' << val << '\n';
while(x <= len)
tree[x] += val,
x += lsb(x);
}
int query(int x) {
x += offset;
int sum = 0;
while(x > 0)
sum += tree[x],
x -= lsb(x);
return sum;
}
int query(int l, int r) {
//cerr << l + offset << ' ' << r + offset << '\n';
return query(r) - query(l - 1);
}
};
#undef int
namespace DS {
AIB offset, firstd, secondd;
namespace Updates {
vector<tii> upd;
void push(int x, int val, int l, int r) {
upd.emplace_back(l, val, x);
upd.emplace_back(r + 1, -val, x + (r + 1) - l);
}
void update(int t, int val, int x) {
//cerr << "+ " << t << ' ' << val << ' ' << x << '\n';
int coef = x - t;
offset.upd(coef, -val * t);
firstd.upd(coef, val);
secondd.upd(coef, (-coef) * val);
}
}
namespace Queries {
int side;
vector<tii> qs;
void push(int l, int r, int t) {
qs.emplace_back(t, l, r);
}
ll query(int t, int l, int r) {
auto [right, mid, left] = tii{r, r - t, l - t};
if(side == 1) { // Orizontal \\ partea superioara
//cerr << t << ' ' << l << ' ' << r << '\t' << '*' << (t + 1) << '\n';
return (ll)offset.query(left, mid) + (ll)firstd.query(left, mid) * (t + 1);
}
else if(side == -1) {
if(mid == right) return 0;
mid++;
return (ll)offset.query(mid, right) + (ll)secondd.query(mid, right) + (ll)firstd.query(mid, right) * (right + 1);
}
else if(side == -2) {
mid = l;
return (ll)offset.query(left, mid) + (ll)secondd.query(left, mid) + (ll)firstd.query(left, mid) * mid;
}
assert(false);
return 0;
}
}
using namespace Queries;
using namespace Updates;
void init(int n) {
vector<int> ind(qs.size());
vector<ll> rez(qs.size(), 0);
//side == 1
Queries::side = 1;
//
offset.init(-n - 1, n + 1);
firstd.init(-n - 1, n + 1);
secondd.init(-n - 1, n + 1);
iota(all(ind), 0);
sort(all(ind), [&](int a, int b) { return qs[a] < qs[b]; });
sort(all(upd));
int ptr = 0;
for(auto i : ind) {
auto [t, l, r] = qs[i];
while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
auto [time, val, poz] = upd[ptr];
Updates::update(time, val, poz);
ptr++;
}
rez[i] = Queries::query(t, l, r);
}
//for(auto x : rez)
//cout << x << ' ';
//cout << '\n';
//side == -1
Queries::side = -1;
//
offset.init(-n - 1, n + 1);
firstd.init(-n - 1, n + 1);
secondd.init(-n - 1, n + 1);
iota(all(ind), 0);
sort(all(ind), [&](int a, int b) { return get<2>(qs[a]) < get<2>(qs[b]); });
sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
ptr = 0;
for(auto i : ind) {
auto [t, l, r] = qs[i];
while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
auto [time, val, poz] = upd[ptr];
Updates::update(time, val, poz);
ptr++;
}
rez[i] += Queries::query(t, l, r);
}
//for(auto x : rez)
//cout << x << ' ';
//cout << '\n';
//side == -2
Queries::side = -2;
//
offset.init(-n - 1, n + 1);
firstd.init(-n - 1, n + 1);
secondd.init(-n - 1, n + 1);
iota(all(ind), 0);
sort(all(ind), [&](int a, int b) { return get<1>(qs[a]) < get<1>(qs[b]); });
sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
ptr = 0;
for(auto i : ind) {
auto [t, l, r] = qs[i];
while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
auto [time, val, poz] = upd[ptr];
Updates::update(time, val, poz);
ptr++;
}
rez[i] -= Queries::query(t, l, r);
}
for(auto x : rez)
cout << x << ' ';
cout << '\n';
return;
}
}
signed main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for(auto &x : v)
cin >> x;
vector<int> poz, rend;
for(int i = n - 1; i >= 0; i--) {
DS::Updates::push(i, v[i], 0, 0);
int boundary = i;
while(!poz.empty() && v[poz.back()] <= v[i]) {
DS::Updates::push(poz.back(), v[i] - v[poz.back()], poz.back() - i, rend.back() - i);
boundary = rend.back();
poz.pop_back();
rend.pop_back();
}
poz.emplace_back(i);
rend.emplace_back(boundary);
}
for(int i = 0, t, l, r; i < q; i++) {
cin >> t >> l >> r;
--l;
--r;
DS::Queries::push(l, r, t);
}
DS::init(n);
return 0;
}
/**
De-atâtea nopți aud plouând,
Aud materia plângând..
Sînt singur, și mă duce un gând
Spre locuințele lacustre.
Și parcă dorm pe scânduri ude,
În spate mă izbește-un val --
Tresar prin somn și mi se pare
Că n-am tras podul de la mal.
Un gol istoric se întinde,
Pe-același vremuri mă găsesc..
Și simt cum de atâta ploaie
Pilonii grei se prăbușesc.
De-atâtea nopți aud plouând,
Tot tresărind, tot așteptând..
Sînt singur, și mă duce-un gând
Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/
Compilation message
ho_t5.cpp: In function 'll DS::Queries::query(int, int, int)':
ho_t5.cpp:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | auto [right, mid, left] = tii{r, r - t, l - t};
| ^
ho_t5.cpp: In function 'void DS::init(int)':
ho_t5.cpp:113:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | auto [t, l, r] = qs[i];
| ^
ho_t5.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
| ~~~~^~~~~~~~~~~~
ho_t5.cpp:115:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | auto [time, val, poz] = upd[ptr];
| ^
ho_t5.cpp:140:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
140 | auto [t, l, r] = qs[i];
| ^
ho_t5.cpp:141:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
| ~~~~^~~~~~~~~~~~
ho_t5.cpp:142:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | auto [time, val, poz] = upd[ptr];
| ^
ho_t5.cpp:165:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
165 | auto [t, l, r] = qs[i];
| ^
ho_t5.cpp:166:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
| ~~~~^~~~~~~~~~~~
ho_t5.cpp:167:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
167 | auto [time, val, poz] = upd[ptr];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
707 ms |
33292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
739 ms |
32356 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
606 ms |
29728 KB |
Output is correct |
| 2 |
Correct |
630 ms |
29852 KB |
Output is correct |
| 3 |
Correct |
615 ms |
30592 KB |
Output is correct |
| 4 |
Correct |
597 ms |
29728 KB |
Output is correct |
| 5 |
Correct |
612 ms |
29860 KB |
Output is correct |
| 6 |
Correct |
647 ms |
29904 KB |
Output is correct |
| 7 |
Correct |
606 ms |
30440 KB |
Output is correct |
| 8 |
Correct |
608 ms |
30220 KB |
Output is correct |
| 9 |
Correct |
614 ms |
29944 KB |
Output is correct |
| 10 |
Correct |
586 ms |
30112 KB |
Output is correct |
| 11 |
Correct |
631 ms |
30088 KB |
Output is correct |
| 12 |
Correct |
594 ms |
30140 KB |
Output is correct |
| 13 |
Correct |
597 ms |
30012 KB |
Output is correct |
| 14 |
Correct |
586 ms |
29976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
