Submission #203564

#	Time	Username	Problem	Language	Result	Execution time	Memory
203564		MKopchev	Watering can (POI13_kon)	C++14	100 / 100	420 ms	29816 KiB

kon

#include<bits/stdc++.h>
#include "koninc.h"
using namespace std;
const int nmax=3e5+42;
int n,k;
int inp[nmax];
int fenwick[nmax];

int query_fenwick(int pos)
{
    int ret=0;
    while(pos)
    {
        ret=ret+fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}
void update_fenwick(int pos)
{
    while(pos<=n)
    {
        fenwick[pos]++;
        pos=pos+(pos&(-pos));
    }
}

struct info
{
    int maxi,pos;
    int lazy;
};
info tree[4*nmax];

info actual(info l)
{
    l.maxi+=l.lazy;
    l.lazy=0;
    return l;
}
info my_merge(info l,info r)
{
    l=actual(l);
    r=actual(r);
    if(l.maxi>=r.maxi)return l;
    return r;
}

void push(int node)
{
    tree[node*2].lazy+=tree[node].lazy;
    tree[node*2+1].lazy+=tree[node].lazy;
    tree[node].lazy=0;
}
void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].maxi=inp[l];
        tree[node].pos=l;
        tree[node].lazy=0;
        return;
    }
    int av=(l+r)/2;
    build(node*2,l,av);
    build(node*2+1,av+1,r);
    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
void update_lazy(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)
    {
        tree[node].lazy++;
        return;
    }
    push(node);

    int av=(l+r)/2;
    if(lq<=av)update_lazy(node*2,l,av,lq,min(av,rq));
    if(av<rq)update_lazy(node*2+1,av+1,r,max(av+1,lq),rq);
    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void update_idle(int node,int l,int r,int pos)
{
    if(l==r)
    {
        tree[node].maxi=-1e9;
        tree[node].pos=0;
        tree[node].lazy=0;
        return;
    }
    push(node);
    int av=(l+r)/2;
    if(pos<=av)update_idle(node*2,l,av,pos);
    else update_idle(node*2+1,av+1,r,pos);
    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
void podlej(int a, int b)
{
    a++;
    b++;
    update_lazy(1,1,n,a,b);
    while(1)
    {
        info current=actual(tree[1]);
        if(current.maxi<k)return;
        update_fenwick(current.pos);

        update_idle(1,1,n,current.pos);
    }
}

void inicjuj(int n_,int k_,int *D)
{
    n=n_;
    k=k_;
    for(int i=1;i<=n;i++)
        inp[i]=D[i-1];
    k++;
    build(1,1,n);

    podlej(0,n-1);
}

int dojrzale(int a, int b)
{
    a++;
    b++;
    return query_fenwick(b)-query_fenwick(a-1);
}
/*
int D[4]={5,4,3,7};
int main()
{
    inicjuj(4, 6, D);
    cout<<dojrzale(2, 3)<<endl;//1
    podlej(0, 2);
    cout<<dojrzale(1, 2)<<endl;//0
    podlej(2, 3);
    podlej(0, 1);
    cout<<dojrzale(0, 3)<<endl;//3
    return 0;
}
*/

• 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