#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#ifndef BALBIT
//#include "grader.h"
//#endif
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#ifdef BALBIT
#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(...)
#define endl '\n'
#endif // BALBITs
#define LL __int128
const int maxn = 7e4+5;
struct big{
vector<ll> ho;
static const ll bits = 62;
static const ll cap = (1ll<<bits)-1; // each digit stores [0,cap]
void mul(int x) {
// bug("mul in ");
ll over = 0;
REP(i, SZ(ho)) {
LL tmp = ho[i] * (LL)x + over;
over = tmp >>bits;
ho[i] = tmp & cap;
}
if (over) {
ho.pb(over);
}
while (SZ(ho) && ho.back() == 0) ho.pop_back();
// bug("mul out");
}
void add(int x) {
ll over = x;
REP(i, SZ(ho)) {
ll tmp = ho[i] + over;
over = tmp >>bits;
ho[i] = tmp & cap;
if (over == 0) break;
}
if (over) {
ho.pb(over);
}
while (SZ(ho) && ho.back() == 0) ho.pop_back();
}
void add(big x) {
while (SZ(ho) < SZ(x.ho)) ho.pb(0);
while (SZ(ho) > SZ(x.ho)) x.ho.pb(0);
ll over = 0;
REP(i, SZ(ho)) {
ll tmp = ho[i] + x.ho[i] + over;
over = tmp >>bits;
ho[i] = tmp & cap;
}
if (over) {
ho.pb(over);
}
while (SZ(ho) && ho.back() == 0) ho.pop_back();
}
void sub(big x) {
while (SZ(ho) < SZ(x.ho)) ho.pb(0);
while (SZ(ho) > SZ(x.ho)) x.ho.pb(0);
ll over = 0;
REP(i, SZ(ho)) {
ll tmp = ho[i] - x.ho[i] - over;
over = 0;
if (tmp < 0) {
tmp += (1ll<<bits);
over--;
}
ho[i] = tmp;
}
if (over) {
bug("negative number oof");
assert(0);
}
while (SZ(ho) && ho.back() == 0) ho.pop_back();
}
bool operator == (big x) {
return x.ho == ho;
}
bool operator < (big x) {
if (SZ(x.ho) > SZ(ho)) {
return 1;
}
if (SZ(ho) > SZ(x.ho)) {
return 0;
}
for (int i = SZ(ho)-1; i>=0; --i) {
if (ho[i] != x.ho[i]) {
if (ho[i] < x.ho[i]) return 1;
if (ho[i] > x.ho[i]) return 0;
}
}
return 0;
}
big(string s) {
for (char c : s){
mul(10);
add(c-'0');
}
}
big(){}
};
pair<big, int> s [maxn*4];
big tg[maxn*4];
//bool neg[maxn*4];
int ans[maxn];
int n;
bool Ra(pair<big, int> &a, pair<big, int> &b) { // is a better than b?
if (a.s == -1) return 0;
if (b.s == -1) return 1;
return a.f == b.f? a.s > b.s : a.f<b.f;
}
void push(int o, int l, int r) {
if (s[o].s == -1) return;
if (tg[o].ho.empty()) return;
s[o].f.sub(tg[o]);
if (l!=r) {
tg[o*2].add(tg[o]);
tg[o*2+1].add(tg[o]);
}
tg[o].ho.clear();
}
big in[maxn], a[maxn], org[maxn];
void build(int o=1, int l=0, int r=n-1) {
if (l == r) {
s[o] = {org[l], l};
return;
}
int mid = (l+r)/2;
build(o*2,l,mid);
build(o*2+1,mid+1,r);
if (Ra(s[o*2], s[o*2+1])) {
s[o] = s[o*2];
}else{
s[o] = s[o*2+1];
}
}
void MO(int L, int R, big v, bool sub, int o=1, int l=0, int r = n-1) {
push(o,l,r);
if (l > R || r < L) return;
if (l >= L && r <= R) {
if (sub)
tg[o].add(v);
push(o,l,r);
return;
}
int mid = (l+r)/2;
MO(L,R,v,sub,o*2,l,mid);
MO(L,R,v,sub,o*2+1,mid+1,r);
if (Ra(s[o*2], s[o*2+1])) {
s[o] = s[o*2];
}else{
s[o] = s[o*2+1];
}
}
big INF;
void MO2(int p, int o=1, int l=0, int r = n-1) {
push(o,l,r);
if (l > p || r < p) return;
if (l == r) {
s[o] = {INF, -1};
return;
}
int mid = (l+r)/2;
MO2(p,o*2,l,mid);
MO2(p,o*2+1,mid+1,r);
if (Ra(s[o*2], s[o*2+1])) {
s[o] = s[o*2];
}else{
s[o] = s[o*2+1];
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin>>n;
big ps("1");
string bigstring;
REP(i, 0) bigstring.pb('9');
INF = big(bigstring);
REP(i,n) {
string s; cin>>s;
in[i] = a[i] = big(s);
if (i) a[i].sub(in[i-1]);
org[i] = ps;
org[i].sub(a[i]);
bug(org[i].ho.size()==0?0:org[i].ho[0]);
// bug(a[i].ho.size()==0?0:a[i].ho[0]);
ps.add(a[i]);
}
build();
// bug(s[1].s);
for (int i = n; i>=1; i--) {
pair<big, int> hi = s[1];
int v = hi.s;
bug(v+1, a[v].ho[0]);
ans[v]=i;
MO(v+1, n-1,a[v],1);
MO2(v);
}
REP(i,n) cout<<ans[i]<<' ';
cout<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 3 |
Runtime error |
33 ms |
41836 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 3 |
Runtime error |
33 ms |
41836 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 3 |
Runtime error |
33 ms |
41836 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 3 |
Runtime error |
33 ms |
41836 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 3 |
Runtime error |
33 ms |
41836 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20556 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 3 |
Runtime error |
33 ms |
41836 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
