Submission #298985

#	Time	Username	Problem	Language	Result	Execution time	Memory
298985		mat_v	Watering can (POI13_kon)	C++14	100 / 100	637 ms	18808 KiB

kon

#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 (stderr)

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