oj.uz

답안 #848971

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848971 2023-09-13T19:02:19 Z mickey080929 Sushi (JOI16_sushi) C++17
15 / 100
 1787 ms 92992 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define szz(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 LazySegTree {
public:
    void build(int _n) {
        n = _n;
        lg = Log2(n);
        sz = (1 << lg);
        tree.resize(sz << 1);
        fill(tree.begin(), tree.end(), inf);
        lazy.resize(sz);
        fill(lazy.begin(), lazy.end(), 0);
    }
    void Set(int i, int val) { tree[--i | sz] = val; }
    void Init() { for (int i = sz - 1; i; i--) Pull(i); }
    void Update(int l, int r, int f) {
        --l |= sz, --r |= sz;
        for (int i = lg; i; i--) {
            if (l >> i << i != l) Push(l >> i);
            if (r + 1 >> i << i != r + 1) Push(r >> i);
        }
        for (int L = l, R = r; L <= R; L >>= 1, R >>= 1) {
            if (L & 1) Apply(L++, f);
            if (~R & 1) Apply(R--, f);
        }
        for (int i = 1; i <= lg; i++) {
            if (l >> i << i != l) Pull(l >> i);
            if (r + 1 >> i << i != r + 1) Pull(r >> i);
        }
    }
    int Getmin() { return tree[1]; }
private:
    int n, lg, sz;
    vector<int> tree; vector<int> lazy;
    static int Log2(int n) {
        int ret = 0;
        while (n > 1 << ret) ret++;
        return ret;
    }
    void Apply(int i, int f) {
        tree[i] += f;
        if (i < sz) lazy[i] += f;
    }
    void Push(int i) {
        Apply(i << 1, lazy[i]);
        Apply(i << 1 | 1, lazy[i]);
        lazy[i] = 0;
    }
    void Pull(int i) {
        tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
    }
};

struct Bucket{
    LazySegTree seg;
    priority_queue<int> pq;
    vector<int> queries;
    vector<int> a;
    vector<int> use;
    vector<int> nxt;
    Bucket() { seg.build(B); }
    void init() {
        pq = priority_queue<int>(a.begin(), a.end());
        use.clear();
        int cur = 0;
        for (int i=0; i<szz(a); i++) {
            if (cur <= a[i]) {
                cur = a[i];
                use.push_back(i);
            }
        }
        nxt.clear();
        nxt.resize(szz(use));
        cur = 0;
        for (int i=0; i<szz(use); i++) {
            int r = szz(a);
            if (i + 1 < szz(use)) r = use[i+1];
            if (use[i] + 1 >= r) {
                nxt[i] = cur;
                seg.Set(i+1, inf);
                continue;
            }
            int idx = max_element(a.begin()+use[i]+1, a.begin()+r) - a.begin();
            if (cur >= a[idx]) {
                nxt[i] = cur;
                seg.Set(i+1, inf);
                continue;
            }
            cur = a[idx];
            nxt[i] = cur;
            int lo = 0, hi = szz(use) - 1;
            while (lo < hi) {
                int mid = lo + hi >> 1;
                if (a[mid] <= cur) lo = mid + 1;
                else hi = mid;
            }
            seg.Set(i+1, i+1 - lo);
        }
        seg.Init();
    }
    void apply() {
        vector<int> t;
        for (auto &x : queries) {
            int idx = lower_bound(nxt.begin(), nxt.end(), x) - nxt.begin();
            seg.Update(idx+1, szz(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<szz(use); i++) a[use[i]] = t[i];
                t.clear();
                int cur = x;
                for (int i=0; i<szz(a); i++) if (cur <= a[i]) swap(cur, a[i]);
                int before = szz(use);
                init();
                assert(before < szz(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<szz(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 LazySegTree::Update(int, int, int)':
sushi.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |             if (r + 1 >> i << i != r + 1) Push(r >> i);
      |                 ~~^~~
sushi.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |             if (r + 1 >> i << i != r + 1) Pull(r >> i);
      |                 ~~^~~
sushi.cpp: In member function 'void Bucket::init()':
sushi.cpp:108:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
sushi.cpp: In function 'int main()':
sushi.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sushi.cpp:186:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 16476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1757 ms 88312 KB Output is correct
2 Correct 1733 ms 88140 KB Output is correct
3 Correct 1227 ms 90592 KB Output is correct
4 Correct 1787 ms 88304 KB Output is correct
5 Correct 1283 ms 92776 KB Output is correct
6 Correct 1786 ms 90732 KB Output is correct
7 Correct 1765 ms 90976 KB Output is correct
8 Correct 1712 ms 92596 KB Output is correct
9 Correct 1193 ms 92884 KB Output is correct
10 Correct 1341 ms 92992 KB Output is correct
11 Correct 1211 ms 92664 KB Output is correct
12 Correct 1368 ms 92728 KB Output is correct
13 Correct 1719 ms 88552 KB Output is correct
14 Correct 1757 ms 88340 KB Output is correct
15 Correct 1275 ms 90452 KB Output is correct
16 Correct 1707 ms 88444 KB Output is correct
17 Correct 1275 ms 92888 KB Output is correct
18 Correct 1751 ms 91036 KB Output is correct
19 Correct 1714 ms 90976 KB Output is correct
20 Correct 1689 ms 92936 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 16476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -