#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const long long mod = 869120869120869120LL;
const long long mod2 = 133333333333333333LL;
class ModStarrySkyTree {
public:
int size_ = 1;
vector<pair<long long, int>> dat;
vector<long long>lazy;
void init(int sz, vector<long long> E) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, make_pair(mod, 0));
lazy.resize(size_ * 2, 0LL);
for (int i = 0; i < E.size(); i++) {
int pos = (i + 1) + size_;
dat[pos] = make_pair(E[i], -(i + 1));
while (pos >= 2) {
pos >>= 1;
dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
}
}
}
void refresh(int pos) {
if (pos < size_) {
lazy[pos * 2 + 0] += lazy[pos]; lazy[pos * 2 + 0] %= mod;
lazy[pos * 2 + 1] += lazy[pos]; lazy[pos * 2 + 1] %= mod;
lazy[pos] = 0;
pair<long long, int> cl = dat[pos * 2 + 0]; cl.first += lazy[pos * 2 + 0]; cl.first %= mod;
pair<long long, int> cr = dat[pos * 2 + 1]; cr.first += lazy[pos * 2 + 1]; cr.first %= mod;
dat[pos] = min(cl, cr);
}
else {
dat[pos].first += lazy[pos]; dat[pos].first %= mod;
lazy[pos] = 0;
}
}
void add_(int l, int r, long long x, int a, int b, int u) {
if (l <= a && b <= r) { lazy[u] += x; lazy[u] %= mod; refresh(u); return; }
if (r <= a || b <= l) return;
add_(l, r, x, a, (a + b) >> 1, u * 2 + 0);
add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
refresh(u);
}
void add(int l, int r, long long x) {
x = (x + mod) % mod;
add_(l, r, x, 0, size_, 1);
}
pair<long long, int> query_(int l, int r, int a, int b, int u) {
refresh(u);
if (l <= a && b <= r) return dat[u];
if (r <= a || b <= l) return make_pair(mod, -1LL);
pair<long long, int> cl = query_(l, r, a, (a + b) >> 1, u * 2 + 0);
pair<long long, int> cr = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
refresh(u);
return min(cl, cr);
}
pair<long long, int> query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
long long StringToMod(string S) {
long long r = 0;
for (int i = 0; i < S.size(); i++) {
r *= 10LL; r += (long long)(S[i] - '0');
r %= mod;
}
return r;
}
long long N, A[1 << 18], X[1 << 18]; vector<long long>F;
ModStarrySkyTree Z;
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
string V; cin >> V;
A[i] = StringToMod(V);
}
for (int i = N; i >= 1; i--) A[i] = (A[i] - A[i - 1] + mod) % mod;
for (int i = 1; i <= N; i++) F.push_back(A[i]);
Z.init(N + 1, F);
for (int i = 1; i <= N; i++) {
pair<long long, int> G = Z.query(1, N + 1);
int pos = -G.second;
X[pos] = i;
Z.add(pos + 1, N + 1, -A[pos]);
Z.add(pos, pos + 1, mod2);
}
for (int i = 1; i <= N; i++) { if (i >= 2) cout << " "; cout << X[i]; } cout << endl;
return 0;
}
Compilation message
permutation.cpp: In member function 'void ModStarrySkyTree::init(int, std::vector<long long int>)':
permutation.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E.size(); i++) {
~~^~~~~~~~~~
permutation.cpp: In function 'long long int StringToMod(std::__cxx11::string)':
permutation.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
