Submission #61561233

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
Start: 
End: 
Time used: 
「責任を負う人の話は、あなたと話したことがありますよね」 
「当時の私はまだわからないけど……今は理解できるようになった」 
「大人としての責務。そして、その延長線上にある、あなたの選択」 
「それに代表されるアイデアもあります」 
「だから、先生」 
「信じられる大人のあなたなら、この歪んだ変形の終点とは、違う結果……そこにつながる選択肢……きっとあなたは見つけることができます」
DON'T GET STUCK ON ONE APPROACH!!!
*/
#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define rep(i,a,b) for (re int i = (a);i <= (b); ++i)
#define debug(x) cout << #x << '=',print(x),putchar(' ')
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define pi pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;//喵内～
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/*
Start: 
End: 
Time used: 
「責任を負う人の話は、あなたと話したことがありますよね」 
「当時の私はまだわからないけど……今は理解できるようになった」 
「大人としての責務。そして、その延長線上にある、あなたの選択」 
「それに代表されるアイデアもあります」 
「だから、先生」 
「信じられる大人のあなたなら、この歪んだ変形の終点とは、違う結果……そこにつながる選択肢……きっとあなたは見つけることができます」
DON'T GET STUCK ON ONE APPROACH!!!
*/
#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define rep(i,a,b) for (re int i = (a);i <= (b); ++i)
#define debug(x) cout << #x << '=',print(x),putchar(' ')
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define pi pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;//喵内～
inline ll read(){
    ll s = 0,f = 1;char c = getchar();
    while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
    while (isdigit(c)){s = (s<<3) + (s<<1) + (c ^ 48);c = getchar();}
    return s * f;
}//喵内～
void print(__int128 x){if (x < 0) {putchar('-'),print(-x);return ;}if (x >= 10) print(x / 10);putchar(x % 10 + 48);}//喵内～
const int Mod = 1e9 + 7;//喵内～要填数字哟～
//const int Mod = 998244353;//喵内～要填数字哟～
const ll INF = 0x3f3f3f3f;
const int N = 2e6 + 5;//喵内～要填数字哟～
ll qpow(ll x,ll y){
   ll res = 1;
    for (;y;y >>= 1,x = x * x % Mod) if (y & 1) res = res * x % Mod;
    return res;
}
int c[N];
int lowbit(int x){return x & -x;}
void add(int x,int val){for (int i = x;i < N;i += lowbit(i)) c[i] += val;}
int query(int x){int res = 0; for (int i = x;i >= 1;i -= lowbit(i)) res += c[i]; return res;}
int n,a[N];
signed main(){
    n = read();
    for (int i = 1;i <= n;++i) a[i] = read();
    for (int i = 1;i <= n;++i){
        a[i] += query(N - 1) - query(i - 1);
        add(i + a[i],1);
    }

    for (int i = 1;i <= n;++i){
        cout << max(0,a[i] + i - n) <<  " ";
    }
    cout << endl;
    return 0;
}//喵内～
/*
What's wrong with my code?
1. 小数据？特殊数据？如 n = 1?
2. 最小值，最大值取多少？是否会溢出？
3. 初始值有没有赋值？有没有建树？
4. 数组大小？是否越界？
5. 思考暴力的时候，考虑是否可能是多个连续段？或者是个数不确定无法暴力？
6. 进行详细的分类讨论?
7. 选择的区间是否可以为空？

Trick:
1. 连通 通常带有特殊性质
2. LIS 有另一种求法
3. Brovuka?

About implementation skills:
1. 全局变量多用长变量名，而局部变量，临时变量，和函数传递的参数使用短变量名。
2. 大模拟尽量遵循：怎么方便怎么写。
3. 对于一些数据很小的需要维护的量并且需要大量讨论时，可以考虑把数组拆掉换成变量。
4. 写成多个函数。
*/

Submission Info

Judge Result