fork(1) download 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define vi vector<int>
  4. #define print(v) for(auto x:v) cout << x << " "; cout<<"\n";
  5. using namespace std;
  6. void mion();
  7.  
  8. signed main() {
  9.     int t;  cin >> t;
  10.     while (t--) {
  11.         mion();
  12.     }
  13.     return 0;
  14. }
  15. struct info {
  16.     int mn,id;
  17.  
  18.     info() : mn(INT_MAX), id(-1) {
  19.     }
  20.     info(int mn,int id) : mn(mn), id(id) {
  21.     } 
  22.     bool operator<(const info& other) const {
  23.         return mn < other.mn || (mn == other.mn && id > other.id);
  24.     }
  25. };
  26.  
  27. info min(const info& a, const info& b) {
  28.     return (a < b) ? a : b;
  29. }
  30.  
  31. vector<info> seg;
  32. vi lazy;
  33.  
  34. void init(int n) {
  35.     seg.clear();
  36.     seg.resize(4*n+1);
  37.     lazy.clear();
  38.     lazy.resize(4*n+1,0);
  39. }
  40.  
  41. void build(int id,int low,int high,vi& arr) {
  42.  
  43.     if(low == high) {
  44.         seg[id] = info(arr[low],low);
  45.         return;
  46.     }
  47.     int mid = low + (high - low)/2;
  48.     build(2*id,low,mid,arr);
  49.     build(2*id+1,mid+1,high,arr);
  50.  
  51.     seg[id] = min(seg[2*id], seg[2*id+1]);
  52. }
  53.  
  54. void push(int v) {
  55.     seg[v*2].mn += lazy[v];
  56.     lazy[v*2] += lazy[v];
  57.     seg[v*2+1].mn += lazy[v];
  58.     lazy[v*2+1] += lazy[v];
  59.     lazy[v] = 0;
  60. }
  61.  
  62. void update(int id,int low,int high,int l,int r,int val) {
  63.     if(l > r) {
  64.         return;
  65.     }
  66.     if(low == l && high == r) {
  67.         seg[id].mn += val;
  68.         lazy[id] += val;
  69.         return;
  70.     }
  71.     push(id);
  72.  
  73.     int mid = low + (high - low)/2;
  74.  
  75.     update(2*id,low,mid,l,min(r,mid),val);
  76.     update(2*id+1,mid+1,high,max(l,mid+1),r,val);
  77.  
  78.     seg[id] = min(seg[2*id], seg[2*id+1]);
  79. }
  80.  
  81. info query(int id,int low,int high,int l,int r) {
  82.  
  83.     if(l > r) {
  84.         return info(INT_MAX,-1);
  85.     }
  86.     if(low == l && high == r) {
  87.         return seg[id];
  88.     }
  89.     push(id);
  90.     int mid = low + (high - low)/2;
  91.  
  92.     auto left = query(2*id,low,mid,l,min(r,mid));
  93.     auto right = query(2*id+1,mid+1,high,max(l,mid+1),r);
  94.  
  95.     return min(left, right);
  96. }
  97.  
  98. void mion() {
  99.     int n,i;  cin >> n;
  100.     init(n);
  101.     vi v(n+1);
  102.     for(i=1;i<=n;i++) {
  103.         cin >> v[i];
  104.     }
  105.     build(1,1,n,v);
  106.     vi ans(n);
  107.     int sz = n;
  108.  
  109.     while(n>0) {
  110.         i = query(1,1,n,1,n).id;
  111.         ans[i-1] = n;
  112.         update(1,1,sz,i,i,INT_MAX);
  113.         update(1,1,sz,i,sz,-1);
  114.         n--;
  115.     }
  116.     print(ans);
  117. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin 
1
6
0 0 0 1 2 0
stdout 
1 2 5 4 3 6
https://ideone.com/72yjBz
language:
C++14 (gcc 8.3)
created:
263 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!