oj.uz

Submission #734768

# Submission time Handle Problem Language Result Execution time Memory
734768 2023-05-03T04:49:11 Z abcvuitunggio Sushi (JOI16_sushi) C++17
0 / 100
 1316 ms 75028 KB 
#include <bits/stdc++.h>
using namespace std;
const int sz=632;
priority_queue <int> q[400000/sz+1];
priority_queue <int, vector <int>, greater <int>> p[400000/sz+1];
int n,x[400000],cur;
void reset(int i){
    for (int j=i*sz;j<min(i*sz+sz,n);j++){
        p[i].push(x[j]);
        x[j]=p[i].top();
        p[i].pop();
    }
    p[i]=priority_queue <int, vector <int>, greater <int>>();
    q[i]=priority_queue <int>();
}
void f(int l, int r){
    int b=l/sz,e=r/sz;
    reset(b);
    for (int i=l;i<min(b*sz+sz,r+1);i++)
        if (x[i]>cur)
            swap(x[i],cur);
    for (int i=b*sz;i<min(b*sz+sz,n);i++)
        q[b].push(x[i]);
    if (b==e)
        return;
    for (int i=b+1;i<e;i++){
        p[i].push(cur);
        q[i].push(cur);
        cur=q[i].top();
        q[i].pop();
    }
    reset(e);
    for (int i=e*sz;i<=r;i++)
        if (x[i]>cur)
            swap(x[i],cur);
    for (int i=e*sz;i<min(e*sz+sz,n);i++)
        q[e].push(x[i]);
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    int q,s,t,p;
    cin >> n >> q;
    for (int i=0;i<n;i++)
        cin >> x[i];
    while (q--){
        cin >> s >> t >> p;
        s--;
        t--;
        cur=p;
        if (s<=t)
            f(s,t);
        else{
            f(s,n-1);
            f(0,t);
        }
        cout << cur << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 340 KB Output is correct
2 Incorrect 62 ms 400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1316 ms 75028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 340 KB Output is correct
2 Incorrect 62 ms 400 KB Output isn't correct
3 Halted 0 ms 0 KB -