#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define int long long int
using namespace std;
#define rand() (rand() * rand() + rand() + 1)
class BigInt{
public:
int sign;
string s;
BigInt() : s("") {}
BigInt(string x){
*this = x;
}
BigInt(int x){
*this = to_string(x);
}
BigInt negative(){
BigInt x = *this;
x.sign *= -1;
return x;
}
BigInt normalize(int newSign){
for(int a = s.size() - 1; a > 0 && s[a] == '0'; a--)
s.erase(s.begin() + a);
sign = (s.size() == 1 && s[0] == '0' ? 1 : newSign);
return *this;
}
void operator =(string x){
int newSign = (x[0] == '-' ? -1 : 1);
s = (newSign == -1 ? x.substr(1) : x);
reverse(s.begin(), s.end());
this->normalize(newSign);
}
bool operator ==(const BigInt &x) const{
return (s == x.s && sign == x.sign);
}
bool operator <(const BigInt &x) const{
if(sign != x.sign) return sign < x.sign;
if(s.size() != x.s.size())
return (sign == 1 ? s.size() < x.s.size() : s.size() > x.s.size());
for(int a = s.size() - 1; a >= 0; a--) if(s[a] != x.s[a])
return (sign == 1 ? s[a] < x.s[a] : s[a] > x.s[a]);
return false;
}
bool operator <=(const BigInt &x) const{
return (*this < x || *this == x);
}
bool operator >(const BigInt &x) const{
return (!(*this < x) && !(*this == x));
}
bool operator >=(const BigInt &x) const{
return (*this > x || *this == x);
}
BigInt operator +(BigInt x){
BigInt curr = *this;
if(curr.sign != x.sign) return curr - x.negative();
BigInt res;
for(int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++){
carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
res.s += (carry % 10 + '0');
carry /= 10;
}
return res.normalize(sign);
}
BigInt operator -(BigInt x){
BigInt curr = *this;
if(curr.sign != x.sign) return curr + x.negative();
int realSign = curr.sign;
curr.sign = x.sign = 1;
if(curr < x) return ( (x - curr).negative()).normalize(-realSign);
BigInt res;
for(int a = 0, borrow = 0; a < s.size(); a++){
borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
res.s += (borrow >= 0 ? borrow + '0' : borrow + '0' + 10);
borrow = (borrow >= 0 ? 0 : 1);
}
return res.normalize(realSign);
}
BigInt operator *(BigInt x){
BigInt res("0");
for(int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] -'0'){
while(b--) res = (res + x);
x.s.insert(x.s.begin(), '0');
}
return res.normalize(sign * x.sign);
}
BigInt operator /(BigInt x){
if(x.s.size() == 1 && x.s[0] == '0') x.s[0] /= (x.s[0] - '0');
BigInt temp("0"), res;
for(int a = 0; a < s.size(); a++)
res.s += "0";
int newSign = sign * x.sign;
x.sign = 1;
for(int a = s.size() - 1; a >= 0; a--){
temp.s.insert(temp.s.begin(), '0');
temp = temp + s.substr(a, 1);
while(!(temp < x)){
temp = temp - x;
res.s[a]++;
}
}
return res.normalize(newSign);
}
BigInt operator %(BigInt x){
if(x.s.size() == 1 && x.s[0] == '0') x.s[0] /= (x.s[0] - '0');
BigInt res("0");
x.sign = 1;
for(int a = s.size() - 1; a >= 0; a--){
res.s.insert(res.s.begin(), '0');
res = res + s.substr(a, 1);
while(!(res < x))
res = res - x;
}
return res.normalize(sign);
}
// operator string(){
// string ret = s;
// reverse(ret.begin(), ret.end());
// return (sign == -1 ? "-" : "") + s;
// }
string toString() const{
string ret = s;
reverse(ret.begin(), ret.end());
return (sign == -1 ? "-" : "") + ret;
}
BigInt toBase10(int base){
BigInt exp(1), res("0"), BASE(base);
for(int a = 0; a < s.size(); a++){
int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));
res = res + (exp * BigInt(curr));
exp = exp * BASE;
}
return res.normalize(sign);
}
BigInt toBase10(int base, BigInt mod){
BigInt exp(1), res("0"), BASE(base);
for(int a = 0; a < s.size(); a++){
int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));
res = (res + ((exp * BigInt(curr) % mod)) % mod);
exp = ((exp * BASE) % mod);
}
return res.normalize(sign);
}
string convertToBase(int base){
BigInt ZERO(0), BASE(base), x = *this;
string modes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
if(x == ZERO)
return "0";
string res = "";
while(x > ZERO){
BigInt mod = x % BASE;
x = x - mod;
if(x > ZERO)
x = x / BASE;
res = modes[stoi(mod.toString())] + res;
}
return res;
}
BigInt toBase(int base){
return BigInt(this->convertToBase(base));
}
friend ostream &operator <<(ostream &os, const BigInt &x){
os << x.toString();
return os;
}
};
struct Node{
int left, right;
int key;
int prior;
BigInt sum = 0, val = 0;
int lazy;
Node(int k = 0){
left = right = key = prior = lazy = 0;
key = k;
}
bool operator<(Node& A){
return key < A.key;
}
bool operator==(Node& A){
return key == A.key;
}
};
vector<Node> node;
namespace Treap{
int root = 0;
int ind = 1;
int new_node(){
return ind++;
}
void push(int j){
if(!j) return;
int l = node[j].left;
int r = node[j].right;
node[j].key += node[j].lazy;
if(l){
node[l].lazy += node[j].lazy;
}
if(r){
node[r].lazy += node[j].lazy;
}
node[j].lazy = 0;
}
void print(int j){
if(!j)return;
push(j);
int l = node[j].left;
int r = node[j].right;
if(l){
print(l);
}
if(r){
print(r);
}
}
void up(int j){
if(!j) return;
int l = node[j].left;
int r = node[j].right;
node[j].sum = node[l].sum + node[r].sum + node[j].val;
}
void split(int j, Node v, int& l, int& r){
push(j);
if(!j) l = r = 0;
else if(node[j] < v){
split(node[j].right, v, node[j].right, r);
l = j;
}
else{
split(node[j].left, v, l, node[j].left);
r = j;
}
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
void merge(int& j, int l, int r){
push(l);
push(r);
if(!l || !r) j = max(l, r);
else if(node[l].prior > node[r].prior){
merge(node[l].right, node[l].right, r);
j = l;
}
else{
merge(node[r].left, l, node[r].left);
j = r;
}
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
void insert(int& j, int i){
push(j);
if(!j) j = i;
else if(node[i].prior > node[j].prior){
split(j, node[i], node[i].left, node[i].right);
j = i;
}
else {
if(node[i] < node[j]) insert(node[j].left, i);
else insert(node[j].right, i);
}
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
int erase(int& j, Node v){
push(j);
if(node[j] == v) {
int ret = j;
merge(j, node[j].left, node[j].right);
return ret;
}
else{
if(v < node[j]) return erase(node[j].left, v);
else return erase(node[j].right, v);
}
push(node[j].left);
push(node[j].right);
up(j);
}
int add(int v, BigInt t){
int j = new_node();
node[j].key = v;
node[j].prior = rand();
node[j].sum = node[j].val = t;
insert(root, j);
return j;
}
int leftmost(int j){
if(node[j].left) return leftmost(node[j].left);
return j;
}
int rightmost(int j){
if(node[j].right) return leftmost(node[j].right);
return j;
}
int find(int& j, BigInt s){
push(j);
int l = node[j].left;
int r = node[j].right;
if(s == node[l].sum + node[j].val) return j;
if(s <= node[l].sum) return find(l, s);
else return find(r, s - node[l].sum - node[j].val);
push(j);
push(node[j].left);
push(node[j].right);
up(j);
}
void update(int j, BigInt v){
if(v == 1){
node[root].lazy++;
add(1, v);
return;
}
int m = node[find(root, v - BigInt(1))].key;
int tl, tr;
split(root, m + 1, tl, tr);
root = tl;
add(tr ? node[leftmost(tr)].key : j, v);
if(tr) node[tr].lazy++;
merge(root, root, tr);
}
void dfs(int j){
push(j);
int l = node[j].left;
int r = node[j].right;
if(l) dfs(l);
if(r) dfs(r);
up(j);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
node = vector<Node> (n + 1);
BigInt last = 0;
for(int i = 1; i <= n; i++){
string t;
cin >> t;
BigInt x(t);
Treap::update(i, x - last);
last = x;
}
Treap::dfs(Treap::root);
for(int i = 1; i <= n; i++) cout << node[i].key << " ";
}
Compilation message
permutation.cpp: In member function 'BigInt BigInt::operator+(BigInt)':
permutation.cpp:89:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++){
| ~~^~~~~~~~~~
permutation.cpp:89:47: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++){
| ~~^~~~~~~~~~~~
permutation.cpp:90:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
| ~~^~~~~~~~~~~~~~~
permutation.cpp:90:60: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
| ~~^~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator-(BigInt)':
permutation.cpp:113:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int a = 0, borrow = 0; a < s.size(); a++){
| ~~^~~~~~~~~~
permutation.cpp:114:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
| ~~^~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator*(BigInt)':
permutation.cpp:127:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] -'0'){
| ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator/(BigInt)':
permutation.cpp:141:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int a = 0; a < s.size(); a++)
| ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::toBase10(long long int)':
permutation.cpp:199:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for(int a = 0; a < s.size(); a++){
| ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::toBase10(long long int, BigInt)':
permutation.cpp:212:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
212 | for(int a = 0; a < s.size(); a++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
4035 ms |
13548 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
4035 ms |
13548 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
4035 ms |
13548 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
4035 ms |
13548 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
35 ms |
512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
4035 ms |
13548 KB |
Time limit exceeded |
