#include <bits/stdc++.h>
#undef BALBIT
#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 = 1000000000000000000ll; // 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/cap;
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 / cap;
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] + (i<SZ(x.ho)?x.ho[i]:0) + over;
over = tmp / cap;
ho[i] = tmp % cap;
if (over == 0 && i+1>=SZ(x.ho)) break;
}
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] - (i < SZ(x.ho)?x.ho[i]:0) - over;
over = 0;
while (tmp < 0) {
tmp += cap;
over++;
}
ho[i] = tmp;
if (over == 0 && i+1>=SZ(x.ho)) break;
}
if (over) {
bug("negative number oof");
// while (1);
}
while (SZ(ho) && ho.back() == 0) ho.pop_back();
}
bool operator == (big &x) {
if (SZ(ho) != SZ(x.ho)) return 0;
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) {
ll nw = 0;
ll p10 = 1;
for (int i = SZ(s)-1; i>=0; --i) {
nw += p10 * (s[i]-'0');
p10 *= 10;
if (p10 == cap) {
p10 = 1;
ho.pb(nw);
nw = 0;
}
}
if (nw) {
ho.pb(nw);
}
}
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);
freopen("out.txt", "r", stdin);
// freopen("in.txt", "r", stdin);
clock_t ts =clock();
{
char c = ' ';
while (!(c>='0' && c<='9')) c = getchar();
while (c>='0' && c<='9') {
n = (n*10) + (c-'0');
c = getchar();
}
}
big ps("1");
string bigstring;
REP(i, 0) bigstring.pb('9');
INF = big(bigstring);
REP(i,n) {
string s;
char c = ' ';
while (!(c>='0' && c<='9')) c = getchar();
while (c>='0' && c<='9') {
s.pb(c); c=getchar();
}
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]);
// if (i % 10 == 0) cout<<i<<endl<<flush;
}
// cout<<((clock() - ts) / (double)CLOCKS_PER_SEC)<<endl;
// return 0;
// cout<<org[n-1].ho[0]<<endl;
// return 0;
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;
}
Compilation message
permutation.cpp: In function 'int main()':
permutation.cpp:216:13: warning: unused variable 'ts' [-Wunused-variable]
216 | clock_t ts =clock();
| ^~
permutation.cpp:214:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
214 | freopen("out.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4096 ms |
20500 KB |
Time limit exceeded |
