oj.uz

Submission #540520

# Submission time Handle Problem Language Result Execution time Memory
540520 2022-03-20T15:54:50 Z Tadiorn Watering can (POI13_kon) C++14
0 / 100
 326 ms 28972 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
using namespace std;
#define MAXN 300010

pii seg[4*MAXN];
int lazy[4*MAXN];
int bit[MAXN];
int a[MAXN];
int N, K;

void init(int node, int l, int r){
    if(l == r){
        seg[node] = {a[l], l};
        return;
    }
    int mid = (l+r)/2;
    init(2*node, l, mid); init(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
void propagate(int node, int l, int r){
    if(!lazy[node]) return;
    if(l == r){
        seg[node].fi += lazy[node];
        lazy[node] = 0;
        return;
    }
    seg[node].fi += lazy[node];
    lazy[2*node]++; lazy[2*node+1]++;
    lazy[node] = 0;
}

void update(int node, int l, int r, int L, int R){
    propagate(node, l, r);
    if(L <= l && r <= R){
        lazy[node] = 1;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    if(L <= mid) update(2*node, l, mid, L, R);
    if(R > mid) update(2*node+1, mid+1, r, L, R);
    propagate(2*node, l, mid); propagate(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}
void update2(int node, int l, int r, int idx){
    propagate(node, l, r);
    if(l == r){
        seg[node].fi = -INF;
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid) update2(2*node, l, mid, idx);
    else update2(2*node+1, mid+1, r, idx);
    propagate(2*node, l, mid); propagate(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}

void updateBIT(int idx){
    while(idx < MAXN){
        bit[idx]++;
        idx += idx&(-idx);
    }
}
int queryBIT(int idx){
    int sum = 0;
    while(idx > 0){
        sum += bit[idx];
        idx -= idx&(-idx);
    }
    return sum;
}

void inicjuj(int n, int k, int *D){
    for(int i = 0; i < n; i++){
        a[i+1] = D[i];
    }
    init(1, 1, n);
    N = n, K = k;
    while(seg[1].fi >= K){
        updateBIT(seg[1].se);
        update2(1, 1, N, seg[1].se);
    }
}

void podlej(int a, int b){
    a++, b++;
    update(1, 1, N, a, b);

    /*cout << endl;
    cout << seg[1].fi << endl;
    cout << seg[2].fi << " " << seg[3].fi << endl;
    cout << seg[4].fi << " " << seg[5].fi << " " << seg[6].fi << " " << seg[7].fi << endl;
    cout << lazy[1]  << endl;
    cout << lazy[2]  << " " << lazy[3]  << endl;
    cout << lazy[4]  << " " << lazy[5]  << " " << lazy[6]  << " " << lazy[7]  << endl << endl;*/
    while(seg[1].fi >= K){
        updateBIT(seg[1].se);
        update2(1, 1, N, seg[1].se);
    }
    /*cout << seg[1].fi << endl;
    cout << seg[2].fi << " " << seg[3].fi << endl;
    cout << seg[4].fi << " " << seg[5].fi << " " << seg[6].fi << " " << seg[7].fi << endl;
    cout << lazy[1]  << endl;
    cout << lazy[2]  << " " << lazy[3]  << endl;
    cout << lazy[4]  << " " << lazy[5]  << " " << lazy[6]  << " " << lazy[7]  << endl << endl;*/
}

int dojrzale(int a, int b){
    a++, b++;
    return queryBIT(b) - (a == 1 ? 0 : queryBIT(a-1));
}
/*
int main(){
    int n = 4;
    int k = 6;
    int D[4] = {5, 4, 3, 7};
    inicjuj(n, k, D);
    cout << seg[1].fi << endl;
    cout << seg[2].fi << " " << seg[3].fi << endl;
    cout << seg[4].fi << " " << seg[5].fi << " " << seg[6].fi << " " << seg[7].fi << endl
    cout << dojrzale(2, 3) << endl;
    cout << "PODLEJ 0 2" << endl;
    podlej(0, 2);
    cout << dojrzale(1, 2) << endl;
    cout << "PODLEJ 2 3" << endl;
    podlej(2, 3);
    cout << "PODLEJ 0 1" << endl;
    podlej(0, 1);
    cout << dojrzale(0, 3) << endl;


    return 0;
}*/

Subtask #1
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 Incorrect 1 ms 1484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5744 KB Output is correct
2 Incorrect 81 ms 5840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 8628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 12544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 12964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 19336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 28620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 28972 KB Output isn't correct
2 Halted 0 ms 0 KB -