oj.uz

Submission #200906

# Submission time Handle Problem Language Result Execution time Memory
200906 2020-02-08T13:30:36 Z gs18115 Sushi (JOI16_sushi) C++14
15 / 100
 3610 ms 77640 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int sz=642;
int n;
int x[400010+sz];
priority_queue<int,vector<int>,less<int> >pq[sz];
priority_queue<int,vector<int>,greater<int> >rn[sz];
inline void init()
{
    for(int i=0;i<n;i++)
        pq[i/sz].ep(x[i]);
    return;
}
inline void app(int g)
{
    if(rn[g].empty())
        return;
    for(int i=g*sz;i<g*sz+sz;i++)
        if(rn[g].top()<x[i])
            rn[g].ep(x[i]),x[i]=rn[g].top(),rn[g].pop();
    while(!rn[g].empty())
        rn[g].pop();
    return;
}
inline void init(int g)
{
    while(!pq[g].empty())
        pq[g].pop();
    for(int i=g*sz;i<g*sz+sz;i++)
        pq[g].ep(x[i]);
    return;
}
inline int solve(int s,int t,int p)
{
    if(t-s<sz)
    {
        for(int i=s;i<t;i++)
            if(p<x[i])
                swap(p,x[i]);
        return p;
    }
    int l=(s+sz-1)/sz;
    int r=t/sz;
    if(s<l*sz)
    {
        app(l-1);
        for(int i=s;i<l*sz;i++)
            if(p<x[i])
                swap(p,x[i]);
        init(l-1);
    }
    for(int i=l;i<r;i++)
    {
        if(p<pq[i].top())
        {
            int prv=p;
            p=pq[i].top();
            pq[i].pop();
            pq[i].ep(prv);
            rn[i].ep(prv);
        }
    }
    if(r*sz<t)
    {
        app(r);
        for(int i=r*sz;i<t;i++)
            if(p<x[i])
                swap(p,x[i]);
        init(r);
    }
    return p;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>n>>q;
    for(int i=0;i<n;i++)
        cin>>x[i];
    while(n%sz!=0)
        x[n++]=-1;
    init();
    while(q-->0)
    {
        int s,t,p;
        cin>>s>>t>>p;
        if(s>t)
            cout<<solve(0,t,solve(s-1,n,p))<<'\n';
        else
            cout<<solve(s-1,t,p)<<'\n';
    }
    cout.flush();
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3224 ms 76460 KB Output is correct
2 Correct 3245 ms 77292 KB Output is correct
3 Correct 442 ms 4600 KB Output is correct
4 Correct 3477 ms 77576 KB Output is correct
5 Correct 2961 ms 76792 KB Output is correct
6 Correct 3610 ms 76740 KB Output is correct
7 Correct 3504 ms 76664 KB Output is correct
8 Correct 3536 ms 76872 KB Output is correct
9 Correct 433 ms 4600 KB Output is correct
10 Correct 2733 ms 72376 KB Output is correct
11 Correct 413 ms 4856 KB Output is correct
12 Correct 2810 ms 73208 KB Output is correct
13 Correct 3157 ms 77640 KB Output is correct
14 Correct 3258 ms 77560 KB Output is correct
15 Correct 422 ms 4700 KB Output is correct
16 Correct 3200 ms 77560 KB Output is correct
17 Correct 2870 ms 76584 KB Output is correct
18 Correct 3547 ms 76792 KB Output is correct
19 Correct 3511 ms 76792 KB Output is correct
20 Correct 3429 ms 76664 KB Output is correct

Subtask #3
0 / 80.0

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