oj.uz

답안 #595845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595845 2022-07-14T07:37:35 Z 이동현(#8445) Sushi (JOI16_sushi) C++17
5 / 100
 12000 ms 42120 KB 
#include <bits/stdc++.h>
using namespace std;

const int BS = 1000;
multiset<int> num[BS];
multiset<int> que[BS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int B = 10000;
    int n, q; cin >> n >> q;
    //n = 400000, q = 25000;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        //a[i] = i + 1;
        num[i / B].insert(a[i]);
    }
    while(q--){
        int x, y, k; cin >> x >> y >> k; --x, --y;
        //x = 0, y = n - 1, k = q + 30;
        auto sol = [&](int x, int y, int k)->int{
            auto doque = [&](int pos)->void{
                int bp = pos / B;
                int l = bp * B, r = min(n, l + B);
                for(int i = l; i < r; ++i){
                    que[bp].insert(a[i]);
                    a[i] = *(que[bp].begin());
                    que[bp].erase(que[bp].begin());
                }
                que[bp].clear();
            };
            doque(x), doque(y);
            int xb = x / B, yb = y / B;
            int xl = xb * B, xr = min(n, xl + B);
            int yl = yb * B, yr = min(n, yl + B);

            if(xb < yb){
                for(int i = x; i < xr; ++i){
                    if(a[i] > k){
                        auto p = num[xb].lower_bound(a[i]);
                        num[xb].erase(p);
                        swap(a[i], k);
                        num[xb].insert(a[i]);
                    }
                }
                for(int i = xb + 1; i < yb; ++i){
                    que[i].insert(k);
                    num[i].insert(k);
                    k = *prev(num[i].end());
                    assert((int)num[i].size() > 0);
                    num[i].erase(--num[i].end());
                }
                for(int i = yl; i <= y; ++i){
                    if(a[i] > k){
                        auto p = num[yb].lower_bound(a[i]);
                        num[yb].erase(p);
                        swap(a[i], k);
                        num[yb].insert(a[i]);
                    }
                }
            }
            else{
                for(int i = x; i <= y; ++i){
                    if(a[i] > k){
                        auto p = num[xb].lower_bound(a[i]);
                        num[xb].erase(p);
                        swap(a[i], k);
                        num[xb].insert(a[i]);
                    }
                }
            }
            return k;
        };
        //if(x <= y) sol(x, y, k);
        //else sol(0, y, sol(x, n - 1, k));
        if(x <= y) cout << sol(x, y, k) << '\n';
        else cout << sol(0, y, sol(x, n - 1, k)) << '\n';
    }
    return 0;
}

Compilation message

sushi.cpp: In lambda function:
sushi.cpp:37:30: warning: unused variable 'yr' [-Wunused-variable]
   37 |             int yl = yb * B, yr = min(n, yl + B);
      |                              ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 628 KB Output is correct
2 Correct 403 ms 516 KB Output is correct
3 Correct 370 ms 504 KB Output is correct
4 Correct 392 ms 512 KB Output is correct
5 Correct 374 ms 496 KB Output is correct
6 Correct 391 ms 496 KB Output is correct
7 Correct 413 ms 504 KB Output is correct
8 Correct 408 ms 500 KB Output is correct
9 Correct 405 ms 512 KB Output is correct
10 Correct 373 ms 512 KB Output is correct
11 Correct 464 ms 500 KB Output is correct
12 Correct 514 ms 516 KB Output is correct
13 Correct 456 ms 504 KB Output is correct
14 Correct 539 ms 504 KB Output is correct
15 Correct 521 ms 512 KB Output is correct
16 Correct 275 ms 496 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 12067 ms 42120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 628 KB Output is correct
2 Correct 403 ms 516 KB Output is correct
3 Correct 370 ms 504 KB Output is correct
4 Correct 392 ms 512 KB Output is correct
5 Correct 374 ms 496 KB Output is correct
6 Correct 391 ms 496 KB Output is correct
7 Correct 413 ms 504 KB Output is correct
8 Correct 408 ms 500 KB Output is correct
9 Correct 405 ms 512 KB Output is correct
10 Correct 373 ms 512 KB Output is correct
11 Correct 464 ms 500 KB Output is correct
12 Correct 514 ms 516 KB Output is correct
13 Correct 456 ms 504 KB Output is correct
14 Correct 539 ms 504 KB Output is correct
15 Correct 521 ms 512 KB Output is correct
16 Correct 275 ms 496 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Execution timed out 12067 ms 42120 KB Time limit exceeded
24 Halted 0 ms 0 KB -