oj.uz

답안 #595795

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

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int B = 632;
    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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 600 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6672 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 600 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -