Submission #848971

#	Time	Username	Problem	Language	Result	Execution time	Memory
848971		mickey080929	Sushi (JOI16_sushi)	C++17	15 / 100	1787 ms	92992 KiB

sushi

#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 (stderr)

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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80