oj.uz

답안 #716262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716262 2023-03-29T12:06:10 Z sofija6 Watering can (POI13_kon) C++14
100 / 100
 437 ms 30708 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 300010
using namespace std;
int h[MAXN],m,K,N;
struct bit
{
    vector<ll> v;
    void Init()
    {
        v.resize(N+2);
    }
    void Add(int pos,int val)
    {
        for (int i=pos;i<=N;i+=i&(-i))
            v[i]+=val;
    }
    int Calc(int pos)
    {
        int ans=0;
        for (int i=pos;i>0;i-=i&(-i))
            ans+=v[i];
        return ans;
    }
    int Query(int l,int r)
    {
        return Calc(r)-Calc(l-1);
    }
};
struct seg_tree
{
    vector<pair<int,int> > st;
    vector<int> lazy;
    void Init()
    {
        m=1;
        while (m<N)
            m <<= 1;
        st.resize(2*m+2);
        lazy.resize(2*m+2);
    }
    pair<int,int> Merge(pair<int,int> x,pair<int,int> y)
    {
        if (x.first<y.first)
            return y;
        return x;
    }
    void Build()
    {
        for (int i=m;i<m+N;i++)
            st[i]={h[i-m+1],i-m+1};
        for (int i=m-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    void Propagate(int x,int lx,int rx)
    {
        st[x].first+=lazy[x];
        if (lx!=rx)
        {
            lazy[2*x]+=lazy[x];
            lazy[2*x+1]+=lazy[x];
        }
        lazy[x]=0;
    }
    void Add(int l,int r,int val,int x,int lx,int rx)
    {
        Propagate(x,lx,rx);
        if (lx>r || rx<l)
            return;
        if (lx>=l && rx<=r)
        {
            lazy[x]+=val;
            Propagate(x,lx,rx);
            return;
        }
        ll mid=(lx+rx)/2;
        Add(l,r,val,2*x,lx,mid);
        Add(l,r,val,2*x+1,mid+1,rx);
        st[x]=Merge(st[2*x],st[2*x+1]);
    }
    pair<int,int> Calc(int l,int r,int x,int lx,int rx)
    {
        Propagate(x,lx,rx);
        if (lx>r || rx<l)
            return {0,0};
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
bit B;
void inicjuj(int n, int k, int *D)
{
    N=n;
    K=k;
    for (int i=0;i<n;i++)
        h[i+1]=D[i];
    S.Init();
    S.Build();
    B.Init();
}
void podlej(int a, int b)
{
    S.Add(a+1,b+1,1,1,1,m);
}
int dojrzale(int a, int b)
{
    while (S.Calc(1,N,1,1,m).first>=K)
    {
        pair<int,int> maxx=S.Calc(1,N,1,1,m);
        B.Add(maxx.second,1);
        S.Add(maxx.second,maxx.second,INT_MIN,1,1,m);
    }
    return B.Query(a+1,b+1);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1480 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 2764 KB Output is correct
2 Correct 54 ms 4000 KB Output is correct
3 Correct 39 ms 4300 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 3656 KB Output is correct
2 Correct 68 ms 3572 KB Output is correct
3 Correct 84 ms 5928 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 5920 KB Output is correct
2 Correct 126 ms 8792 KB Output is correct
3 Correct 104 ms 7500 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 6756 KB Output is correct
2 Correct 127 ms 10828 KB Output is correct
3 Correct 211 ms 11764 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 6884 KB Output is correct
2 Correct 208 ms 15016 KB Output is correct
3 Correct 197 ms 13704 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 11240 KB Output is correct
2 Correct 383 ms 18576 KB Output is correct
3 Correct 416 ms 21568 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 18544 KB Output is correct
2 Correct 318 ms 29308 KB Output is correct
3 Correct 437 ms 29976 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 368 ms 18752 KB Output is correct
2 Correct 355 ms 30708 KB Output is correct
3 Correct 431 ms 29920 KB Output is correct