Submission #61602433

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 = 2e5 + 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 a[N],n,b[N];
int f[N][20];
void init(){
    for (int i = 1;i <= n;++i) f[i][0] = b[i] - i;
    for (int j = 1;j <= 19;++j){
        for (int i = 1;i + (1 << j) - 1 <= n;++i){
            f[i][j] = min(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
        }
    }
}
int query(int l,int r){
    int k = log2(r - l + 1);
    return min(f[l][k],f[r - (1 << k) + 1][k]);
}
signed main(){
    n = read();
    for (int i = 1;i <= n;++i)
        a[i] = read();

    for (int i = 1;i <= n;++i){
        b[i] = upper_bound(a + 1,a + n + 1,a[i] / 2) - a - 1;
        //debug(b[i]),puts("");
    }

    init();


    int q = read();
    while (q--){
        int l = read(),r = read();
        int mid = (l + r) / 2;
        /*int L = mid - 1,R = r + 1;
        while (L + 1 != R){
            int qmid = L + R >> 1;
            if (query(qmid,r) >= l - mid + 1) R = qmid;
            else L = qmid;
        }*/

        cout << max(0,min(r - mid,query(mid + 1,r) + r - l + 1)) << 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

Compile Error

Main.cpp: In function ‘void init()’:
Main.cpp:44:53: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   44 |             f[i][j] = min(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
      |                                                   ~~^~~

Judge Result