oj.uz

Submission #678813

# Submission time Handle Problem Language Result Execution time Memory
678813 2023-01-06T15:51:24 Z Ahmed57 Watering can (POI13_kon) C++14
100 / 100
 383 ms 40744 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3340 KB Output is correct
2 Correct 41 ms 3148 KB Output is correct
3 Correct 33 ms 3272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6604 KB Output is correct
2 Correct 77 ms 7168 KB Output is correct
3 Correct 80 ms 7244 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10424 KB Output is correct
2 Correct 76 ms 11240 KB Output is correct
3 Correct 86 ms 8628 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 13724 KB Output is correct
2 Correct 108 ms 13356 KB Output is correct
3 Correct 188 ms 14032 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 14228 KB Output is correct
2 Correct 184 ms 20064 KB Output is correct
3 Correct 230 ms 15676 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 22468 KB Output is correct
2 Correct 305 ms 23072 KB Output is correct
3 Correct 344 ms 26072 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 36684 KB Output is correct
2 Correct 302 ms 39280 KB Output is correct
3 Correct 332 ms 39872 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 37068 KB Output is correct
2 Correct 322 ms 40744 KB Output is correct
3 Correct 383 ms 39556 KB Output is correct