CF 338 E Optimize(線分樹)
2917 ワード
転載は出典を明記してください.ありがとうございます. by---cxlove
出題者の問題が分かりませんでした.囧
そしてtouristコードを見て、短くてよく分かりました.
私たちはbを並べた後、明らかに組み合わせたら必ず欲張りです.
aのあるサブストリングa'に対して条件を満たすと、明らかにすべての数とbの最大要素が加算されてh以下ではない.
少なくともlen−1個の数があるbの中の次数の大きい要素の加算はhより小さくない.このように類推すると、まず前処理してaの各要素に対して、b列のどの要素との加算はhより小さくなく、明らかに順序付けの後の2つの要素である.
ある区間の数を選択すると、区間がカバーされています.bの第iの要素は少なくともi回上書きされていますか?
便利さのために、i番目の位からiを引いて、区間の最小値が負でないかどうかを判断します.
出題者の問題が分かりませんでした.囧
そしてtouristコードを見て、短くてよく分かりました.
私たちはbを並べた後、明らかに組み合わせたら必ず欲張りです.
aのあるサブストリングa'に対して条件を満たすと、明らかにすべての数とbの最大要素が加算されてh以下ではない.
少なくともlen−1個の数があるbの中の次数の大きい要素の加算はhより小さくない.このように類推すると、まず前処理してaの各要素に対して、b列のどの要素との加算はhより小さくなく、明らかに順序付けの後の2つの要素である.
ある区間の数を選択すると、区間がカバーされています.bの第iの要素は少なくともi回上書きされていますか?
便利さのために、i番目の位からiを引いて、区間の最小値が負でないかどうかを判断します.
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define lson step << 1
#define rson step << 1 | 1
using namespace std;
typedef long long LL;
const int N = 150005;
struct Node {
int left , right , add , mn;
}L[N << 2];
int n , h , b[N] , len , a[N];
void bulid (int step , int l , int r) {
L[step].left = l;
L[step].right = r;
L[step].add = 0;
L[step].mn = 0;
if (l == r) return ;
int m = (l + r) >> 1;
bulid (lson , l , m);
bulid (rson , m + 1 , r);
}
void update (int step , int l , int r , int v);
void push_down (int step) {
int l = L[step].left , r = L[step].right , m = (l + r) >> 1;
if (L[step].add) {
update (lson , l , m , L[step].add);
update (rson , m + 1 , r , L[step].add);
L[step].add = 0;
}
}
void push_up (int step) {
L[step].mn = min (L[lson].mn , L[rson].mn);
}
void update (int step , int l , int r , int v) {
if (L[step].left == l && L[step].right == r) {
L[step].mn += v;
L[step].add += v;
return ;
}
push_down (step);
int m = (L[step].left + L[step].right) >> 1;
if (r <= m) update (lson , l , r , v);
else if (l > m) update (rson , l , r , v);
else {
update (lson , l , m , v);
update (rson , m + 1 , r , v);
}
push_up (step);
}
int main() {
int t;
#ifndef ONLINE_JUDGE
freopen ("input.txt" , "r" , stdin);
// freopen ("output.txt" , "w" , stdout);
#endif
scanf ("%d %d %d" , &n , &len , &h);
for (int i = 0 ; i < len ; i ++)
scanf ("%d" , &b[i]);
sort (b , b + len);
bulid (1 , 0 , len);
for (int i = 0 ; i < n ; i ++) {
scanf ("%d" , &a[i]);
a[i] = lower_bound (b , b + len , h - a[i]) - b;
}
for (int i = 0 ; i < len ; i ++)
update (1 , i , i , -(i + 1));
for (int i = 0 ; i < len - 1 ; i ++)
update (1 , a[i] , len , 1);
int ans = 0;
for (int i = len - 1 ; i < n ; i ++) {
update (1 , a[i] , len , 1);
if (L[1].mn >= 0) ans ++;
update (1 , a[i - len + 1] , len , -1);
}
printf ("%d
" , ans);
return 0;
}