| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 796948 |
2023-07-29T00:29:22 Z |
eltu0815 |
Fish 2 (JOI22_fish2) |
C++14 |
|
1282 ms |
40292 KB |
#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1987654321)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
int n, q;
int arr[100005];
struct SEG1 {
ll seg[400005];
void update(int str, int ed, int idx, ll val, int node) {
if(str == ed) {
seg[node] = val;
return;
}
int mid = str + ed >> 1;
if(idx <= mid) update(str, mid, idx, val, node << 1);
else update(mid + 1, ed, idx, val, node << 1 | 1);
seg[node] = seg[node << 1] + seg[node << 1 | 1];
}
ll query(int str, int ed, int left, int right, int node) {
if(str > right || ed < left) return 0;
if(left <= str && ed <= right) return seg[node];
int mid = str + ed >> 1;
return query(str, mid, left, right, node << 1) + query(mid + 1, ed, left, right, node << 1 | 1);
}
} seg1;
struct SEG2 {
int seg[400005];
void update(int str, int ed, int idx, int val, int node) {
if(str == ed) {
seg[node] = val;
return;
}
int mid = str + ed >> 1;
if(idx <= mid) update(str, mid, idx, val, node << 1);
else update(mid + 1, ed, idx, val, node << 1 | 1);
seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
int get_mx(int str, int ed, int left, int right, int val, int node) {
if(str > right || ed < left) return -1;
if(seg[node] <= val) return -1;
if(str == ed) return str;
int mid = str + ed >> 1;
int tmp = get_mx(mid + 1, ed, left, right, val, node << 1 | 1);
if(tmp != -1) return tmp;
return get_mx(str, mid, left, right, val, node << 1);
}
int get_mn(int str, int ed, int left, int right, ll val, int node) {
if(str > right || ed < left) return -1;
if(seg[node] <= val) return -1;
if(str == ed) return str;
int mid = str + ed >> 1;
int tmp = get_mn(str, mid, left, right, val, node << 1);
if(tmp != -1) return tmp;
return get_mn(mid + 1, ed, left, right, val, node << 1 | 1);
}
} seg2;
struct SEG3 {
struct Node{
int mn, cnt;
Node(int a = 0, int b = 1) { mn = a, cnt = b; }
};
Node seg[400005];
int lazy[400005];
Node Merge(Node l, Node r) {
Node ret; ret.cnt = 0;
ret.mn = min(l.mn, r.mn);
if(l.mn == ret.mn) ret.cnt += l.cnt;
if(r.mn == ret.mn) ret.cnt += r.cnt;
return ret;
}
void init(int str, int ed, int node) {
lazy[node] = 0;
if(str == ed) {
seg[node].mn = 0, seg[node].cnt = 1;
return;
}
int mid = str + ed >> 1;
init(str, mid, node << 1);
init(mid + 1, ed, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
void lazyProp(int str, int ed, int node) {
if(lazy[node]) {
seg[node].mn += lazy[node];
if(str != ed) {
lazy[node << 1] += lazy[node];
lazy[node << 1 | 1] += lazy[node];
}
lazy[node] = 0;
}
}
void update(int str, int ed, int left, int right, int val, int node) {
lazyProp(str, ed, node);
if(str > right || ed < left) return;
if(left <= str && ed <= right) {
lazy[node] += val;
lazyProp(str, ed, node);
return;
}
int mid = str + ed >> 1;
update(str, mid, left, right, val, node << 1);
update(mid + 1, ed, left, right, val, node << 1 | 1);
seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}
Node query(int str, int ed, int left, int right, int node) {
lazyProp(str, ed, node);
if(str > right || ed < left) return Node(inf, 0);
if(left <= str && ed <= right) return seg[node];
int mid = str + ed >> 1;
return Merge(query(str, mid, left, right, node << 1), query(mid + 1, ed, left, right, node << 1 | 1));
}
} seg3;
set<pii> s;
struct SEG4 {
vector<pii> seg[400005];
void update(int str, int ed, int l, int r, int node) {
int mid = str + ed >> 1;
if(str == ed || (l <= mid && r > mid)) {
seg[node].push_back({l, r});
seg3.update(1, n, l, r, 1, 1);
return;
}
if(r <= mid) update(str, mid, l, r, node << 1);
else update(mid + 1, ed, l, r, node << 1 | 1);
}
void erasex(int str, int ed, int x, int node) {
while(!seg[node].empty() && seg[node].back().first <= x && x <= seg[node].back().second) {
seg3.update(1, n, seg[node].back().first, seg[node].back().second, -1, 1);
s.erase({seg[node].back().first, seg[node].back().second});
seg[node].pop_back();
}
if(str == ed) return;
int mid = str + ed >> 1;
if(x <= mid) erasex(str, mid, x, node << 1);
else erasex(mid + 1, ed, x, node << 1 | 1);
}
} seg4;
void update(int i) {
vector<pii> left, right;
int j = i;
while(j > 1) {
j = seg2.get_mx(1, n, 1, j - 1, arr[j], 1);
if(j == -1) break;
left.push_back({j, seg1.query(1, n, 1, j, 1)});
}
j = i;
while(j < n) {
j = seg2.get_mn(1, n, j + 1, n, arr[j], 1);
if(j == -1) break;
right.push_back({j, seg1.query(1, n, 1, j - 1, 1)});
}
vector<pii> range;
for(auto l : left) for(auto r : right) {
if(r.second - l.second < min(arr[r.first], arr[l.first])) {
range.push_back({l.first + 1, r.first - 1});
}
}
if(i > 1 && seg1.query(1, n, 1, i - 1, 1) < arr[i]) range.push_back({1, i - 1});
if(i < n && seg1.query(1, n, i + 1, n, 1) < arr[i]) range.push_back({i + 1, n});
sort(range.begin(), range.end(), [&](auto a, auto b) {
if(a.first != b.first) return a.first >= b.first;
else return a.second <= b.second;
});
for(auto [l, r] : range) {
if(s.find({l, r}) == s.end()) {
seg4.update(1, n, l, r, 1);
s.insert({l, r});
}
}
}
int compL(int i, int lim) {
vector<int> right;
int j = i;
while(j < n) {
j = seg2.get_mn(1, n, j + 1, n, arr[j], 1);
if(j == -1) break;
right.push_back(j);
}
int mx = i;
for(auto r : right) {
if(r <= lim && seg1.query(1, n, i, r - 1, 1) < arr[r]) mx = max(mx, r);
}
return mx;
}
int compR(int i, int lim) {
vector<int> left;
int j = i;
while(j > 1) {
j = seg2.get_mx(1, n, 1, j - 1, arr[j], 1);
if(j == -1) break;
left.push_back(j);
}
int mn = i;
for(auto l : left) {
if(l >= lim && seg1.query(1, n, l + 1, i, 1) < arr[l]) mn = min(mn, l);
}
return mn;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n; seg3.init(1, n, 1);
for(int i = 1; i <= n; ++i) cin >> arr[i];
for(int i = 1; i <= n; ++i) seg1.update(1, n, i, arr[i], 1);
for(int i = 1; i <= n; ++i) seg2.update(1, n, i, arr[i], 1);
for(int i = 1; i <= n; ++i) update(i);
cin >> q;
while(q--) {
int t, a, b; cin >> t >> a >> b;
if(t == 1) {
seg4.erasex(1, n, a, 1);
if(a > 1) seg4.erasex(1, n, a - 1, 1);
if(a < n) seg4.erasex(1, n, a + 1, 1);
arr[a] = b;
seg1.update(1, n, a, b, 1);
update(a);
if(a > 1) update(a - 1);
if(a < n) update(a + 1);
}
else {
int l = a, r = b;
a = compL(a, r); b = compR(b, l);
assert(a <= b);
cout << seg3.query(1, n, a, b, 1).cnt << '\n';
}
}
return 0;
}
Compilation message
fish2.cpp: In member function 'void SEG1::update(int, int, int, ll, int)':
fish2.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'll SEG1::query(int, int, int, int, int)':
fish2.cpp:30:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'void SEG2::update(int, int, int, int, int)':
fish2.cpp:42:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'int SEG2::get_mx(int, int, int, int, int, int)':
fish2.cpp:51:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'int SEG2::get_mn(int, int, int, int, ll, int)':
fish2.cpp:60:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'void SEG3::init(int, int, int)':
fish2.cpp:87:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'void SEG3::update(int, int, int, int, int, int)':
fish2.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'SEG3::Node SEG3::query(int, int, int, int, int)':
fish2.cpp:119:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
119 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'void SEG4::update(int, int, int, int, int)':
fish2.cpp:128:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
128 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In member function 'void SEG4::erasex(int, int, int, int)':
fish2.cpp:145:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
145 | int mid = str + ed >> 1;
| ~~~~^~~~
fish2.cpp: In function 'void update(int)':
fish2.cpp:180:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
180 | for(auto [l, r] : range) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12804 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 5 |
Incorrect |
57 ms |
13104 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Incorrect |
1282 ms |
40292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12804 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 5 |
Incorrect |
57 ms |
13104 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Incorrect |
1282 ms |
40292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Incorrect |
1282 ms |
40292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12804 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 5 |
Incorrect |
57 ms |
13104 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
