oj.uz

Submission #284377

# Submission time Handle Problem Language Result Execution time Memory
284377 2020-08-27T09:51:44 Z Alexa2001 Sushi (JOI16_sushi) C++17
100 / 100
 6610 ms 80228 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 512 KB Output is correct
2 Correct 207 ms 632 KB Output is correct
3 Correct 213 ms 632 KB Output is correct
4 Correct 206 ms 512 KB Output is correct
5 Correct 207 ms 504 KB Output is correct
6 Correct 209 ms 620 KB Output is correct
7 Correct 95 ms 384 KB Output is correct
8 Correct 96 ms 384 KB Output is correct
9 Correct 208 ms 632 KB Output is correct
10 Correct 208 ms 512 KB Output is correct
11 Correct 202 ms 512 KB Output is correct
12 Correct 203 ms 632 KB Output is correct
13 Correct 213 ms 760 KB Output is correct
14 Correct 230 ms 504 KB Output is correct
15 Correct 237 ms 512 KB Output is correct
16 Correct 108 ms 512 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3032 ms 79948 KB Output is correct
2 Correct 3039 ms 78580 KB Output is correct
3 Correct 1609 ms 76516 KB Output is correct
4 Correct 3130 ms 80056 KB Output is correct
5 Correct 2433 ms 80096 KB Output is correct
6 Correct 2887 ms 80036 KB Output is correct
7 Correct 2942 ms 80104 KB Output is correct
8 Correct 2891 ms 80108 KB Output is correct
9 Correct 1369 ms 76488 KB Output is correct
10 Correct 2409 ms 78464 KB Output is correct
11 Correct 1363 ms 76512 KB Output is correct
12 Correct 2429 ms 78664 KB Output is correct
13 Correct 3093 ms 79932 KB Output is correct
14 Correct 3008 ms 78732 KB Output is correct
15 Correct 1579 ms 76640 KB Output is correct
16 Correct 3073 ms 80228 KB Output is correct
17 Correct 2501 ms 79852 KB Output is correct
18 Correct 2880 ms 80020 KB Output is correct
19 Correct 2880 ms 80196 KB Output is correct
20 Correct 2895 ms 80056 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 512 KB Output is correct
2 Correct 207 ms 632 KB Output is correct
3 Correct 213 ms 632 KB Output is correct
4 Correct 206 ms 512 KB Output is correct
5 Correct 207 ms 504 KB Output is correct
6 Correct 209 ms 620 KB Output is correct
7 Correct 95 ms 384 KB Output is correct
8 Correct 96 ms 384 KB Output is correct
9 Correct 208 ms 632 KB Output is correct
10 Correct 208 ms 512 KB Output is correct
11 Correct 202 ms 512 KB Output is correct
12 Correct 203 ms 632 KB Output is correct
13 Correct 213 ms 760 KB Output is correct
14 Correct 230 ms 504 KB Output is correct
15 Correct 237 ms 512 KB Output is correct
16 Correct 108 ms 512 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 3032 ms 79948 KB Output is correct
24 Correct 3039 ms 78580 KB Output is correct
25 Correct 1609 ms 76516 KB Output is correct
26 Correct 3130 ms 80056 KB Output is correct
27 Correct 2433 ms 80096 KB Output is correct
28 Correct 2887 ms 80036 KB Output is correct
29 Correct 2942 ms 80104 KB Output is correct
30 Correct 2891 ms 80108 KB Output is correct
31 Correct 1369 ms 76488 KB Output is correct
32 Correct 2409 ms 78464 KB Output is correct
33 Correct 1363 ms 76512 KB Output is correct
34 Correct 2429 ms 78664 KB Output is correct
35 Correct 3093 ms 79932 KB Output is correct
36 Correct 3008 ms 78732 KB Output is correct
37 Correct 1579 ms 76640 KB Output is correct
38 Correct 3073 ms 80228 KB Output is correct
39 Correct 2501 ms 79852 KB Output is correct
40 Correct 2880 ms 80020 KB Output is correct
41 Correct 2880 ms 80196 KB Output is correct
42 Correct 2895 ms 80056 KB Output is correct
43 Correct 5259 ms 12064 KB Output is correct
44 Correct 5234 ms 12088 KB Output is correct
45 Correct 3120 ms 8848 KB Output is correct
46 Correct 5290 ms 12524 KB Output is correct
47 Correct 5266 ms 12524 KB Output is correct
48 Correct 5454 ms 12144 KB Output is correct
49 Correct 5693 ms 12192 KB Output is correct
50 Correct 5572 ms 12192 KB Output is correct
51 Correct 5513 ms 12112 KB Output is correct
52 Correct 6360 ms 18460 KB Output is correct
53 Correct 6186 ms 17956 KB Output is correct
54 Correct 6244 ms 18476 KB Output is correct
55 Correct 6506 ms 17972 KB Output is correct
56 Correct 6558 ms 18168 KB Output is correct
57 Correct 6610 ms 18168 KB Output is correct
58 Correct 3615 ms 14252 KB Output is correct
59 Correct 3725 ms 14440 KB Output is correct
60 Correct 4177 ms 80088 KB Output is correct
61 Correct 4770 ms 79676 KB Output is correct
62 Correct 4750 ms 79736 KB Output is correct
63 Correct 4834 ms 79816 KB Output is correct
64 Correct 2221 ms 8496 KB Output is correct
65 Correct 2846 ms 43860 KB Output is correct
66 Correct 2888 ms 44008 KB Output is correct
67 Correct 5122 ms 66344 KB Output is correct
68 Correct 5662 ms 66280 KB Output is correct
69 Correct 5709 ms 66424 KB Output is correct
70 Correct 5683 ms 66412 KB Output is correct