oj.uz

답안 #678812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678812 2023-01-06T15:50:00 Z Ahmed57 Watering can (POI13_kon) C++14
30 / 100
 4000 ms 12116 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[30000*4+1];
pair<long long,long long> seg[30000*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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 1 ms 1480 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4848 KB Output is correct
2 Correct 60 ms 4724 KB Output is correct
3 Correct 37 ms 4788 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4083 ms 4920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 11732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 12116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 12036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 5040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 5800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 5816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -