Submission #540520

#	Time	Username	Problem	Language	Result	Execution time	Memory
540520		Tadiorn	Watering can (POI13_kon)	C++14	0 / 100	326 ms	28972 KiB

kon

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10