Submission #362462

#	Time	Username	Problem	Language	Result	Execution time	Memory
362462		MasterTaster	Watering can (POI13_kon)	C++14	100 / 100	805 ms	42476 KiB

kon

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 300010
#define INF 2000000010

using namespace std;

int N, K, a[MAXN];

int bit[MAXN];
pair<ll, int> seg[4*MAXN];
ll lazy[4*MAXN];

void upd(int x)
{
    while (x<MAXN)
    {
        bit[x]++;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}
void relax(int node, int l, int r)
{
    seg[node].xx+=lazy[node];
    if (l!=r)
    {
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
}
void build(int node, int l, int r)
{
    if (l==r) { seg[node]={a[l], l}; return; }
    int mid=l+(r-l)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node]=max(seg[2*node], seg[2*node+1]);
}
void update(int node, int l, int r, int levo, int desno, int val) ///[l,r]-gde sam u segmentnom; [levo,desno]-query;
{
    relax(node, l, r);
    if (levo>r || desno<l) return;
    if (levo<=l && desno>=r) { lazy[node]+=val; return; }

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

    int mid=l+(r-l)/2;
    return max(query(2*node, l, mid, levo, desno),
               query(2*node+1, mid+1, r, levo, desno));
}

void inicjuj(int n, int k, int *D)
{
    N = n, K = k;
    for (int i = 0; i < n; ++i)
    {
        a[i+1] = D[i];
        if (a[i+1]>=k) { a[i+1]=-INF; upd(i+1); }
    }
    build(1, 1, n);
}

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

    pii maxx=query(1, 1, N, a, b);
    while (maxx.xx>=K)
    {
        upd(maxx.yy);
        update(1, 1, N, maxx.yy, maxx.yy, -INF);
        maxx=query(1, 1, N, a, b);
    }
}

int dojrzale(int a, int b)
{
    a++; b++;
    return sum(b)-sum(a-1);
    //return (t[a] >= K) + (t[b] >= K); /* cos glupiego */
}

• 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