Cod sursa(job #2613402)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 9 mai 2020 17:17:24
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 12.77 kb
/*#include<bits/stdc++.h>
#define N (int)1e5+5
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,t;
    cin>>n>>m;
    int v[n],viz[N],dp[n];
    memset(viz,0,sizeof(viz));
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;++i)
        cin>>v[i];
    dp[n-1]=1;
    viz[v[n-1]]=1;
    for(int i=n-2;i>=0;--i)
    {
        if(!viz[v[i]])
        {
            viz[v[i]]=1;
            dp[i]=dp[i+1]+1;
        }
        else
            dp[i]=dp[i+1];
    }
    for(int i=1;i<=m;++i)
    {
        cin>>t;
        cout<<dp[t-1]<<'\n';
    }

}*/
//Ksecv
/*#include<bits/stdc++.h>
#define N 100003
using namespace std;

int n,k,v[N],dp[2][N];
int s[N];

void read()
{
    ifstream fin("ksecv.in");
    fin>>n>>k;
    for(int i=0;i<n;++i)
        fin>>v[i];
    fin.close();
}


int main()
{
    read();
    bool pas=0;
    dp[0][0]=dp[0][1]=1e9;
    dp[1][0]=v[0];
    for(int j=1;j<n;++j)
    {
        dp[0][j]=1e9;
        dp[1][j]=max(dp[1][j-1],v[j]);
    }
    //cout<<dp[1][n-1];
    //dinamica in n*k
    //dp(i)(j)=min(dp(i-1)(l)+max(l+1 ... j)) dupa l de la 1 la j-1
    //i de la 1 la k
    //j de la 1 la n
    for(int i=1;i<k;++i,pas=1-pas)
    {
        for(int j=0;j<n;++j)
            dp[pas][j]=1e9;
        //stack<int> s;
        int stop=1;
        s[stop]=0;
        //in stiva imi pastrez indicii din v ai maximelor(l-ul din formula)
        //stiva va contine un sir descrescator de valori ( de fapt indicii lor )
        //fiecare valoare din stiva este un reprezentant pentru fiecare secventa
        for(int j=1;j<n;++j)
        {
            //if(stop>0)
            while(stop>0 && v[j]>=v[s[stop]])
            {
                dp[pas][j]=min(dp[pas][j],dp[1-pas][s[stop]]+v[j]);
                //daca avem o situatie de tipul:
                //  (..)(..)...(...)(...v[s[stop]]...)->urmeaza v[j] care e mai mare, trebuie actualizat numarul
                dp[pas][j]=min(dp[pas][j],dp[pas][s[stop]]-v[s[stop]]+v[j]);
                --stop;
                if(!stop)
                    break;
            }
            //daca nu e maximul pana in prezent:
            if(stop>0)
            {
                //daca incepem o noua secventa dinainte de la un indice <= s[stop]
                dp[pas][j]=min(dp[pas][j],dp[pas][s[stop]]);
                //daca incep de la s[stop]+1 (de indice mai mare am verificat mai sus
                dp[pas][j]=min(dp[pas][j],dp[1-pas][s[stop]]+v[j]);

            }

            ++stop;
            s[stop]=j;
        }

    }
    ofstream fout("ksecv.out");
    fout<<dp[k&1][n-1]<<'\n';
    fout.close();

}*/
//Order
/*#include<bits/stdc++.h>
using namespace std;
int st[120000];
ofstream fout("order.out");

int getMid(int s, int e)
{
    return s+(e-s)/2;
}

void build(int node,int s,int d)
{
    if(s==d)
    {
        st[node]=1;
        return;
    }
    build(2*node,s,getMid(s,d));
    build(2*node+1,getMid(s,d)+1,d);
    st[node]=st[2*node]+st[2*node+1];
    return;
}

void del(int node,int s,int d,int x)
{
    if(s==d)
    {
        fout<<s<<' ';
        st[node]=0;
        return;
    }
    //cout<<s<<' '<<d<<' '<<st[2*node]<<'\n';
    if(st[2*node]>=x)
    {
        del(2*node,s,getMid(s,d),x);
        st[node]=st[2*node]+st[2*node+1];
        return;
    }
    del(2*node+1,getMid(s,d)+1,d,x-st[2*node]);
    st[node]=st[2*node]+st[2*node+1];
    return;

}


int main()
{
    int n,k;
    ifstream fin("order.in");
    fin>>n;
    fin.close();
    k=n;
    build(1,1,n);
    int sters=2;
    for(int i=0;i<n;++i)
    {
        del(1,1,n,sters);
        --k;
        if(k>0)
        {
            sters+=i;
            //in sters imi retin al catelea 1 trebuie sters din arborele de intervale
            ++sters;
            sters%=k;
            if(!sters)
                sters=k;
            //cout<<<<sters<<' ';
        }

    }
    fout.close();
}*/
//Timbre
/*#include<bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int>,greater<int> > hp;
//pentru a afla costul cel mai mic la fiecare pas
vector< pair<int,int> > timbre;

bool cmp(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.first < b.first);
}

int main()
{
    int n,m,k;
    ifstream fin("timbre.in");
    ofstream fout("timbre.out");
    fin>>n>>m>>k;
    for(int i=0;i<m;++i)
    {
        int x,y;
        fin>>x>>y;
        timbre.push_back(make_pair(x,y));
    }
    sort(timbre.begin(),timbre.end());
    //int index=m-1,ans=0;
    int ans=0;
    int index=timbre.size()-1;
    //cout<<index<<' '<<m;
    while(n>0)
    {
        while(index>=0 && timbre[index].first>=n)
        {
            hp.push(timbre[index].second);
            --index;

        }
        ans+=hp.top();
        hp.pop();
        n-=k;
    }
    fout<<ans<<'\n';
    fin.close();
    fout.close();
}*/

//Drazil and Factorial
/*#include<bits/stdc++.h>
using namespace std;
string a;
void CS(string& str)
{
    int h[10] = {0};

    for (int i = 0; i < str.length(); i++)
        h[str[i] - '0']++;

    for (int i = 9; i >= 0; i--)
        for (int j = 0; j < h[i]; j++)
            cout << (char)('0' + i);
}
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(char& c:s)
    {
        if(c=='2')
            a+="2";
        if(c=='3')
            a+="3";
        if(c=='4')
            a+="322";
        if(c=='5')
            a+="5";
        if(c=='6')
            a+="53";
        if(c=='7')
            a+="7";
        if(c=='8')
            a+="7222";
        if(c=='9')
            a+="7332";

    }
    CS(a);

}*/
//Vanya and Lanterns
/*#include<bits/stdc++.h>
#include<algorithm>
#define N 1005
using namespace std;
int n,i,v[N],l;
float ans;
int main()
{
    cin>>n>>l;
    for (i=0;i<n;i++)
        cin>>v[i];
    sort(v,v+n);
    for (i=0;i<n-1;i++)
        ans=max(ans, (float)(v[i+1]-v[i]));
    ans/=2;
    ans=max(ans,max((float)v[0],(float)(l-v[n-1])));
    cout<<setprecision(10)<<fixed<<ans;
}*/
//Inv-Resubmit

/*#include<bits/stdc++.h>

#define N 100000

#define MOD 9917

using namespace std;



int getSum(int BITree[], int index)

{

    int sum = 0;

    while (index > 0)

    {

        sum += BITree[index];

        index -= index & (-index);

    }

    return sum;

}





void updateBIT(int BITree[], int n, int index, int val)

{

    while (index <= n)

    {

       BITree[index] += val;

       index += index & (-index);

    }

}



void convert(int arr[],int n)

{

    int lst[n];

    for(int i=1;i<=n;i++)

        lst[i]=arr[i];

    sort(lst+1,lst+n+1);

    for(int i=1;i<=n;i++)

        arr[i]=lower_bound(lst+1,lst+n+1,arr[i])-lst;

}



int getInvCount(int arr[], int n)

{

    int invcount = 0;

    convert(arr,n);

    int maxElement = 0;

    for (int i=1; i<=n; i++)

        if (maxElement < arr[i])

            maxElement = arr[i];



    int BIT[maxElement+1];

    for (int i=1; i<=maxElement; i++)

        BIT[i] = 0;



    for (int i=n; i>0; i--)

    {

        invcount += getSum(BIT, arr[i]-1);

        invcount%=MOD;

        updateBIT(BIT, maxElement, arr[i], 1);

    }



    return invcount;

}



int main()

{

    int arr[N],n;

    ifstream fin("inv.in");

    fin>>n;

    for(int i=1;i<=n;i++)

        fin>>arr[i];

    fin.close();

    ofstream fout("inv.out");

    fout<<getInvCount(arr,n)%MOD;

    fout.close();



}*/
//Sum of Odd Integers
/*#include<iostream>
using namespace std;
int main()
{
    unsigned long long n,k,q;
    cin>>q;
    while(q--)
    {
        cin>>n>>k;
        if((k&1)==(n&1) && (k*k)<=n)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}*/
//Sea
/*#include<bits/stdc++.h>
using namespace std;

int n,m;
vector< pair<double,double> > ship;
vector< pair<double,int> > far;

bool comp(const pair<double,double> &a,const pair<double,double> &b)
{
    return (a.first < b.first);
}

void read()
{
    ifstream fin("sea.in");
    fin>>n>>m;
    ship.reserve(n);
    for(int i=0;i<n;++i)
    {
        double a,b;
        fin>>a>>b;
        ship.emplace_back(make_pair(a,b));
    }
    far.reserve(m);
    for(int i=0;i<m;++i)
    {
        double a;
        int b; //b este nr de ordine a farului
        fin>>a>>b;
        far.emplace_back(make_pair(a,b));
    }
    fin.close();
}

double dist(double x,double y)
{
    return sqrt(x*x+y*y);
}

void solve()
{
    ofstream fout("sea.out");
    sort(ship.begin(),ship.end(),comp);
    vector<int> before;
    int adding=0;
    //in before imi pastrez indicii vapoarelor cu x mai mic decat x-ul farului curent
    for(auto& x:far)
    {
        double curr=x.first;
        int nri=x.second;
        while(adding<static_cast<int>(ship.size()) && ship[adding].first<curr)
            before.push_back(adding++);
        //cout<<ship[adding].first<<' '<<curr<<endl;
        //~bubble pe before
        //cout<<static_cast<int>(before.size())<<' ';
        for(int i=1;i<static_cast<int>(before.size());++i)
        {
            int j=i-1;
            //cout<<"plm";
            double cx1=curr-ship[before[j+1]].first,cx2=curr-ship[before[j]].first;
            double cy1=ship[before[j+1]].second,cy2=ship[before[j]].second;
            if(cx1*cx1+cy1*cy1<cx2*cx2+cy2*cy2)
                {swap(before[j],before[j+1]);
                --j;
                }
            if(j>=0)
            {
                cx1=curr-ship[before[j+1]].first,cx2=curr-ship[before[j]].first;
                cy1=ship[before[j+1]].second,cy2=ship[before[j]].second;
            }
            while(j>=0 && cx1*cx1+cy1*cy1<cx2*cx2+cy2*cy2)
            {
                swap(before[j],before[j+1]);
                --j;
                if(j>=0){
                cx1=curr-ship[before[j+1]].first,cx2=curr-ship[before[j]].first;
                cy1=ship[before[j+1]].second,cy2=ship[before[j]].second;}
            }
         }

        auto dist=[](double x,double y){
             return sqrt(x*x+y*y);
         };
        fout<<setprecision(4)<<fixed<<dist(ship[before[nri-1]].first-curr,ship[before[nri-1]].second)<<'\n';
    }
    fout.close();
}


int main()
{
    read();
    solve();
    return 0;
}*/
//Proc2
/*#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;

class proc{
int x,y;
public:
    proc(int _x,int _y):x(_x),y(_y){};
    int tim() const
    {
        return y;
    }
    int nr() const
    {
        return x;
    }
    friend bool operator >(proc const& p1, proc const& p2)
    {
        return p1.y > p2.y;
    }
};

priority_queue<int, vector<int> , greater<int> > timp;
priority_queue<proc,vector<proc>, greater<proc> > hp;

int main()
{
    int n,m;
    ifstream fin("proc2.in");
    ofstream fout("proc2.out");
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        timp.push(i);
    for(int i=0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        //if(!hp.empty())
        //cout<<hp.top().nr()<<' '<<hp.top().tim()<<endl;
        while(!hp.empty() && hp.top().tim()<=x)
        {
            //cout<<hp.top().nr()<<' ';
            timp.push(hp.top().nr());
            hp.pop();
        }
        int sol=timp.top();
        fout<<sol<<'\n';
        timp.pop();
        proc p(sol,x+y);
        hp.push(p);
    }
    fin.close();
    fout.close();
}*/
//Schi
#include<bits/stdc++.h>
using namespace std;
int v[30005],sol[30005],st[120005];

int getMid(int s, int e)
{
    return s+(e-s)/2;
}

void build(int node,int s,int d)
{
    if(s==d)
    {
        st[node]=0;
        return;
    }
    build(2*node,s,getMid(s,d));
    build(2*node+1,getMid(s,d)+1,d);
    st[node]=st[2*node]+st[2*node+1];
    return;
}

void upd(int k,int node,int s,int d,int x)
{
    if(s==d)
    {
        //fout<<s<<' ';
        sol[s]=k;
        st[node]=1;
        return;
    }
    int shift=x+st[2*node];
    //st[node]->cate pozitii din clasament sunt deja ocupate
    if(shift<=getMid(s,d)+1-s)
    {
        upd(k,2*node,s,getMid(s,d),x);
        st[node]=st[2*node]+st[2*node+1];
        return;
    }
    upd(k,2*node+1,getMid(s,d)+1,d,shift-(getMid(s,d)+1-s));
    st[node]=st[2*node]+st[2*node+1];
    return;

}


int main()
{
    int n,k;
    ifstream fin("schi.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    fin.close();
    build(1,1,n);
    for(int i=n;i>0;--i)
        upd(i,1,1,n,v[i]);
    ofstream fout("schi.out");
    for(int i=1;i<=n;++i)
        fout<<sol[i]<<'\n';
    fout.close();
}