oj.uz

답안 #203564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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