Pagini recente » Cod sursa (job #2137061) | Cod sursa (job #2753823) | Cod sursa (job #2579209) | Cod sursa (job #1864081) | Cod sursa (job #2864352)
#include "fstream"
#include "iostream"
namespace containrr{
using namespace containrr;
struct Interval{
unsigned long long start=0, end=0;
bool onlyStart=false;
Interval(unsigned long long start){
this->start=start;
onlyStart=true;
}
Interval(unsigned long long start, unsigned long long end){
this->start=start;
this->end=end;
}
};
template<class T>
struct Command{
short command=0;
Interval commandInterval=Interval(0);
unsigned long long valNR=0;
T *vals=nullptr;
void del(){
delete vals;
}
template<typename U>
operator Command<U>(){
Command<U> newCommand;
newCommand.command=command;
newCommand.commandInterval=commandInterval;
newCommand.valNR=valNR;
newCommand.vals=new U[valNR];
for(short i=0;i<valNR;i++)
newCommand.vals[i]=vals[i];
delete vals;
return newCommand;
}
};
template <typename T>
Command<T> lowerBound(T val, Interval interval=Interval(0)){
Command<T> command;
command.command=1;
command.vals=new T[1];
command.vals[0]=val;
command.valNR=1;
command.commandInterval=interval;
return command;
}
template <typename T>
Command<T> upperBound(T val, Interval interval=Interval(0)){
Command<T> command;
command.command=2;
command.vals=new T[1];
command.vals[0]=val;
command.valNR=1;
command.commandInterval=interval;
return command;
}
template <class T=int>
class BinaryPartialSum{
private:
unsigned long long *dims=nullptr, *powsOf2=nullptr, *modif=nullptr, *currentPos=nullptr, *currentStartPos=nullptr;
T *tree=nullptr;
short dimNR=0, currentPosIndex=0, commandDim=0;
Command<T> currentCommand;
bool checkCurrentPosValidity(){
if(currentPosIndex!=dimNR)
return 0;
for(short i=0;i<dimNR;i++)
if(currentPos[i]>=dims[i]||currentPos[i]<0||currentStartPos[i]>=dims[i]||currentStartPos[i]<0||currentPos[i]<currentStartPos[i])
return 0;
return 1;
}
void init(){
powsOf2=new unsigned long long[dimNR];
modif=new unsigned long long[dimNR];
currentPos=new unsigned long long[dimNR];
currentStartPos=new unsigned long long[dimNR];
unsigned long long factor=1;
for(short i=0;i<dimNR;i++){
modif[i]=factor;
factor*=dims[i];
while((1ull<<powsOf2[i])<=dims[i])
powsOf2[i]++;
powsOf2[i]--;
}
tree = new T[factor];
}
unsigned long long basePos(short dim){
unsigned long long sum=0;
for(short i=dimNR-1;i>dim;i--)
sum+=modif[i]*currentPos[i];
return sum;
}
void add(T x, short dim=-1){
if(dim==-1)
dim=dimNR-1;
unsigned long long i=currentPos[dim], bkp=currentPos[dim], pow=1, base=basePos(dim);
while(i<dims[dim]){
if((i+1)%pow){
currentPos[dim]=i;
if(dim>0){
add(x, dim-1);
}else
tree[base+i]+=x;
i+=pow>>1;
}
pow=pow<<1;
}
currentPos[dim]=bkp;
}
T get(short dim){
unsigned long long pos=currentPos[dim]+1, base=basePos(dim);
T sum=0;
currentPos[dim]=-1;
for(unsigned long long pow=1ull<<powsOf2[dim];pow>0;pow=pow>>1){
if(currentPos[dim]+pow<pos){
currentPos[dim]+=pow;
dim==0 ? sum+=tree[base+currentPos[dim]] : sum+=get(dim-1);
}
}
currentPos[dim]=pos-1;
return sum;
}
T getInterval(short dim, short i=0){
T val=0;
val+=get(dimNR-1);
for(;i<dimNR;i++){
unsigned long long temp=currentPos[i];
currentPos[i]=currentStartPos[i]-1;
val-=getInterval(dimNR, i+1);
currentPos[i]=temp;
}
return val;
}
void getDimensions(){
init();
}
template<typename IntType, typename... Types>
void getDimensions(IntType length, Types... lengths){
dims[dimNR++]=length;
getDimensions(lengths...);
}
void getDimNR(){return;}
template<typename IntType, typename... Types>
void getDimNR(IntType length, Types... lengths){
dimNR++;
getDimNR(lengths...);
}
Interval getLowerBound(T val){
bool isOnFirstDim=true;
for(short i=0;i<dimNR;i++){
if(currentPos[i]>0||currentStartPos[i]>0)
isOnFirstDim=false;
}
if(isOnFirstDim){
unsigned long long i=-1;
T sum=0;
for(long long pow=1ull<<powsOf2[commandDim];pow>0&&i+pow>=currentCommand.commandInterval.start;pow=pow>>1){
if(i+pow<dims[commandDim]&&i+pow<currentCommand.commandInterval.end&&sum+tree[(i+pow)*modif[commandDim]]<val){
i+=pow;
sum+=tree[i*modif[commandDim]];
}
}
return Interval(currentStartPos[commandDim], i+1);
}else{
currentPos[commandDim]=-1;
for(unsigned long long pow=1ull<<powsOf2[commandDim];pow>0&¤tPos[commandDim]+pow>=currentCommand.commandInterval.start;pow=pow>>1){
currentPos[commandDim]+=pow;
if(currentPos[commandDim]>=dims[commandDim]||currentPos[commandDim]>=currentCommand.commandInterval.end||getInterval(dimNR-1)>=val)
currentPos[commandDim]-=pow;
}
return Interval(currentStartPos[commandDim], currentPos[commandDim]+1);
}
}
Interval getUpperBound(T val){
bool isOnFirstDim=true;
for(short i=0;i<dimNR;i++){
if(currentPos[i]>0||currentStartPos[i]>0)
isOnFirstDim=false;
}
if(isOnFirstDim){
unsigned long long i=-1;
T sum=0;
for(unsigned long long pow=1ull<<powsOf2[commandDim];pow>0&&i+pow>=currentCommand.commandInterval.start;pow=pow>>1){
if(i+pow<dims[commandDim]&&i+pow<currentCommand.commandInterval.end&&sum+tree[(i+pow)*modif[commandDim]]<=val){
i+=pow;
sum+=tree[i*modif[commandDim]];
}
}
return Interval(currentStartPos[commandDim], i+1);
}else{
currentPos[commandDim]=-1;
for(unsigned long long pow=1ull<<powsOf2[commandDim];pow>0&¤tPos[commandDim]+pow>=currentCommand.commandInterval.start;pow=pow>>1){
currentPos[commandDim]+=pow;
if(currentPos[commandDim]>=dims[commandDim]||currentPos[commandDim]>=currentCommand.commandInterval.end||getInterval(dimNR-1)>val)
currentPos[commandDim]-=pow;
}
return Interval(currentStartPos[commandDim], currentPos[commandDim]+1);
}
}
public:
template<typename... Types>
BinaryPartialSum(Types... lengths){
getDimNR(lengths...);
dims=new unsigned long long[dimNR];
dimNR=0;
getDimensions(lengths...);
}
T debugval(T newval=0){
if(newval){
tree[basePos(0)+currentPos[0]]=newval;
return 0;
}
if(checkCurrentPosValidity()){
return tree[basePos(0)+currentPos[0]];
}
return 0;
}
operator T(){
T val=0;
if(checkCurrentPosValidity())
switch (currentCommand.command)
{
default:
val=getInterval(dimNR-1);
break;
}
for(short i=0;i<dimNR;i++)
currentStartPos[i]=0;
currentPosIndex=0;
currentCommand.command=-1;
commandDim=-1;
if(currentCommand.vals)
delete currentCommand.vals;
currentCommand.vals=nullptr;
return val;
}
operator Interval(){
Interval val(0);
if(checkCurrentPosValidity())
switch (currentCommand.command)
{
case 1:
if(currentCommand.commandInterval.onlyStart)
currentCommand.commandInterval.end=dims[commandDim]-1;
currentPos[commandDim]=0;
val=getLowerBound(currentCommand.vals[0]);
break;
case 2:
if(currentCommand.commandInterval.onlyStart)
currentCommand.commandInterval.end=dims[commandDim]-1;
currentPos[commandDim]=0;
val=getUpperBound(currentCommand.vals[0]);
break;
default:
break;
}
for(short i=0;i<dimNR;i++)
currentStartPos[i]=0;
currentPosIndex=0;
currentCommand.command=-1;
currentCommand.commandInterval=Interval(-1,-1);
commandDim=-1;
if(currentCommand.vals)
delete currentCommand.vals;
currentCommand.vals=nullptr;
return val;
}
BinaryPartialSum &operator[](long long pos) {
currentPos[currentPosIndex]=pos;
currentStartPos[currentPosIndex++]=pos;
return *this;
}
BinaryPartialSum &operator[](Interval pos) {
currentPos[currentPosIndex]=pos.onlyStart?dims[currentPosIndex]-1:pos.end;
currentStartPos[currentPosIndex++]=pos.start;
return *this;
}
BinaryPartialSum &operator[](Command<T> command) {
this->currentCommand=command;
commandDim=currentPosIndex;
currentStartPos[currentPosIndex]=currentCommand.commandInterval.start;
if(currentCommand.commandInterval.onlyStart)
currentCommand.commandInterval.end=dims[currentPosIndex]-1;
currentPos[currentPosIndex++]=currentCommand.commandInterval.end;
return *this;
}
void operator+=(T x){
if(checkCurrentPosValidity())
add(x);
currentPosIndex=0;
}
void operator-=(T x){
if(checkCurrentPosValidity())
add(-x);
currentPosIndex=0;
}
void operator=(T x){
if(checkCurrentPosValidity()){
for(short i=0;i<dimNR;i++)
currentStartPos[i]=currentPos[i];
x-=getInterval(dimNR-1);
add(x);
}
currentPosIndex=0;
}
T *memDump(){
return tree;
}
void del(){
delete dims;
delete powsOf2;
delete modif;
delete currentPos;
delete currentStartPos;
delete tree;
}
};
}
long long pos[30000],sol[30000];
int main(){
using namespace std;
using namespace containrr;
ifstream in("schi.in");
ofstream out("schi.out");
int n;
in>>n;
BinaryPartialSum<long long> v(n);
for(int i=0;i<n;i++){
in>>pos[i];
v[i]+=1;
}
for(int i=n-1;i>=0;i--){
Interval currpos=v[lowerBound(pos[i])];
cout<<currpos.end<<" ";
sol[currpos.end]=i+1;
v[currpos.end]-=1;
}
for(int i=0;i<n;i++)
out<<sol[i]<<"\n";
out<<flush;
}