oj.uz

답안 #298981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298981 2020-09-14T11:33:48 Z MladenP Watering can (POI13_kon) C++17
100 / 100
 3432 ms 22264 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lld long long
#define pll pair<lld,lld>
#define all(x) begin(x),end(x)
#define mid ((l+r)/2)
#define sz(x) int((x).size())
#define endl '\n'
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define INF 100000000
#define pb push_back
using namespace std;
#define MAXN 300010

int N, K, bit[MAXN], lazy[4*MAXN];
pii seg[4*MAXN];
void updBIT(int idx, int val) {
    while(idx < MAXN) {
        bit[idx] += val;
        idx += idx&-idx;
    }
}
int queryBIT(int idx) {
    int rez = 0;
    while(idx) {
        rez += bit[idx];
        idx -= idx&-idx;
    }
    return rez;
}
void propagate(int node, int l, int r) {
    if(l == r) {
        seg[node].fi += lazy[node];
        lazy[node] = 0;
        return;
    }
    seg[node].fi += lazy[node];
    lazy[2*node] += lazy[node];
    lazy[2*node+1] += lazy[node];
    lazy[node] = 0;
}
pii query(int node, int l, int r, int L, int R) {
    propagate(node, l, r);
    if(r < l || R < L || r < L || R < l) return {-INF, -INF};
    if(L <= l && r <= R) return seg[node];
    return max(query(2*node, l, mid, L, R), query(2*node+1, mid+1, r, L, R));
}
void update(int node, int l, int r, int L, int R, int val) {
    propagate(node, l, r);
    if(r < l || R < L || r < L || R < l) return;
    if(L <= l && r <= R) {
        lazy[node] += val;
        propagate(node, l, r);
        return;
    }
    update(2*node, l, mid, L, R, val);
    update(2*node+1, mid+1, r, L, R, val);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
void init(int node, int l, int r) {
    if(l == r) {
        seg[node] = {0, l};
        return;
    }
    init(2*node, l, mid); init(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
void inicjuj(int n, int k, int *D)
{
    //PRINT(n);
    N = n, K = k;
    init(1, 1, N);
    //PRINT(22222);
    for(int i = 0; i < N; i++) {
        PRINT(D[i]);
        int idx = i+1;
        if(D[i] >= K) updBIT(idx, +1), update(1, 1, N, idx, idx, -INF);
        else update(1, 1, N, idx, idx, D[i]);
    }
    //PRINT(333333);
}

void podlej(int a, int b)
{
    a++; b++;
    update(1, 1, N, a, b, +1);
    pii rez = query(1, 1, N, 1, N);
    while(rez.fi >= K) {
        update(1, 1, N, rez.se, rez.se, -INF);
        updBIT(rez.se, +1);
        rez = query(1, 1, N, 1, N);
    }
}

int dojrzale(int a, int b)
{
    a++; b++;
    return queryBIT(b)-queryBIT(a-1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 504 KB Output is correct
2 Correct 16 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 2016 KB Output is correct
2 Correct 282 ms 2944 KB Output is correct
3 Correct 263 ms 2872 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 3072 KB Output is correct
2 Correct 534 ms 4216 KB Output is correct
3 Correct 499 ms 3960 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 936 ms 5496 KB Output is correct
2 Correct 814 ms 6540 KB Output is correct
3 Correct 654 ms 4600 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1381 ms 6776 KB Output is correct
2 Correct 838 ms 7032 KB Output is correct
3 Correct 1157 ms 6444 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1457 ms 7116 KB Output is correct
2 Correct 1643 ms 11252 KB Output is correct
3 Correct 1367 ms 7416 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2453 ms 12184 KB Output is correct
2 Correct 2509 ms 12812 KB Output is correct
3 Correct 2514 ms 12024 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3322 ms 20972 KB Output is correct
2 Correct 3191 ms 22116 KB Output is correct
3 Correct 2969 ms 18832 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3263 ms 20952 KB Output is correct
2 Correct 3273 ms 22264 KB Output is correct
3 Correct 3432 ms 18512 KB Output is correct