#include <iostream> #include <vector> using namespace std; #define int long long struct bigint { int sign=+1; vector<int> val; bigint() { } void set(string inp) { val.clear(); sign=1; int n=inp.size(); for(int i=n-1;i>=0;i--) { if(inp[i]=='-') { sign=-1; continue; } int cur=0,pw=1; for(int j=0;j<18 and (i-j)>=0;j++) { cur+=(inp[i-j]-'0')*pw; pw*=10; } val.push_back(cur); i-=17; } } void print() { if(sign==-1)cout<<'-'; for(int i=val.size()-1;i>=0;i--) { cout<<val[i]<<' '; } cout<<endl; } }; bigint add(bigint a,bigint b); bool cmp_abs(bigint a,bigint b) // return 0 if a>b 1 else { if(a.val.size()>b.val.size())return 0; if(a.val.size()<b.val.size())return 1; for(int i=a.val.size()-1;i>=0;i--) { if(a.val[i]!=b.val[i]) { return (a.val[i]<b.val[i]); } } return 1; } const int base=1e18; bigint sub(bigint a,bigint b) { // a-b if(a.sign!=b.sign) { b.sign*=-1; return add(a,b); } // cout<<"Sub "; // a.print(); // b.print(); bigint res; if(cmp_abs(a,b)) { // cout<<"B is bigger then A"<<endl; swap(a,b); res.sign=-a.sign; } else{ res.sign=a.sign; } int na=a.val.size(); int nb=b.val.size(); int cry=0; for(int i=0;i<na;i++) { int cb=a.val[i]-cry; cry=0; if(i<nb)cb-=b.val[i]; if(cb<0) { cb+=base; cry=1; } res.val.push_back(cb); } while(res.val.size()>0 and res.val.back()==0)res.val.pop_back(); if(res.val.size()==0) { res.sign=+1; res.val.push_back(0); } return res; } bigint add(bigint a,bigint b) { if(a.sign==1 and b.sign==1) { // we do this } else if(a.sign==-1 and b.sign==-1) { } else if(a.sign==-1 and b.sign==1) { a.sign=1; return sub(b,a); // b-a } else if(a.sign==1 and b.sign==-1) { // cout<<"Case "; // a.print(); // b.print(); b.sign=1; return sub(a,b); } bigint res; res.sign=a.sign; int na=a.val.size(); int nb=b.val.size(); int cry=0; for(int i=0;i<=max(na,nb);i++) { int cb=cry; if(i<na)cb+=a.val[i]; if(i<nb)cb+=b.val[i]; cry=(cb/base); cb%=base; res.val.push_back(cb); } while(res.val.size()>0 and res.val.back()==0)res.val.pop_back(); if(res.val.size()==0) { res.sign=+1; res.val.push_back(0); } return res; } const int N=1e6+10; bigint qp[N]; bigint mi[N],lzy[N]; int ind[N],n; void push(int l,int r,int v) { int m=(l+r)>>1,lc=v<<1,rc=lc|1; mi[v]=sub(mi[v],lzy[v]); if(l!=r) { lzy[lc]=add(lzy[lc],lzy[v]); lzy[rc]=add(lzy[rc],lzy[v]); } lzy[v].set("0"); } void build(int l=1,int r=n,int v=1) { lzy[v].set("0"); if(l==r) { mi[v]=qp[l]; // cout<<"Qp "<<l<<' ';qp[l].print(); ind[v]=l; return; } int m=(l+r)>>1,lc=v<<1,rc=lc|1; build(l,m,lc); build(m+1,r,rc); mi[v]=mi[lc]; ind[v]=ind[lc]; if(cmp_abs(mi[rc],mi[lc])) { mi[v]=mi[rc],ind[v]=ind[rc]; } // cout<<"At "<<l<<' '<<r<<' '<<v<<endl; // cout<<"Mi ";mi[v].print(); // cout<<"ind "<<ind[v]<<endl; } void update(int ql,int qr,bigint& val,int l=1,int r=n,int v=1) { push(l,r,v); if(qr<l or r<ql)return; if(ql<=l and r<=qr) { lzy[v]=add(lzy[v],val); // we have to sub lzy[v] from the min push(l,r,v); return; } int m=(l+r)>>1,lc=v<<1,rc=lc|1; update(ql,qr,val,l,m,lc); update(ql,qr,val,m+1,r,rc); mi[v]=mi[lc]; ind[v]=ind[lc]; if(cmp_abs(mi[rc],mi[lc])) mi[v]=mi[rc],ind[v]=ind[rc]; } main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; string s; bigint q[n+1]={}; // cin>>s; // q[0].set(s); // q[0].print(); int ans[n+1]={}; bigint val[n+1]={}; q[0].set("0"); bigint one; one.set("1"); for(int i=1;i<=n;i++)cin>>s,q[i].set(s),val[i]=sub(q[i],q[i-1]),qp[i]=sub(add(add(q[i-1],q[i-1]),one),q[i]); bigint infy=add(q[n],q[n]); infy.sign=-1; build(); for(int j=n;j>=1;j--) { int mx=ind[1]; ans[mx]=j; update(mx,mx,infy); // set to infy update(mx,n,val[mx]); } for(int i=1;i<=n;i++)cout<<ans[i]<<' '; cout<<endl; }

Main.cpp:209:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  209 | main()
      | ^~~~