?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
178845813 |
Дорешивание: -infinities- |
1523H - 26 | C++14 (GCC 6-32) | Полное решение | 1123 мс | 80600 КБ | 2022-11-01 16:06:14 | 2022-11-01 16:06:14 |
#include<bits/stdc++.h> namespace infinities{ #define fint register int #define ls(i) (i << 1) #define rs(i) ((i << 1) | 1) #define pii pair<int, int> #define im int mid = (l + r) >> 1 #define INT __int128 #define ll long long #define ui unsigned int #define lc ch[now][0] #define rc ch[now][1] const int INF = 998244353, maxn = 2e4 + 11; namespace FastIO{//10M const int S = 1e7; char num_[50]; int cnt_; inline int xchar(){static char buf[S]; static int len = 0, pos = 0; if(pos == len)pos = 0, len = fread(buf, 1, S, stdin); if(pos == len)exit(0); return buf[pos++];} inline int read(){fint x = 0, f = 1, ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();} return x * f;} inline void write(int x){if(x == 0){putchar('0'); return;}if(x < 0)putchar('-'), x = -x; while(x)num_[++cnt_] = x % 10 ^ 48,x /= 10; while(cnt_)putchar(num_[cnt_--]);} inline void write(int x, char c){write(x), putchar(c);} } using namespace std; using namespace FastIO; namespace mystd{ const int mod = 1e9 + 7; inline int qmin(int a, int b){return (a > b) ? b : a;} inline int qmax(int a, int b){return (a > b) ? a : b;} inline void chkmin(int &a, int b){a = min(a, b); return;} inline void chkmax(int &a, int b){a = max(a, b); return;} inline int qk_(int a, int b){return ((a + b) % mod + mod) % mod;} inline int qk(int a, int b){return (a + b < 0) ? a + b + mod : ((a + b >= mod) ? a + b - mod : a + b);} inline int mul(int a, int b){return (1ll * a * b % mod + mod) % mod;} inline int qpow(int x, int k){fint res = 1; for(; k; k = (k >> 1), x = 1ll * x * x % mod)if(k & 1)res = 1ll * res * x % mod; return res;} inline void looked(int a[], int n){for(fint i = 1; i < n; i++)write(a[i], ' '); write(a[n], '\n');} inline void debug(){puts("qwq");} inline void YES(){puts("YES");} inline void Yes(){puts("Yes");} inline void yes(){puts("yes");} inline void NO(){puts("NO");} inline void No(){puts("No");} inline void no(){puts("no");} } //using namespace mystd; void file(){freopen("a.in", "r", stdin), freopen("a.out", "w", stdout);} int n, q, a[maxn], ans[maxn][31], anss[maxn], lg[maxn], f[16][31][maxn], st[31][16][maxn]; void work(int j, int k){ for(fint i = 1; i <= n; i++)st[k][0][i] = f[j][k][i]; for(fint l = 1; l < 15; l++){ for(fint i = 1; i + (1 << l) - 1 <= n; i++){ st[k][l][i] = max(st[k][l - 1][i], st[k][l - 1][i + (1 << l - 1)]); } } } int ql[maxn], qr[maxn], qk[maxn]; int getans(int l, int r, int k){fint d = lg[r - l + 1]; return max(st[k][d][l], st[k][d][r - (1 << d) + 1]);} signed main(){ // file(); n = read(), q = read(); lg[0] = -1;//虽然没用 for(fint i = 1; i <= n; i++)lg[i] = log2(i); for(fint i = 1; i <= n; i++){a[i] = read(); for(fint k = 0; k <= 30; k++)f[0][k][i] = min(n, i + a[i] + k);} for(fint j = 1; j < 15; j++){ for(fint k = 0; k <= 30; k++)work(j - 1, k); for(fint k1 = 0; k1 <= 30; k1++)for(fint k2 = 0; k2 + k1 <= 30; k2++)for(fint i = 1; i <= n; i++) f[j][k1 + k2][i] = max(f[j][k1 + k2][i], getans(i, f[j - 1][k1][i], k2)); } for(fint i = 1; i <= q; i++){ql[i] = read(), qr[i] = read(), qk[i] = read(); for(fint k = 0; k <= 30; k++)ans[i][k] = ql[i];} for(fint j = 14; j >= 0; j--){ for(fint k = 0; k <= 30; k++)work(j, k); for(fint i = 1; i <= q; i++){ if(ql[i] == qr[i])continue; static int qwq[32]; for(fint k = 0; k <= qk[i]; k++)qwq[k] = 0; for(fint k1 = 0; k1 <= qk[i]; k1++){ for(fint k2 = 0; k2 + k1 <= qk[i]; k2++){ qwq[k1 + k2] = max(qwq[k1 + k2], getans(ql[i], ans[i][k1], k2)); } } if(qwq[qk[i]] < qr[i]){ anss[i] += (1 << j); for(fint k = 0; k <= qk[i]; k++){ ans[i][k] = qwq[k]; } } } } for(fint i = 1; i <= q; i++){cout << (ql[i] == qr[i] ? 0 : anss[i] + 1) << "\n";} return 0; } } signed main(){ return infinities::main(); }
?
?
?
?