Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Candles
- Time limit: 1000 ms
- Memory limit: 128 MB
- You have N candles, for each candle i you know its height h_i. Using a candle during one evening decreases the candle height by 1.
- You plan to have at most M romantic evenings. For each evening i you know the number of candles c_i you want to lit. Find of strategy of lighting the candles in order to maximize the number of evenings you can spend. You are forced to stop after the first night i when you can't light c_i candles.
- */
- #include<bits/stdc++.h>
- #define INF 1000010000
- #define nl '\n'
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pdd pair<double,double>
- #define all(c) (c).begin(), (c).end()
- #define SORT(c) sort(all(c))
- #define sz(c) (c).size()
- #define rep(i,n) for( int i = 0; i < n; ++i )
- #define repi(i,n) for( int i = 1 ; i <= n; ++i )
- #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
- #define repf(j,i,n) for( int j = i ; j < n ; ++j )
- #define die(s) {std::cout << s << nl;}
- #define dier(s) {std::cout << s; return 0;}
- #define vi vector<int>
- typedef long long ll;
- #define MAXN 101010
- using namespace std;
- vector<ll> t(2 * MAXN , 0);
- vector<ll> lazy(MAXN , 0);
- int n , h;
- void calc(int p , int k){
- if(lazy[p] == 0){
- t[p] = t[2 * p] + t[2 * p + 1];
- }else{
- t[p] += k * lazy[p];
- }
- }
- void apply(int p , ll val , int k){
- t[p] += val;
- if(p < n){
- lazy[p] += val;
- }
- }
- void build(int l , int r){
- int k = 2;
- for(l += n , r += n - 1 ; l > 1 ; k *= 2){
- l /= 2;
- r /= 2;
- for(int i = r ; i >= l ; --i){
- calc(i , k);
- }
- }
- }
- void push(int l , int r){
- int s = h , k = 1 << (h - 1);
- for(l += n , r += n - 1 ; s > 0 ; --s , k /= 2){
- for(int i = l >> s ; i <= r >> s ; ++i){
- if(lazy[i] != 0){
- apply(2 * i , lazy[i] , k);
- apply(2 * i + 1 , lazy[i] , k);
- lazy[i] = 0;
- }
- }
- }
- }
- void upd(int l , int r , ll val){
- if(val == 0){
- return;
- }
- push(l , l + 1);
- push(r - 1 , r);
- int l0 = l , r0 = r , k = 1;
- for(l +=n , r += n ; l < r ; l/= 2 , r /= 2 , k *= 2){
- if(l % 2){
- apply(l , val , k);
- ++l;
- }
- if(r % 2){
- --r;
- apply(r , val , k);
- }
- }
- build(l0 , l0 + 1);
- build(r0 - 1 , r0);
- }
- ll query(int l , int r){
- push(l , l + 1);
- push(r - 1 , r);
- ll res = 0;
- for(l += n , r += n ; l < r ; l /= 2 , r /= 2){
- if(l % 2){
- res += 1LL * t[l];
- ++l;
- }
- if(r % 2){
- --r;
- res += 1LL * t[r];
- }
- }
- return res;
- }
- ll query(int p){
- return query(p , p + 1);
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.precision(0);
- int m;
- cin >> n >> m;
- h = sizeof(int) * 8 - __builtin_clz(n);
- vi c(n);
- rep(i , n){
- cin >> c[i];
- }
- SORT(c);
- reverse(all(c));
- rep(i , n){
- t[n + i] = c[i];
- }
- build(0 , n);
- int ans = 0;
- rep(i , m){
- int x;
- cin >> x;
- int val = query(x - 1);
- if(val < 1)break;
- if(query(x) == val){
- int l1 = 0 , r1 = x - 1;
- if(query(0) != val){
- while(r1 - l1 > 1){
- int mid = (r1 + l1) / 2;
- if(query(mid) == val){
- r1 = mid;
- }else{
- l1 = mid;
- }
- }
- }else{
- r1 = 0;
- }
- int l2 = x , r2 = n - 1;
- if(query(n - 1) != val){
- while(r2 - l2 > 1){
- int mid = (r2 + l2) / 2;
- if(query(mid) == val){
- l2 = mid;
- }else{
- r2 = mid;
- }
- }
- }else{
- l2 = n - 1;
- }
- upd(0 , r1 , -1);
- x -= r1;
- upd(l2 - x + 1 , l2 + 1 , -1);
- }else{
- upd(0 , x , -1);
- }
- ++ans;
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement