Submission #284377

#	Time	Username	Problem	Language	Result	Execution time	Memory
284377		Alexa2001	Sushi (JOI16_sushi)	C++17	100 / 100	6610 ms	80228 KiB

sushi

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 4e5 + 5;
const int B = 650;

priority_queue<int, vector<int>, greater<int>> op[Nmax / B + 5];
priority_queue<int> val[Nmax / B + 5];

int n, q, m;
int a[Nmax];


void init()
{
    int i;
    for(i=0; i<n; ++i)
        val[i / B].push(a[i]);
}

int query1(int x, int y, int w)
{
    y = min(y, n-1);

    int i, buc = x/B;

    for(i=buc*B; i<(buc+1)*B && i<n; ++i)
    {
        op[buc].push(a[i]);
        a[i] = op[buc].top();
        op[buc].pop();
    }

    while(!op[buc].empty()) op[buc].pop();
    while(!val[buc].empty()) val[buc].pop();

    for(i=x; i<=y; ++i)
        if(a[i] > w) swap(a[i], w);

    for(i=buc*B; i<(buc+1)*B && i < n; ++i)
        val[buc].push(a[i]);

    return w;
}

int query2(int buc, int x)
{
    op[buc].push(x);
    val[buc].push(x);
    x = val[buc].top();
    val[buc].pop();
    return x;
}

int query(int x, int y, int val)
{
    if(x > y)
        return query(0, y, query(x, n-1, val));

    if(x/B == y/B) return query1(x, y, val);

    if(x%B!=0) val = query1(x, x/B*B + B - 1, val);
        else val = query2(x/B, val);

    for(int i = x/B + 1; i < y/B; ++i)
        val = query2(i, val);

    if(y%B==B-1 || y==n-1) val = query2(y/B, val);
        else val = query1(y/B*B, y, val);

    return val;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> q;

    int i;
    for(i=0; i<n; ++i) cin >> a[i];

    m = (n-1) / B + 1;

    init();

    while(q--)
    {
        int x, y, val;
        cin >> x >> y >> val;
        --x; --y;
        cout << query(x, y, val) << '\n';
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80