Submission #78387

#	Time	Username	Problem	Language	Result	Execution time	Memory
78387		igzi	Zalmoxis (BOI18_zalmoxis)	C++17	0 / 100	1080 ms	70200 KiB

zalmoxis

#include <bits/stdc++.h>
#include <ext/rope>
#define maxN 1000005
#define s 4294967296

using namespace std;
using namespace __gnu_cxx;

int n,k,i,x,p;
priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int f[maxN];
void update(int p){
while(p<=n){
    f[p]++;
    p+=p & (-p);
}
}
int query(int p){
int ans=0;
while(p>0){
    ans+=f[p];
    p-=p &(-p);
}
return ans;
}
struct broj{
int b;
int sl;
};
broj v[maxN];
rope <long long> r;

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>k;
    cin>>x;
    pq.push({x,i});
    p=0;
    r.insert(r.mutable_end(),s*x+p);
    v[0].b=x;
    v[0].sl=-1;
    p=1;
    for(i=1;i<n;i++){
        cin>>x;
        pq.push({x,i});
        v[p].b=x;
        v[p-1].sl=p;
        r.insert(r.mutable_end(),s*x+p);
        p++;
    }
    v[p-1].sl=-1;
    //for(i=0;i<n;i++) cout<<r[i]/s<<" ";
    while(k>0){
        long long tmp=pq.top().second;
        pq.pop();
        x=tmp-query(tmp);
        if((x==r.size()-1 || r[x+1]/s!=r[x]/s) && (x==0 || r[x-1]/s!=r[x]/s)){
            broj c;
            c.sl=v[r[x]%s].sl;
            c.b=r[x]/s;
            pq.push({c.b,tmp});
            v[p]=c;
            v[r[x]%s].sl=p;
            tmp=(r[x]/s+1)*s+p;
            p++;
            //cout<<r[x]/s<<" "<<tmp/s<<endl;
            r.erase(x,1);
            r.insert(r.mutable_begin()+x,tmp);
        }
        else{
            if(x!=r.size()-1 && r[x+1]/s==r[x]/s){
                update(r[x+1]%s);
                broj c;
                c.sl=v[r[x+1]%s].sl;
                c.b=r[x+1]/s+1;
                pq.push({c.b,tmp});
                v[p]=c;
                v[r[x+1]%s].sl=p;
                tmp=(r[x]/s+1)*s+p;
                p++;
                r.erase(x,1);
                r.insert(r.mutable_begin()+x,tmp);
                r.erase(x+1,1);
            }
            else{
                update(r[x-1]%s);
                broj c;
                c.sl=v[r[x-1]%s].sl;
                c.b=r[x-1]/s+1;
                pq.push({c.b,tmp});
                v[p]=c;
                v[r[x-1]%s].sl=p;
                tmp=(r[x]/s+1)*s+p;
                p++;
                r.erase(x,1);
                r.insert(r.mutable_begin()+x,tmp);
                r.erase(x-1,1);
            }
        }
        k--;
    }
    int x=0;
    while(x!=-1){
        cout<<v[x].b<<" ";
        x=v[x].sl;
    }
    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:58:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if((x==r.size()-1 || r[x+1]/s!=r[x]/s) && (x==0 || r[x-1]/s!=r[x]/s)){
             ~^~~~~~~~~~~~
zalmoxis.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(x!=r.size()-1 && r[x+1]/s==r[x]/s){
                ~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70