| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 848928 |
2023-09-13T17:58:34 Z |
mickey080929 |
Sushi (JOI16_sushi) |
C++17 |
|
1891 ms |
98500 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int inf = 1e9;
const int B = 640;
struct LazySegmentTree{
int tree[B*4+100];
int lazy[B*4+100];
void init(int n) {
fill(tree, tree+n*4+10, inf);
fill(lazy, lazy+n*4+10, 0);
}
void propagate(int node, int s, int e) {
if (!lazy[node]) return;
tree[node] += lazy[node];
if (s != e) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
lazy[node] = 0;
}
void update_point(int node, int s, int e, int tar, int val) {
propagate(node, s, e);
if (s > tar || tar > e) return;
if (s == e) {
tree[node] = val;
return;
}
int mid = s + e >> 1;
update_point(node<<1, s, mid, tar, val);
update_point(node<<1|1, mid+1, e, tar, val);
tree[node] = min(tree[node<<1], tree[node<<1|1]);
}
void update_range(int node, int s, int e, int l, int r, int val) {
propagate(node, s, e);
if (l > e || s > r) return;
if (l <= s && e <= r) {
lazy[node] = val;
propagate(node, s, e);
return;
}
int mid = s + e >> 1;
update_range(node<<1, s, mid, l, r, val);
update_range(node<<1|1, mid+1, e, l, r, val);
tree[node] = min(tree[node<<1], tree[node<<1|1]);
}
int getmin() { return tree[1]; }
};
struct Bucket{
LazySegmentTree seg;
priority_queue<int> pq;
vector<int> queries;
vector<int> a;
vector<int> use;
vector<int> nxt;
void init() {
pq = priority_queue<int>(a.begin(), a.end());
use.clear();
int cur = 0;
for (int i=0; i<sz(a); i++) {
if (cur <= a[i]) {
cur = a[i];
use.push_back(i);
}
}
seg.init(sz(use));
nxt.clear();
nxt.resize(sz(use));
cur = 0;
for (int i=0; i<sz(use); i++) {
int r = sz(a);
if (i + 1 < sz(use)) r = use[i+1];
if (use[i] + 1 >= r) {
nxt[i] = cur;
continue;
}
int mx = 0, idx = 0;
for (int j=use[i]+1; j<r; j++) {
if (mx < a[j]) {
mx = a[j];
idx = j;
}
}
if (cur >= a[idx]) {
nxt[i] = cur;
continue;
}
cur = a[idx];
nxt[i] = cur;
int lo = 0, hi = sz(use) - 1;
while (lo < hi) {
int mid = lo + hi >> 1;
if (a[mid] <= cur) lo = mid + 1;
else hi = mid;
}
seg.update_point(1, 1, sz(use), i+1, i+1 - lo);
}
}
void apply() {
vector<int> t;
for (auto &x : queries) {
int idx = lower_bound(nxt.begin(), nxt.end(), x) - nxt.begin();
seg.update_range(1, 1, sz(use), idx+1, sz(use), -1);
if (seg.getmin() <= 0) {
for (auto &p : use) t.push_back(a[p]);
sort(t.begin(), t.end());
assert(sz(t) == sz(use));
for (int i=0; i<sz(use); i++) a[use[i]] = t[i];
t.clear();
int cur = x;
for (int i=0; i<sz(a); i++) if (cur <= a[i]) swap(cur, a[i]);
init();
} else t.push_back(x);
}
for (auto &p : use) t.push_back(a[p]);
sort(t.begin(), t.end());
for (int i=0; i<sz(use); i++) a[use[i]] = t[i];
queries.clear();
init();
}
int Push(int x) {
queries.push_back(x);
pq.push(x);
int t = pq.top();
pq.pop();
return t;
}
} buc[B];
int n, q;
int a[400010];
int query(int l, int r, int x) {
int lb = l / B;
int rb = r / B;
buc[lb].apply();
for (int i=l; i<=min({r, n-1, lb*B+B-1}); i++) {
if (x < buc[lb].a[i-lb*B]) {
swap(x, buc[lb].a[i-lb*B]);
}
}
buc[lb].init();
if (lb == rb) return x;
for (int i=lb+1; i<=rb-1; i++) {
x = buc[i].Push(x);
}
buc[rb].apply();
for (int i=rb*B; i<=min(n-1, r); i++) {
if (x < buc[rb].a[i-rb*B]) {
swap(x, buc[rb].a[i-rb*B]);
}
}
buc[rb].init();
return x;
}
int main() {
scanf("%d %d", &n, &q);
for (int i=0; i<n; i++) {
scanf("%d", &a[i]);
buc[i/B].a.push_back(a[i]);
}
for (int i=0; i<=(n-1)/B; i++) {
buc[i].init();
}
while (q --) {
int l, r, x;
scanf("%d %d %d", &l, &r, &x);
l --; r --;
if (l <= r) printf("%d\n", query(l, r, x));
else printf("%d\n", query(0, r, query(l, n-1, x)));
}
return 0;
}
Compilation message
sushi.cpp: In member function 'void LazySegmentTree::update_point(int, int, int, int, int)':
sushi.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = s + e >> 1;
| ~~^~~
sushi.cpp: In member function 'void LazySegmentTree::update_range(int, int, int, int, int, int)':
sushi.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = s + e >> 1;
| ~~^~~
sushi.cpp: In member function 'void Bucket::init()':
sushi.cpp:105:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = lo + hi >> 1;
| ~~~^~~~
sushi.cpp: In function 'int main()':
sushi.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
sushi.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | scanf("%d %d %d", &l, &r, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
14936 KB |
Output is correct |
| 2 |
Correct |
43 ms |
14944 KB |
Output is correct |
| 3 |
Runtime error |
46 ms |
29776 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1875 ms |
93912 KB |
Output is correct |
| 2 |
Correct |
1856 ms |
93656 KB |
Output is correct |
| 3 |
Correct |
1449 ms |
95732 KB |
Output is correct |
| 4 |
Correct |
1842 ms |
93504 KB |
Output is correct |
| 5 |
Correct |
1540 ms |
98040 KB |
Output is correct |
| 6 |
Correct |
1838 ms |
96080 KB |
Output is correct |
| 7 |
Correct |
1790 ms |
96420 KB |
Output is correct |
| 8 |
Correct |
1738 ms |
97900 KB |
Output is correct |
| 9 |
Correct |
1379 ms |
98068 KB |
Output is correct |
| 10 |
Correct |
1472 ms |
98500 KB |
Output is correct |
| 11 |
Correct |
1397 ms |
97912 KB |
Output is correct |
| 12 |
Correct |
1578 ms |
97896 KB |
Output is correct |
| 13 |
Correct |
1853 ms |
93440 KB |
Output is correct |
| 14 |
Correct |
1891 ms |
93524 KB |
Output is correct |
| 15 |
Correct |
1446 ms |
95752 KB |
Output is correct |
| 16 |
Correct |
1869 ms |
93888 KB |
Output is correct |
| 17 |
Correct |
1464 ms |
98208 KB |
Output is correct |
| 18 |
Correct |
1811 ms |
96172 KB |
Output is correct |
| 19 |
Correct |
1779 ms |
96556 KB |
Output is correct |
| 20 |
Correct |
1715 ms |
97976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
14936 KB |
Output is correct |
| 2 |
Correct |
43 ms |
14944 KB |
Output is correct |
| 3 |
Runtime error |
46 ms |
29776 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
