Submission #678813

#	Time	Username	Problem	Language	Result	Execution time	Memory
678813		Ahmed57	Watering can (POI13_kon)	C++14	100 / 100	383 ms	40744 KiB

kon

#include <bits/stdc++.h>

using namespace std;
int lim = 300000;
int bit[300001]={0};
void add(int e,int v){
    while(e<=lim){
        bit[e]+=v;
        e+=e&-e;
    }
}
long long sum(int e){
    long long res = 0;
    while(e>=1){
        res+=bit[e];
        e -= e&-e;
    }
    return res;
}
long long lazy[300000*4+1];
pair<long long,long long> seg[300000*4+1];
pair<long long,long long> ma(pair<long long,long long> a,pair<long long,long long> b){
    if(a.first>b.first)return a;
    else return b;
}
void init(int node, int l, int r) {
    if(l == r) {
        seg[node] = {0, l};
        return;
    }
    int mid = (l+r)/2;
    init(2*node, l, mid); init(2*node+1, mid+1, r);
    seg[node] = ma(seg[2*node], seg[2*node+1]);
}
void prob(int p,int l,int r){
    seg[p].first+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val){
    prob(p,l,r);
    if(r < l || rq < lq || r < lq || rq < l) return;
    if(lq<=l&&rq>=r){
        lazy[p] += val;
        prob(p,l,r);
        return;
    }
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);
    update(p*2+1,md+1,r,lq,rq,val);
    seg[p] = ma(seg[p*2],seg[p*2+1]);
}
pair<long long,long long> query(int p,int l,int r,int lq,int rq){
    prob(p,l,r);
    if(r<lq||l>rq)return {-1e9,-1e9};
    if(lq<=l&&rq>=r)return seg[p];
    int md = (l+r)/2;
    return ma(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int N , K;
void inicjuj(int n,int k,int *D){
    K = k;
    N = n;
    init(1,1,n);
    for(int i = 1;i<=n;i++){
        if(D[i-1]>=k){
            update(1,1,n,i,i,-1e9);
            add(i,1);
            continue;
        }
        update(1,1,n,i,i,D[i-1]);
    }
}
void podlej(int a,int b){
    a++;b++;
    update(1,1,N,a,b,1);
    pair<long long,long long> y = query(1,1,N,1,N);
    while(y.first>=K){
        add(y.second,1);
        update(1,1,N,y.second,y.second,-1e9);
        y = query(1,1,N,1,N);
    }
}
int dojrzale(int a, int b){
    a++; b++;
    return sum(b)-sum(a-1);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10