oj.uz

Submission #848978

# Submission time Handle Problem Language Result Execution time Memory
848978 2023-09-13T19:10:31 Z mickey080929 Sushi (JOI16_sushi) C++17
100 / 100
 3659 ms 102644 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 idx = max_element(a.begin()+use[i]+1, a.begin()+r) - a.begin();
            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[use[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());
                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]);
                int before = sz(use);
                init();
                assert(before < sz(use));
            } 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:99:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
sushi.cpp: In function 'int main()':
sushi.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:168:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sushi.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15096 KB Output is correct
2 Correct 41 ms 14936 KB Output is correct
3 Correct 58 ms 14944 KB Output is correct
4 Correct 46 ms 14948 KB Output is correct
5 Correct 40 ms 15196 KB Output is correct
6 Correct 41 ms 14940 KB Output is correct
7 Correct 58 ms 14940 KB Output is correct
8 Correct 55 ms 14944 KB Output is correct
9 Correct 42 ms 14940 KB Output is correct
10 Correct 40 ms 14936 KB Output is correct
11 Correct 60 ms 14936 KB Output is correct
12 Correct 62 ms 14956 KB Output is correct
13 Correct 65 ms 14936 KB Output is correct
14 Correct 57 ms 14936 KB Output is correct
15 Correct 55 ms 14936 KB Output is correct
16 Correct 19 ms 14936 KB Output is correct
17 Correct 2 ms 14680 KB Output is correct
18 Correct 2 ms 14680 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 2 ms 14680 KB Output is correct
21 Correct 2 ms 14680 KB Output is correct
22 Correct 2 ms 14680 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1844 ms 93464 KB Output is correct
2 Correct 1834 ms 93540 KB Output is correct
3 Correct 1318 ms 95668 KB Output is correct
4 Correct 1869 ms 93488 KB Output is correct
5 Correct 1504 ms 98128 KB Output is correct
6 Correct 1809 ms 96220 KB Output is correct
7 Correct 1767 ms 96340 KB Output is correct
8 Correct 1768 ms 97988 KB Output is correct
9 Correct 1289 ms 98004 KB Output is correct
10 Correct 1390 ms 97988 KB Output is correct
11 Correct 1335 ms 97864 KB Output is correct
12 Correct 1499 ms 98104 KB Output is correct
13 Correct 1831 ms 93540 KB Output is correct
14 Correct 1831 ms 93712 KB Output is correct
15 Correct 1447 ms 95824 KB Output is correct
16 Correct 1869 ms 93804 KB Output is correct
17 Correct 1506 ms 98128 KB Output is correct
18 Correct 1871 ms 96164 KB Output is correct
19 Correct 1859 ms 96244 KB Output is correct
20 Correct 1755 ms 97852 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15096 KB Output is correct
2 Correct 41 ms 14936 KB Output is correct
3 Correct 58 ms 14944 KB Output is correct
4 Correct 46 ms 14948 KB Output is correct
5 Correct 40 ms 15196 KB Output is correct
6 Correct 41 ms 14940 KB Output is correct
7 Correct 58 ms 14940 KB Output is correct
8 Correct 55 ms 14944 KB Output is correct
9 Correct 42 ms 14940 KB Output is correct
10 Correct 40 ms 14936 KB Output is correct
11 Correct 60 ms 14936 KB Output is correct
12 Correct 62 ms 14956 KB Output is correct
13 Correct 65 ms 14936 KB Output is correct
14 Correct 57 ms 14936 KB Output is correct
15 Correct 55 ms 14936 KB Output is correct
16 Correct 19 ms 14936 KB Output is correct
17 Correct 2 ms 14680 KB Output is correct
18 Correct 2 ms 14680 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 2 ms 14680 KB Output is correct
21 Correct 2 ms 14680 KB Output is correct
22 Correct 2 ms 14680 KB Output is correct
23 Correct 1844 ms 93464 KB Output is correct
24 Correct 1834 ms 93540 KB Output is correct
25 Correct 1318 ms 95668 KB Output is correct
26 Correct 1869 ms 93488 KB Output is correct
27 Correct 1504 ms 98128 KB Output is correct
28 Correct 1809 ms 96220 KB Output is correct
29 Correct 1767 ms 96340 KB Output is correct
30 Correct 1768 ms 97988 KB Output is correct
31 Correct 1289 ms 98004 KB Output is correct
32 Correct 1390 ms 97988 KB Output is correct
33 Correct 1335 ms 97864 KB Output is correct
34 Correct 1499 ms 98104 KB Output is correct
35 Correct 1831 ms 93540 KB Output is correct
36 Correct 1831 ms 93712 KB Output is correct
37 Correct 1447 ms 95824 KB Output is correct
38 Correct 1869 ms 93804 KB Output is correct
39 Correct 1506 ms 98128 KB Output is correct
40 Correct 1871 ms 96164 KB Output is correct
41 Correct 1859 ms 96244 KB Output is correct
42 Correct 1755 ms 97852 KB Output is correct
43 Correct 1765 ms 25344 KB Output is correct
44 Correct 1769 ms 29080 KB Output is correct
45 Correct 2032 ms 28916 KB Output is correct
46 Correct 1786 ms 29096 KB Output is correct
47 Correct 1746 ms 29408 KB Output is correct
48 Correct 2524 ms 35004 KB Output is correct
49 Correct 2779 ms 34084 KB Output is correct
50 Correct 2693 ms 34368 KB Output is correct
51 Correct 2637 ms 34428 KB Output is correct
52 Correct 2498 ms 35576 KB Output is correct
53 Correct 2421 ms 35528 KB Output is correct
54 Correct 3283 ms 40240 KB Output is correct
55 Correct 3659 ms 40080 KB Output is correct
56 Correct 3574 ms 40024 KB Output is correct
57 Correct 3455 ms 40772 KB Output is correct
58 Correct 1879 ms 36004 KB Output is correct
59 Correct 1942 ms 36472 KB Output is correct
60 Correct 1321 ms 102644 KB Output is correct
61 Correct 1597 ms 100800 KB Output is correct
62 Correct 1578 ms 101200 KB Output is correct
63 Correct 1599 ms 102288 KB Output is correct
64 Correct 1639 ms 30752 KB Output is correct
65 Correct 984 ms 66416 KB Output is correct
66 Correct 966 ms 66420 KB Output is correct
67 Correct 2874 ms 90508 KB Output is correct
68 Correct 3143 ms 89368 KB Output is correct
69 Correct 3190 ms 89696 KB Output is correct
70 Correct 3001 ms 90080 KB Output is correct