Submission #559147

#	Time	Username	Problem	Language	Result	Execution time	Memory
559147		groshi	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	132 ms	15628 KiB

ho_t1

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int t[300000];
int drzewo[1000000];
int drzewo2[1000000];
int pot=1;
int wynik[300000];
int a[300000];
int b[300000];
vector<pair<int,int> > Q;
vector<int> Q2;
int zap1(int x,int y)
{
    if(x>y)
        return 0;
    x+=pot;
    y+=pot;
    int wynik=0;
    wynik=max(drzewo[x],drzewo[y]);
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik=max(wynik,drzewo[x+1]);
        if(y%2==1)
            wynik=max(wynik,drzewo[y-1]);
        x/=2;
        y/=2;
    }
    return wynik;
}
int zap2(int x,int y)
{
    if(x>y)
        return 0;
    x+=pot;
    y+=pot;
    int wynik=0;
    wynik=max(drzewo2[x],drzewo2[y]);
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik=max(wynik,drzewo2[x+1]);
        if(y%2==1)
            wynik=max(wynik,drzewo2[y-1]);
        x/=2;
        y/=2;
    }
    return wynik;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    while(pot<=n+1)
        pot*=2;
    pot--;
    for(int i=1;i<=n+1;i++)
    {
        cin>>a[i];
        Q.push_back({a[i],i});
    }
    sort(Q.begin(),Q.end());
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
        Q2.push_back(b[i]);
    }
    sort(Q2.begin(),Q2.end());
    for(int i=1;i<=n;i++)
        b[i]=Q2[i-1];
    for(int i=1;i<=n+1;i++)
    {
        //cout<<a[Q[i-1].second]<<" "<<b[i-1]<<" "<<b[i]<<"\n";
        if(i<=n)
            drzewo[i+pot]=a[Q[i-1].second]-b[i];
        if(i>1)
            drzewo2[i+pot]=a[Q[i-1].second]-b[i-1];
    }
    for(int i=pot;i>=1;i--)
        drzewo[i]=max(drzewo[i*2],drzewo[i*2+1]);
    for(int i=pot;i>=1;i--)
        drzewo2[i]=max(drzewo2[i*2],drzewo2[i*2+1]);
    for(int i=1;i<=n+1;i++)
    {
        //cout<<"na lewo "<<zap1(1,i-1)<<" "<<zap2(i+1,n)<<"\n";
        //cout<<"usuwam "<<Q[i-1].second<<"\n";
        wynik[Q[i-1].second]=max(zap1(1,i-1),zap2(i+1,n+1));
        wynik[Q[i-1].second]=max(wynik[Q[i-1].second],0);
    }
    for(int i=1;i<=n+1;i++)
        cout<<wynik[i]<<" ";
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91