Submission #298985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
298985	2020-09-14T11:37:56 Z	mat_v	Watering can (POI13_kon)	C++14	100 / 100	637 ms	18808 KB

#include "koninc.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define maxn 300005
#define pii pair<int,int>
#define pb push_back
#define xx first
#define yy second
#define MAXN 3005

using namespace std;


int N, K;

int seg[4 * maxn];
int idx[4 * maxn];
int lejzi[4 * maxn];
int niz[maxn];

void propagate(int node, int l, int r){
    if(lejzi[node]){
        if(l != r){
            lejzi[node * 2] += lejzi[node];
            lejzi[node * 2 + 1] += lejzi[node];
        }
        seg[node] += lejzi[node];
        lejzi[node] = 0;
    }
}

void init(int node, int l, int r){
    //cout << node << " " << l << " " << r << "\n";
    if(l == r){
        seg[node] = niz[l];
        idx[node] = l;
        return;
    }
    int mid = (l + r) / 2;
    init(node * 2, l, mid);
    init(node * 2 + 1, mid + 1, r);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
    if(seg[node * 2] > seg[node * 2 + 1])idx[node] = idx[node * 2];
    else idx[node] = idx[node * 2 + 1];
}

void apdejt(int node, int l, int r, int levo, int desno, int val){
    propagate(node, l, r);
    if(r < levo || l > desno)return;
    if(l >= levo && r <= desno){
        lejzi[node] += val;
        propagate(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    apdejt(node * 2, l, mid, levo, desno, val);
    apdejt(node * 2 + 1, mid + 1, r, levo, desno, val);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
    if(seg[node * 2] > seg[node * 2 + 1])idx[node] = idx[node * 2];
    else idx[node] = idx[node * 2 + 1];
}

pii query(int node, int l, int r, int levo, int desno){
    if(l >= levo && r <= desno)return {seg[node], idx[node]};
    if(r < levo || l > desno)return {-1e9, 1};
    int mid = (l + r) / 2;
    return max(query(node * 2, l, mid, levo, desno), query(node * 2 + 1, mid + 1, r, levo, desno));
}

int bit[maxn];


void apdejtbit(int x){
    while(x <= N){
        bit[x]++;
        x += (x&-x);
    }
}

int kveribit(int x){
    int res = 0;
    while(x > 0){
        res += bit[x];
        x -= (x&-x);
    }
    return res;
}


void namesti(int le, int ri){
    while(1){
        pii sta = query(1,1,N,le,ri);
        if(sta.xx < 0)break;
        apdejtbit(sta.yy);
        apdejt(1,1,N,sta.yy,sta.yy,-1e9-sta.xx);
    }
}

void inicjuj(int n, int k, int *D)
{
    N = n, K = k;
    for(int i=0; i<n; i++){
        niz[i + 1] = D[i] - k;
    }
    ff(i,1,n){
        if(niz[i] >= 0){
            niz[i] = -1e9;
            apdejtbit(i);
        }
    }
    init(1,1,n);
}

void podlej(int a, int b)
{
    a++;
    b++;
    apdejt(1,1,N,a,b,1);
    namesti(a,b);
}

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

Compilation message

kon.cpp: In function 'void inicjuj(int, int, int*)':
kon.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
kon.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,1,n){
      |     ^~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	5 ms	512 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	2512 KB	Output is correct
2	Correct	68 ms	2168 KB	Output is correct
3	Correct	54 ms	2296 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	3384 KB	Output is correct
2	Correct	126 ms	3320 KB	Output is correct
3	Correct	108 ms	3320 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	131 ms	5624 KB	Output is correct
2	Correct	100 ms	5496 KB	Output is correct
3	Correct	150 ms	3832 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	6520 KB	Output is correct
2	Correct	155 ms	6008 KB	Output is correct
3	Correct	310 ms	5624 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	303 ms	6520 KB	Output is correct
2	Correct	285 ms	9400 KB	Output is correct
3	Correct	276 ms	6008 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	409 ms	11128 KB	Output is correct
2	Correct	542 ms	10072 KB	Output is correct
3	Correct	584 ms	10724 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	563 ms	18424 KB	Output is correct
2	Correct	411 ms	18552 KB	Output is correct
3	Correct	557 ms	16760 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	546 ms	18260 KB	Output is correct
2	Correct	438 ms	18808 KB	Output is correct
3	Correct	637 ms	16632 KB	Output is correct