#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#pragma warning (disable: 4996)
int cnt = 0;
const long long MAX_Z = 1000000000000000000LL;
struct BigInteger {
vector<long long> t;
};
bool operator==(BigInteger a1, BigInteger a2) {
if (a1.t == a2.t) return true;
return false;
}
bool operator<(BigInteger a1, BigInteger a2) {
if (a1.t.size() < a2.t.size()) return true;
if (a1.t.size() > a2.t.size()) return false;
for (int i = (int)a1.t.size() - 1; i >= 0; i--) {
if (a1.t[i] < a2.t[i]) return true;
if (a1.t[i] > a2.t[i]) return false;
}
return false;
}
BigInteger operator+(BigInteger a1, BigInteger a2) {
BigInteger a3; a3.t.resize(max(a1.t.size(), a2.t.size()) + 1, 0);
for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
for (int i = 0; i < a2.t.size(); i++) a3.t[i] += a2.t[i];
for (int i = 0; i < (int)a3.t.size() - 1; i++) {
while (a3.t[i] >= MAX_Z) { a3.t[i] -= MAX_Z; a3.t[i + 1] += 1; }
}
while (a3.t.size() >= 2 && a3.t[a3.t.size() - 1] == 0) a3.t.pop_back();
return a3;
}
BigInteger operator-(BigInteger a1, BigInteger a2) {
BigInteger a3; a3.t.resize(max(a1.t.size(), a2.t.size()) + 1, 0);
for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
for (int i = 0; i < a2.t.size(); i++) a3.t[i] -= a2.t[i];
for (int i = 0; i < (int)a3.t.size() - 1; i++) {
while (a3.t[i] < 0) { a3.t[i] += MAX_Z; a3.t[i + 1] -= 1; }
}
while (a3.t.size() >= 2 && a3.t[a3.t.size() - 1] == 0) a3.t.pop_back();
return a3;
}
BigInteger ConvertFromString(string V) {
BigInteger a1; a1.t.resize(((int)V.size() + 17) / 18);
reverse(V.begin(), V.end());
long long r = 1;
for (int i = 0; i < V.size(); i++) {
a1.t[i / 18] += r * (long long)(V[i] - '0');
r *= 10;
if (i % 18 == 17) r = 1;
}
return a1;
}
BigInteger getmin(BigInteger a1, BigInteger a2) {
if (a1.t < a2.t) return a1;
return a2;
}
pair<BigInteger, int> getmin(pair<BigInteger, int> a1, pair<BigInteger, int> a2) {
if (a1.first < a2.first) return a1;
return a2;
}
int N;
BigInteger P[100009]; int A[100009];
// -------------------- Segment Tree -------------------
int size_ = 0;
pair<BigInteger, int> dat[1 << 17]; BigInteger lazy[1 << 17]; BigInteger INF;
void init(int sz) {
string str = ""; for (int i = 0; i < 400; i++) str += "9";
INF = ConvertFromString(str);
size_ = 1;
while (size_ <= sz) size_ *= 2;
for (int i = 1; i <= N; i++) dat[size_ + i] = make_pair(P[i], i);
for (int i = size_ - 1; i >= 1; i--) dat[i] = getmin(dat[i * 2], dat[i * 2 + 1]);
}
void move_lazy(int pos) {
if (pos < size_) {
lazy[pos * 2 + 0] = lazy[pos * 2 + 0] + lazy[pos];
lazy[pos * 2 + 1] = lazy[pos * 2 + 1] + lazy[pos];
lazy[pos] = ConvertFromString("0");
}
}
void refresh(int pos) {
if (pos < size_) {
pair<BigInteger, int> A1 = dat[pos * 2 + 0]; A1.first = A1.first - lazy[pos * 2 + 0];
pair<BigInteger, int> A2 = dat[pos * 2 + 1]; A2.first = A2.first - lazy[pos * 2 + 1];
dat[pos] = getmin(A1, A2);
}
else {
pair<BigInteger, int> A1 = dat[pos]; A1.first = A1.first - lazy[pos];
lazy[pos] = ConvertFromString("0");
dat[pos] = A1;
}
}
void lose_(int l, int r, BigInteger p, int a, int b, int u) {
if (l <= a && b <= r) { lazy[u] = lazy[u] + p; move_lazy(u); refresh(u); return; }
if (r <= a || b <= l) return;
lose_(l, r, p, a, (a + b) >> 1, u * 2 + 0);
lose_(l, r, p, (a + b) >> 1, b, u * 2 + 1);
refresh(u);
}
void lose(int cl, int cr, BigInteger p) {
lose_(cl, cr, p, 0, size_, 1);
}
pair<BigInteger, int> query_(int l, int r, int a, int b, int u) {
move_lazy(u);
if (l <= a && b <= r) return dat[u];
if (r <= a || b <= l) return make_pair(INF, -1);
pair<BigInteger, int> G1 = query_(l, r, a, (a + b) >> 1, u * 2 + 0);
pair<BigInteger, int> G2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
refresh(u);
return getmin(G1, G2);
}
pair<BigInteger, int> query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
void annihilation(int pos) {
lose(pos, pos + 1, ConvertFromString("0"));
// lazy = 0 となった
dat[pos + size_] = make_pair(INF, -1);
int cx = pos + size_;
while (cx >= 2) {
cx >>= 1;
refresh(cx);
}
}
// -------------------- Segment Tree End ----------------
int main() {
//FILE *in = freopen("in1.txt", "r", stdin);
cin >> N;
for (int i = 1; i <= N; i++) {
string V;
cin >> V;
P[i] = ConvertFromString(V);
}
for (int i = N; i >= 1; i--) P[i] = (P[i] - P[i - 1]);
init(N + 1);
int cnts = 0;
while (cnts < N) {
pair<BigInteger, int> c = query(1, N + 1);
int pos = c.second;
cnts++; A[pos] = cnts;
lose(pos + 1, N + 1, P[pos]);
lose(pos, pos + 1, ConvertFromString("0"));
annihilation(pos);
}
for (int i = 1; i <= N; i++) { if (i >= 2) cout << " "; cout << A[i]; } cout << endl;
//cout << "count = " << cnt << endl;
return 0;
}
Compilation message
permutation.cpp:6:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
permutation.cpp: In function 'BigInteger operator+(BigInteger, BigInteger)':
permutation.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
~~^~~~~~~~~~~~~
permutation.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a2.t.size(); i++) a3.t[i] += a2.t[i];
~~^~~~~~~~~~~~~
permutation.cpp: In function 'BigInteger operator-(BigInteger, BigInteger)':
permutation.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a1.t.size(); i++) a3.t[i] += a1.t[i];
~~^~~~~~~~~~~~~
permutation.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a2.t.size(); i++) a3.t[i] -= a2.t[i];
~~^~~~~~~~~~~~~
permutation.cpp: In function 'BigInteger ConvertFromString(std::__cxx11::string)':
permutation.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
72 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
72 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10268 KB |
Output is correct |
| 5 |
Execution timed out |
4043 ms |
27068 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
72 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10268 KB |
Output is correct |
| 5 |
Execution timed out |
4043 ms |
27068 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
72 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10268 KB |
Output is correct |
| 5 |
Execution timed out |
4043 ms |
27068 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
72 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10268 KB |
Output is correct |
| 5 |
Execution timed out |
4043 ms |
27068 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
36 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
72 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10268 KB |
Output is correct |
| 5 |
Execution timed out |
4043 ms |
27068 KB |
Time limit exceeded |
