oj.uz

Submission #203105

# Submission time Handle Problem Language Result Execution time Memory
203105 2020-02-19T11:31:53 Z mhy908 Sushi (JOI16_sushi) C++14
100 / 100
 7427 ms 82384 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, q, sq;
int arr[400010];
priority_queue<int> pq[1010];
vector<int> temp[1010];
int query2(int a, int b, int c){
    if(a>b)return c;
    priority_queue<int, vector<int>, greater<int> > tpq;
    int buca=(a-1)/sq;
    for(auto i:temp[buca])tpq.push(i);
    temp[buca].clear();
    for(int i=buca*sq+1; i<=(buca+1)*sq; i++){
        tpq.push(arr[i]);
        arr[i]=tpq.top();
        tpq.pop();
    }
    for(int i=a; i<=b; i++){
        if(c<arr[i])swap(c, arr[i]);
    }
    while(!pq[buca].empty())pq[buca].pop();
    for(int i=buca*sq+1; i<=(buca+1)*sq; i++)pq[buca].push(arr[i]);
    return c;
}
int query(int a, int b, int c){
    int buca=(a-1)/sq+1, bucb=(b-1)/sq;
    if(buca>bucb)return query2(a, b, c);
    c=query2(a, buca*sq, c);
    for(int i=buca; i<bucb; i++){
        temp[i].pb(c);
        pq[i].push(c);
        c=pq[i].top();
        pq[i].pop();
    }
    c=query2(bucb*sq+1, b, c);
    return c;
}
int main(){
    scanf("%d %d", &n, &q);
    sq=sqrt(n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        pq[(i-1)/sq].push(arr[i]);
    }
    for(int i=1; i<=q; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(a<=b)printf("%d\n", query(a, b, c));
        else printf("%d\n", query(1, b, query(a, n, c)));
    }
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 504 KB Output is correct
2 Correct 24 ms 504 KB Output is correct
3 Correct 24 ms 508 KB Output is correct
4 Correct 25 ms 504 KB Output is correct
5 Correct 24 ms 500 KB Output is correct
6 Correct 24 ms 504 KB Output is correct
7 Correct 17 ms 504 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 24 ms 504 KB Output is correct
10 Correct 25 ms 504 KB Output is correct
11 Correct 25 ms 504 KB Output is correct
12 Correct 25 ms 504 KB Output is correct
13 Correct 27 ms 504 KB Output is correct
14 Correct 28 ms 632 KB Output is correct
15 Correct 28 ms 508 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3571 ms 78028 KB Output is correct
2 Correct 3554 ms 80676 KB Output is correct
3 Correct 2028 ms 78664 KB Output is correct
4 Correct 3524 ms 82216 KB Output is correct
5 Correct 2832 ms 82120 KB Output is correct
6 Correct 3687 ms 82368 KB Output is correct
7 Correct 3638 ms 82188 KB Output is correct
8 Correct 3616 ms 82120 KB Output is correct
9 Correct 1750 ms 78428 KB Output is correct
10 Correct 2835 ms 80964 KB Output is correct
11 Correct 1719 ms 78536 KB Output is correct
12 Correct 2825 ms 80792 KB Output is correct
13 Correct 3555 ms 82024 KB Output is correct
14 Correct 3522 ms 80832 KB Output is correct
15 Correct 1992 ms 78664 KB Output is correct
16 Correct 3562 ms 82164 KB Output is correct
17 Correct 2801 ms 82168 KB Output is correct
18 Correct 3577 ms 82268 KB Output is correct
19 Correct 3724 ms 82068 KB Output is correct
20 Correct 3685 ms 82240 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 504 KB Output is correct
2 Correct 24 ms 504 KB Output is correct
3 Correct 24 ms 508 KB Output is correct
4 Correct 25 ms 504 KB Output is correct
5 Correct 24 ms 500 KB Output is correct
6 Correct 24 ms 504 KB Output is correct
7 Correct 17 ms 504 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 24 ms 504 KB Output is correct
10 Correct 25 ms 504 KB Output is correct
11 Correct 25 ms 504 KB Output is correct
12 Correct 25 ms 504 KB Output is correct
13 Correct 27 ms 504 KB Output is correct
14 Correct 28 ms 632 KB Output is correct
15 Correct 28 ms 508 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 3571 ms 78028 KB Output is correct
24 Correct 3554 ms 80676 KB Output is correct
25 Correct 2028 ms 78664 KB Output is correct
26 Correct 3524 ms 82216 KB Output is correct
27 Correct 2832 ms 82120 KB Output is correct
28 Correct 3687 ms 82368 KB Output is correct
29 Correct 3638 ms 82188 KB Output is correct
30 Correct 3616 ms 82120 KB Output is correct
31 Correct 1750 ms 78428 KB Output is correct
32 Correct 2835 ms 80964 KB Output is correct
33 Correct 1719 ms 78536 KB Output is correct
34 Correct 2825 ms 80792 KB Output is correct
35 Correct 3555 ms 82024 KB Output is correct
36 Correct 3522 ms 80832 KB Output is correct
37 Correct 1992 ms 78664 KB Output is correct
38 Correct 3562 ms 82164 KB Output is correct
39 Correct 2801 ms 82168 KB Output is correct
40 Correct 3577 ms 82268 KB Output is correct
41 Correct 3724 ms 82068 KB Output is correct
42 Correct 3685 ms 82240 KB Output is correct
43 Correct 5500 ms 12628 KB Output is correct
44 Correct 5476 ms 12408 KB Output is correct
45 Correct 3163 ms 8824 KB Output is correct
46 Correct 5487 ms 12400 KB Output is correct
47 Correct 5487 ms 12436 KB Output is correct
48 Correct 5505 ms 12536 KB Output is correct
49 Correct 6110 ms 12600 KB Output is correct
50 Correct 6013 ms 12488 KB Output is correct
51 Correct 6035 ms 12408 KB Output is correct
52 Correct 6920 ms 19528 KB Output is correct
53 Correct 6750 ms 19068 KB Output is correct
54 Correct 6561 ms 19140 KB Output is correct
55 Correct 7427 ms 18952 KB Output is correct
56 Correct 7315 ms 18936 KB Output is correct
57 Correct 7194 ms 18916 KB Output is correct
58 Correct 3856 ms 14460 KB Output is correct
59 Correct 3933 ms 14328 KB Output is correct
60 Correct 2989 ms 82384 KB Output is correct
61 Correct 3633 ms 82340 KB Output is correct
62 Correct 3602 ms 82200 KB Output is correct
63 Correct 3609 ms 82184 KB Output is correct
64 Correct 2207 ms 8696 KB Output is correct
65 Correct 2443 ms 45176 KB Output is correct
66 Correct 2421 ms 45204 KB Output is correct
67 Correct 5246 ms 69300 KB Output is correct
68 Correct 6114 ms 69148 KB Output is correct
69 Correct 6089 ms 69392 KB Output is correct
70 Correct 5974 ms 69256 KB Output is correct