#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<(b); ++i)
#define rep3(i,a,b) for(int i=a; i>=(b); --i)
#define pb push_back
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define pow2(x) (1ll<<(x))
#define inf 0x3f3f3f3f3f3f3f3f
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T x){cerr << x << endl;}
template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);}
#else
#define bug(...) 49
#endif
const int maxn=70005,mod=1000000007;
#define num vector<int16_t>
int n,val[maxn*4],minid[maxn*4],ans[maxn];
num a[maxn],minn[maxn*4],tag[maxn*4];
void ri(num& x){
x.clear();
string str;
cin >> str;
reverse(all(str));
for(auto c: str) x.pb(c^'0');
}
void noob(num& x){
if(x.empty()){
x.pb(0);
return;
}
rep(sz(x)-1){
x[i+1]+=x[i]/10;
x[i]%=10;
if(x[i]<0) x[i+1]--,x[i]+=10;
}
while(x.back()>=10||x.back()<=-10){
x.pb(x.back()/10);
x[sz(x)-2]%=10;
}
while(sz(x)>1&&x.back()==0) x.pop_back();
}
num operator +(const num& x, const num& y){
int k=max(sz(x),sz(y));
num res(k);
rep(sz(x)) res[i]+=x[i];
rep(sz(y)) res[i]+=y[i];
noob(res);
return res;
}
num operator -(const num& x, const num& y){
int k=max(sz(x),sz(y));
num res(k);
rep(sz(x)) res[i]+=x[i];
rep(sz(y)) res[i]-=y[i];
noob(res);
return res;
}
bool operator <(const num& x, const num& y){
if(x.back()<0&&y.back()>=0) return true;
if(y.back()<0&&x.back()>=0) return false;
bool flag=0;
if(x.back()<0) flag=1;
if(sz(x)<sz(y)) return 1^flag;
if(sz(y)<sz(x)) return flag;
rep3(i,sz(x)-1,0){
if(x[i]<y[i]) return true;
if(x[i]>y[i]) return false;
}
return false;
}
void pull(int k){
val[k]=val[k<<1]+val[k<<1|1];
if(!val[k<<1]) return minn[k]=minn[k<<1|1],minid[k]=minid[k<<1|1],void();
if(!val[k<<1|1]) return minn[k]=minn[k<<1],minid[k]=minid[k<<1],void();
if(minn[k<<1]<minn[k<<1|1]) minn[k]=minn[k<<1],minid[k]=minid[k<<1];
else minn[k]=minn[k<<1|1],minid[k]=minid[k<<1|1];
}
void push(int k, int l, int r){
if(l!=r){
minn[k<<1]=minn[k<<1]+tag[k];
minn[k<<1|1]=minn[k<<1|1]+tag[k];
tag[k<<1]=tag[k<<1]+tag[k];
tag[k<<1|1]=tag[k<<1|1]+tag[k];
}
tag[k]=num(1);
}
void build(int k, int l, int r){
if(l==r){
minn[k]=a[l];
minid[k]=l;
val[k]=1;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
pull(k);
}
void modify(int k, int l, int r, int ql, int qr, num& x){
if(l>qr||r<ql) return;
if(ql<=l&&qr>=r){
minn[k]=minn[k]+x,tag[k]=tag[k]+x;
return;
}
int mid=l+r>>1;
push(k,l,r);
modify(k<<1,l,mid,ql,qr,x),modify(k<<1|1,mid+1,r,ql,qr,x);
pull(k);
}
void modify2(int k, int l, int r, int p){
if(l==r){
val[k]--;
return;
}
int mid=l+r>>1;
push(k,l,r);
if(p<=mid) modify2(k<<1,l,mid,p);
else modify2(k<<1|1,mid+1,r,p);
pull(k);
}
void print(int k, int l, int r){
bug(k,l,r,minid[k]);
for(auto i: minn[k]) bug(i);
if(l==r) return;
push(k,l,r);
int mid=l+r>>1;
print(k<<1,l,mid),print(k<<1|1,mid+1,r);
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n;
rep(n) ri(a[i]);
rep(n) for(auto j: a[i]) bug(i,j);
rep3(i,n-1,1) a[i]=a[i]-a[i-1];
rep(n) for(auto j: a[i]) bug(i,j);
build(1,0,n-1);
print(1,0,n-1);
rep(n){
int x=minid[1];
ans[x]=i+1;
bug(x);
modify2(1,0,n-1,x);
num tmp(1);
tmp=tmp-a[x];
modify(1,0,n-1,x+1,n-1,tmp);
}
rep(n) cout << ans[i] << ' ';
cout << "\n";
}
Compilation message
permutation.cpp: In function 'void build(long long int, long long int, long long int)':
permutation.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, std::vector<short int>&)':
permutation.cpp:124:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
124 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'void modify2(long long int, long long int, long long int, long long int)':
permutation.cpp:135:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'void print(long long int, long long int, long long int)':
permutation.cpp:22:18: warning: statement has no effect [-Wunused-value]
22 | #define bug(...) 49
| ^~
permutation.cpp:143:5: note: in expansion of macro 'bug'
143 | bug(k,l,r,minid[k]);
| ^~~
permutation.cpp:22:18: warning: statement has no effect [-Wunused-value]
22 | #define bug(...) 49
| ^~
permutation.cpp:144:26: note: in expansion of macro 'bug'
144 | for(auto i: minn[k]) bug(i);
| ^~~
permutation.cpp:144:14: warning: unused variable 'i' [-Wunused-variable]
144 | for(auto i: minn[k]) bug(i);
| ^
permutation.cpp:147:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
147 | int mid=l+r>>1;
| ~^~
permutation.cpp: In function 'int main()':
permutation.cpp:22:18: warning: statement has no effect [-Wunused-value]
22 | #define bug(...) 49
| ^~
permutation.cpp:155:30: note: in expansion of macro 'bug'
155 | rep(n) for(auto j: a[i]) bug(i,j);
| ^~~
permutation.cpp:155:21: warning: unused variable 'j' [-Wunused-variable]
155 | rep(n) for(auto j: a[i]) bug(i,j);
| ^
permutation.cpp:22:18: warning: statement has no effect [-Wunused-value]
22 | #define bug(...) 49
| ^~
permutation.cpp:157:30: note: in expansion of macro 'bug'
157 | rep(n) for(auto j: a[i]) bug(i,j);
| ^~~
permutation.cpp:157:21: warning: unused variable 'j' [-Wunused-variable]
157 | rep(n) for(auto j: a[i]) bug(i,j);
| ^
permutation.cpp:22:18: warning: statement has no effect [-Wunused-value]
22 | #define bug(...) 49
| ^~
permutation.cpp:163:9: note: in expansion of macro 'bug'
163 | bug(x);
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15564 KB |
Output is correct |
| 4 |
Correct |
27 ms |
15556 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15564 KB |
Output is correct |
| 4 |
Correct |
27 ms |
15556 KB |
Output is correct |
| 5 |
Correct |
3133 ms |
59020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15564 KB |
Output is correct |
| 4 |
Correct |
27 ms |
15556 KB |
Output is correct |
| 5 |
Correct |
3133 ms |
59020 KB |
Output is correct |
| 6 |
Execution timed out |
4073 ms |
96388 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15564 KB |
Output is correct |
| 4 |
Correct |
27 ms |
15556 KB |
Output is correct |
| 5 |
Correct |
3133 ms |
59020 KB |
Output is correct |
| 6 |
Execution timed out |
4073 ms |
96388 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15564 KB |
Output is correct |
| 4 |
Correct |
27 ms |
15556 KB |
Output is correct |
| 5 |
Correct |
3133 ms |
59020 KB |
Output is correct |
| 6 |
Execution timed out |
4073 ms |
96388 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15128 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15148 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15564 KB |
Output is correct |
| 4 |
Correct |
27 ms |
15556 KB |
Output is correct |
| 5 |
Correct |
3133 ms |
59020 KB |
Output is correct |
| 6 |
Execution timed out |
4073 ms |
96388 KB |
Time limit exceeded |
