답안 #540520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	1624 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	48 ms	4204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	85 ms	8628 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	168 ms	12544 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	216 ms	12964 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	294 ms	19336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	311 ms	28620 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	326 ms	28972 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

답안 #540520

Compilation message