oj.uz

Submission #200905

# Submission time Handle Problem Language Result Execution time Memory
200905 2020-02-08T13:27:58 Z gs18115 Sushi (JOI16_sushi) C++14
15 / 100
 3624 ms 82040 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]),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 138 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 3234 ms 76744 KB Output is correct
2 Correct 3282 ms 80376 KB Output is correct
3 Correct 431 ms 5856 KB Output is correct
4 Correct 3200 ms 82040 KB Output is correct
5 Correct 2943 ms 81144 KB Output is correct
6 Correct 3624 ms 81016 KB Output is correct
7 Correct 3506 ms 81152 KB Output is correct
8 Correct 3442 ms 81144 KB Output is correct
9 Correct 411 ms 6008 KB Output is correct
10 Correct 2735 ms 75256 KB Output is correct
11 Correct 413 ms 5624 KB Output is correct
12 Correct 2793 ms 76412 KB Output is correct
13 Correct 3192 ms 82040 KB Output is correct
14 Correct 3215 ms 80532 KB Output is correct
15 Correct 411 ms 5880 KB Output is correct
16 Correct 3150 ms 81784 KB Output is correct
17 Correct 2848 ms 81040 KB Output is correct
18 Correct 3461 ms 81248 KB Output is correct
19 Correct 3409 ms 81144 KB Output is correct
20 Correct 3404 ms 81208 KB Output is correct

Subtask #3
0 / 80.0

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