답안 #848938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848938 2023-09-13T18:09:38 Z mickey080929 Sushi (JOI16_sushi) C++17
15 / 100
1942 ms 98004 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[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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 14944 KB Output is correct
2 Correct 44 ms 14936 KB Output is correct
3 Runtime error 47 ms 29776 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1881 ms 93536 KB Output is correct
2 Correct 1821 ms 93624 KB Output is correct
3 Correct 1351 ms 95780 KB Output is correct
4 Correct 1848 ms 93640 KB Output is correct
5 Correct 1486 ms 97956 KB Output is correct
6 Correct 1754 ms 95964 KB Output is correct
7 Correct 1785 ms 96364 KB Output is correct
8 Correct 1748 ms 97756 KB Output is correct
9 Correct 1346 ms 97812 KB Output is correct
10 Correct 1422 ms 97984 KB Output is correct
11 Correct 1318 ms 98000 KB Output is correct
12 Correct 1536 ms 97928 KB Output is correct
13 Correct 1816 ms 93544 KB Output is correct
14 Correct 1942 ms 93520 KB Output is correct
15 Correct 1464 ms 95696 KB Output is correct
16 Correct 1783 ms 93812 KB Output is correct
17 Correct 1403 ms 98004 KB Output is correct
18 Correct 1804 ms 96400 KB Output is correct
19 Correct 1891 ms 96556 KB Output is correct
20 Correct 1774 ms 97832 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 14944 KB Output is correct
2 Correct 44 ms 14936 KB Output is correct
3 Runtime error 47 ms 29776 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -