oj.uz

답안 #595800

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

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int B = 6320;
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        num[i / B].insert(a[i]);
    }
    while(q--){
        int x, y, k; cin >> x >> y >> k; --x, --y;
        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){
                    auto p = num[bp].lower_bound(a[i]);
                    num[bp].erase(p);

                    que[bp].insert(a[i]);
                    a[i] = *(que[bp].begin());
                    que[bp].erase(que[bp].begin());

                    num[bp].insert(a[i]);
                }
                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 = *num[i].begin();
                    num[i].erase(num[i].begin());
                }
                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) 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:40:30: warning: unused variable 'yr' [-Wunused-variable]
   40 |             int yl = yb * B, yr = min(n, yl + B);
      |                              ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2380 ms 2380 KB Output is correct
2 Correct 2371 ms 2472 KB Output is correct
3 Correct 2330 ms 2352 KB Output is correct
4 Correct 2329 ms 2352 KB Output is correct
5 Correct 2315 ms 2336 KB Output is correct
6 Correct 2331 ms 2340 KB Output is correct
7 Correct 1943 ms 2316 KB Output is correct
8 Correct 1979 ms 2324 KB Output is correct
9 Correct 2446 ms 2364 KB Output is correct
10 Correct 2410 ms 2352 KB Output is correct
11 Correct 2361 ms 2364 KB Output is correct
12 Correct 2350 ms 2352 KB Output is correct
13 Correct 2146 ms 2352 KB Output is correct
14 Correct 3151 ms 2360 KB Output is correct
15 Correct 3129 ms 2356 KB Output is correct
16 Correct 1603 ms 2344 KB Output is correct
17 Correct 2 ms 2132 KB Output is correct
18 Correct 1 ms 2132 KB Output is correct
19 Correct 1 ms 2116 KB Output is correct
20 Correct 2 ms 2204 KB Output is correct
21 Correct 2 ms 2132 KB Output is correct
22 Correct 2 ms 2132 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2380 ms 2380 KB Output is correct
2 Correct 2371 ms 2472 KB Output is correct
3 Correct 2330 ms 2352 KB Output is correct
4 Correct 2329 ms 2352 KB Output is correct
5 Correct 2315 ms 2336 KB Output is correct
6 Correct 2331 ms 2340 KB Output is correct
7 Correct 1943 ms 2316 KB Output is correct
8 Correct 1979 ms 2324 KB Output is correct
9 Correct 2446 ms 2364 KB Output is correct
10 Correct 2410 ms 2352 KB Output is correct
11 Correct 2361 ms 2364 KB Output is correct
12 Correct 2350 ms 2352 KB Output is correct
13 Correct 2146 ms 2352 KB Output is correct
14 Correct 3151 ms 2360 KB Output is correct
15 Correct 3129 ms 2356 KB Output is correct
16 Correct 1603 ms 2344 KB Output is correct
17 Correct 2 ms 2132 KB Output is correct
18 Correct 1 ms 2132 KB Output is correct
19 Correct 1 ms 2116 KB Output is correct
20 Correct 2 ms 2204 KB Output is correct
21 Correct 2 ms 2132 KB Output is correct
22 Correct 2 ms 2132 KB Output is correct
23 Execution timed out 12058 ms 43704 KB Time limit exceeded
24 Halted 0 ms 0 KB -