Submission #203564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
203564	2020-02-21T10:27:52 Z	MKopchev	Watering can (POI13_kon)	C++14	100 / 100	420 ms	29816 KB

#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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	248 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	504 KB	Output is correct
2	Correct	8 ms	504 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	3320 KB	Output is correct
2	Correct	54 ms	2936 KB	Output is correct
3	Correct	45 ms	3320 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	4728 KB	Output is correct
2	Correct	85 ms	4856 KB	Output is correct
3	Correct	69 ms	4856 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	7928 KB	Output is correct
2	Correct	100 ms	7544 KB	Output is correct
3	Correct	94 ms	6392 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	11900 KB	Output is correct
2	Correct	128 ms	9720 KB	Output is correct
3	Correct	175 ms	10872 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	12384 KB	Output is correct
2	Correct	213 ms	14092 KB	Output is correct
3	Correct	192 ms	12408 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	19056 KB	Output is correct
2	Correct	368 ms	17656 KB	Output is correct
3	Correct	316 ms	20440 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	420 ms	28676 KB	Output is correct
2	Correct	304 ms	28156 KB	Output is correct
3	Correct	340 ms	28536 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	29048 KB	Output is correct
2	Correct	368 ms	29816 KB	Output is correct
3	Correct	359 ms	28536 KB	Output is correct

Submission #203564

Compilation message