#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
typedef vector < int > vi;
vector < int > s[N],A[N];
int pri[N],sz[N],lz[N],L[N],R[N],ans[N],uu;
char u[N+N];
void put(int x){
if(!x) return;
lz[x] = 1 - lz[x];
swap(L[x],R[x]);
}
void push(int x){
if(!lz[x]) return;
lz[x] = 0;
put(L[x]); put(R[x]);
}
vi top(vi a, vi b){
if(a.size() < b.size()) swap(a,b);
int t,i,j,h=0;
for(i=a.size()-1,j=b.size()-1 ; i>=0 ; i--,j--){
t = a[i]+h+(j<b.size() ? b[j] : 0);
if(t >= 10) { h=1; t-=10; }
else h=0;
a[i] = t;
}
if(h) a.insert(a.begin() , 1);
return a;
}
vi cik(vi a, vi b){
int t,i,j,h=0;
for(i=a.size()-1,j=b.size()-1 ; i >= 0; i--,j--){
t = a[i]-h-(j<b.size() ? b[j] : 0);
if(t < 0) { h=1; t+=10; }
else h=0;
a[i] = t;
}
for(; a.size()>1 && a[0] == 0 ;) a.erase(a.begin());
return a;
}
void relax(int x){
sz[x] = sz[ L[x] ] + sz[ R[x] ] + 1;
s[x] = top(A[x] , top(s[ L[x] ] , s[ R[x] ]));
}
int mrg(int x, int y){
if(!x) return y;
if(!y) return x;
if(pri[x] < pri[y]){
push(y);
L[y] = mrg(x,L[y]);
relax(y);
return y;
}
else{
push(x);
R[x] = mrg(R[x],y);
relax(x);
return x;
}
}
bool g(vi &a, vi &b){
if(a.size() < b.size()) return 1;
if(a.size() > b.size()) return 0;
for(int i=0; i<a.size(); i++){
if(b[i] > a[i])
return 1;
if(a[i] > b[i])
return 0;
}
return 1;
}
void split(int x, vector <int> k, int &a, int &b){
if(x == 0){
a = b = 0;
return;
}
push(x);
if(g(k,s[ L[x] ])){
split(L[x], k, a, b);
L[x] = b;
b = x;
}
else{
vi vv = cik(k,s[ L[x] ]);
vv = cik(vv,A[x]);
split(R[x], vv, a, b);
R[x] = a;
a = x;
}
relax(x);
}
void f(int x, int h){
if(x==0) return;
push(x);
f(L[x],h); ans[x] = h+sz[ L[x] ]+1; f(R[x],h+sz[ L[x] ]+1);
}
vi bir,x,y,t;
int n,i,j,a,b,root;
int main(){
bir.pb(1);
s[0].pb(0);
A[0].pb(0);
y.pb(0);
scanf("%lld",&n);
srand(time(NULL));
for(i=1;i<=n;i++){
scanf(" %s", u);
uu = strlen(u);
x.clear();
for(j=0;j<uu;j++) x.pb(u[j]-'0');
t = cik(x,y);
t = cik(t,bir);
split(root, t, a, b);
t = cik(x,y);
sz[i] = 1;
pri[i] = rand();
s[i] = A[i] = t;
root = mrg( mrg(a,i) , b );
y = x;
}
f(root,0);
for(i=1;i<=n;i++) printf("%lld ",ans[i]);
return 0;
}
Compilation message
permutation.cpp: In function 'vi top(vi, vi)':
permutation.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
t = a[i]+h+(j<b.size() ? b[j] : 0);
~^~~~~~~~~
permutation.cpp: In function 'vi cik(vi, vi)':
permutation.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
t = a[i]-h-(j<b.size() ? b[j] : 0);
~^~~~~~~~~
permutation.cpp: In function 'bool g(vi&, vi&)':
permutation.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<a.size(); i++){
~^~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:120:20: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
scanf("%lld",&n);
~~^
permutation.cpp:140:44: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
for(i=1;i<=n;i++) printf("%lld ",ans[i]);
~~~~~~^
permutation.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
permutation.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", u);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| 3 |
Correct |
33 ms |
10292 KB |
Output is correct |
| 4 |
Correct |
41 ms |
10352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| 3 |
Correct |
33 ms |
10292 KB |
Output is correct |
| 4 |
Correct |
41 ms |
10352 KB |
Output is correct |
| 5 |
Execution timed out |
4027 ms |
41932 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| 3 |
Correct |
33 ms |
10292 KB |
Output is correct |
| 4 |
Correct |
41 ms |
10352 KB |
Output is correct |
| 5 |
Execution timed out |
4027 ms |
41932 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| 3 |
Correct |
33 ms |
10292 KB |
Output is correct |
| 4 |
Correct |
41 ms |
10352 KB |
Output is correct |
| 5 |
Execution timed out |
4027 ms |
41932 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| 3 |
Correct |
33 ms |
10292 KB |
Output is correct |
| 4 |
Correct |
41 ms |
10352 KB |
Output is correct |
| 5 |
Execution timed out |
4027 ms |
41932 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9832 KB |
Output is correct |
| 3 |
Correct |
33 ms |
10292 KB |
Output is correct |
| 4 |
Correct |
41 ms |
10352 KB |
Output is correct |
| 5 |
Execution timed out |
4027 ms |
41932 KB |
Time limit exceeded |
