oj.uz

Submission #848919

# Submission time Handle Problem Language Result Execution time Memory
848919 2023-09-13T17:41:34 Z mickey080929 Sushi (JOI16_sushi) C++17
20 / 100
 2047 ms 100608 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], 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[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:99:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
sushi.cpp: In function 'int main()':
sushi.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sushi.cpp:175:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14940 KB Output is correct
2 Correct 49 ms 14940 KB Output is correct
3 Correct 47 ms 14936 KB Output is correct
4 Correct 49 ms 14936 KB Output is correct
5 Correct 42 ms 14960 KB Output is correct
6 Correct 50 ms 14936 KB Output is correct
7 Correct 58 ms 14960 KB Output is correct
8 Correct 54 ms 14976 KB Output is correct
9 Correct 49 ms 14936 KB Output is correct
10 Correct 48 ms 15184 KB Output is correct
11 Correct 123 ms 15020 KB Output is correct
12 Correct 122 ms 15008 KB Output is correct
13 Correct 124 ms 15008 KB Output is correct
14 Correct 75 ms 14936 KB Output is correct
15 Correct 74 ms 14936 KB Output is correct
16 Correct 18 ms 14936 KB Output is correct
17 Correct 2 ms 14888 KB Output is correct
18 Correct 2 ms 14684 KB Output is correct
19 Correct 2 ms 14680 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 1870 ms 93656 KB Output is correct
2 Correct 1854 ms 93520 KB Output is correct
3 Correct 1305 ms 95700 KB Output is correct
4 Correct 1856 ms 93924 KB Output is correct
5 Correct 1383 ms 98184 KB Output is correct
6 Correct 1729 ms 95936 KB Output is correct
7 Correct 1705 ms 96312 KB Output is correct
8 Correct 1712 ms 97760 KB Output is correct
9 Correct 1354 ms 97836 KB Output is correct
10 Correct 1486 ms 98176 KB Output is correct
11 Correct 1350 ms 98532 KB Output is correct
12 Correct 1613 ms 99928 KB Output is correct
13 Correct 2032 ms 95800 KB Output is correct
14 Correct 2013 ms 95428 KB Output is correct
15 Correct 1544 ms 96476 KB Output is correct
16 Correct 2047 ms 96568 KB Output is correct
17 Correct 1532 ms 100568 KB Output is correct
18 Correct 1779 ms 98864 KB Output is correct
19 Correct 1823 ms 99052 KB Output is correct
20 Correct 1766 ms 100608 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14940 KB Output is correct
2 Correct 49 ms 14940 KB Output is correct
3 Correct 47 ms 14936 KB Output is correct
4 Correct 49 ms 14936 KB Output is correct
5 Correct 42 ms 14960 KB Output is correct
6 Correct 50 ms 14936 KB Output is correct
7 Correct 58 ms 14960 KB Output is correct
8 Correct 54 ms 14976 KB Output is correct
9 Correct 49 ms 14936 KB Output is correct
10 Correct 48 ms 15184 KB Output is correct
11 Correct 123 ms 15020 KB Output is correct
12 Correct 122 ms 15008 KB Output is correct
13 Correct 124 ms 15008 KB Output is correct
14 Correct 75 ms 14936 KB Output is correct
15 Correct 74 ms 14936 KB Output is correct
16 Correct 18 ms 14936 KB Output is correct
17 Correct 2 ms 14888 KB Output is correct
18 Correct 2 ms 14684 KB Output is correct
19 Correct 2 ms 14680 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 1870 ms 93656 KB Output is correct
24 Correct 1854 ms 93520 KB Output is correct
25 Correct 1305 ms 95700 KB Output is correct
26 Correct 1856 ms 93924 KB Output is correct
27 Correct 1383 ms 98184 KB Output is correct
28 Correct 1729 ms 95936 KB Output is correct
29 Correct 1705 ms 96312 KB Output is correct
30 Correct 1712 ms 97760 KB Output is correct
31 Correct 1354 ms 97836 KB Output is correct
32 Correct 1486 ms 98176 KB Output is correct
33 Correct 1350 ms 98532 KB Output is correct
34 Correct 1613 ms 99928 KB Output is correct
35 Correct 2032 ms 95800 KB Output is correct
36 Correct 2013 ms 95428 KB Output is correct
37 Correct 1544 ms 96476 KB Output is correct
38 Correct 2047 ms 96568 KB Output is correct
39 Correct 1532 ms 100568 KB Output is correct
40 Correct 1779 ms 98864 KB Output is correct
41 Correct 1823 ms 99052 KB Output is correct
42 Correct 1766 ms 100608 KB Output is correct
43 Runtime error 119 ms 48468 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -