Pagini recente » Cod sursa (job #2128436) | Cod sursa (job #1877425) | Cod sursa (job #2603225) | Cod sursa (job #1646350) | Cod sursa (job #2756601)
#include <cstdio>
#include <cctype>
#include <algorithm>
#define NMAX 200000 //doua sute de mii
#define BUF_SIZE 1 << 17
using namespace std;
FILE *fin = fopen("schi.in", "r");
FILE *fout = fopen("schi.out", "w");
char buf[BUF_SIZE];
int pos = BUF_SIZE;
inline char nextch(){
if(pos == BUF_SIZE){
fread(buf, BUF_SIZE, 1, fin);
pos = 0;
}
return buf[pos++];
}
inline int read(){
char ch = nextch();
while( !isdigit(ch) ){
ch = nextch();
}
int nr = 0;
while( isdigit(ch) ){
nr = nr * 10 + ch - '0';
ch = nextch();
}
return nr;
}
int A, B;
int pozSterg;
int tree[4 * NMAX + 1];
int v[NMAX + 1];
int rez[NMAX + 1];
void creareArbore(int node, int left, int right){
tree[node] = right - left + 1;
if(left == right){
return;
}
int mid = left + (right - left) / 2;
creareArbore(node * 2, left, mid);
creareArbore(node * 2 + 1, mid + 1, right);
}
int query(int node, int left, int right){
if(A <= left && right <= B){
return tree[node];
}
int mid = left + (right - left) / 2;
int rez1 = 0, rez2 = 0;
if(A <= mid){
rez1 = query(node * 2, left, mid);
}
if(B >= mid + 1){
rez2 = query(node * 2 + 1, mid + 1, right);
}
return rez1 + rez2;
}
void sterg(int node, int left, int right){
if(left == right){
tree[node] = 0;
return;
}
int mid = left + (right - left) / 2;
if(pozSterg <= mid){
sterg(node * 2, left, mid);
}
else {
sterg(node * 2 + 1, mid + 1, right);
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int main()
{
int N;
N = read();
for(int i = 1; i <= N; i++){
v[i] = read();
}
creareArbore(1, 1, N);
for(int i = N; i >= 1; i--){
int lo = 0;
int hi = N + 1;
while(hi - lo > 1){
int mid = lo + (hi - lo) / 2;
A = 1;
B = mid; //[A, B] imi da intervalul pe care vreau suma
if(query(1, 1, N) >= v[i]){
hi = mid;
}
else{
lo = mid;
}
}
//raspunsul se afla in hi
rez[ hi ] = i;
pozSterg = hi;
sterg(1, 1, N); //sterg hi
}
for(int i = 1; i <= N; i++){
fprintf(fout, "%d\n", rez[i]);
}
return 0;
}