oj.uz

Submission #716216

# Submission time Handle Problem Language Result Execution time Memory
716216 2023-03-29T09:21:00 Z sofija6 Watering can (POI13_kon) C++14
0 / 100
 4000 ms 22944 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 300010
using namespace std;
int h[MAXN],m,K,N;
struct seg_tree
{
    struct element
    {
        int sum=0,maxx=0;
    };
    vector<element> st;
    element neutral_element;
    vector<int> lazy;
    int no_operation=-1;
    void Init()
    {
        m=1;
        while (m<N)
            m <<= 1;
        st.resize(2*m+2);
        lazy.resize(2*m+2);
    }
    void Propagate(int x,int lx,int rx)
    {
        if (lazy[x]==no_operation)
            return;
        st[x].maxx+=lazy[x];
        if (lx!=rx)
        {
            lazy[2*x]=lazy[x];
            lazy[2*x+1]=lazy[x];
        }
        else if (st[x].maxx>=K)
            st[x].sum=1;
        lazy[x]=no_operation;
    }
    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]={st[2*x].sum+st[2*x+1].sum,max(st[2*x].maxx,st[2*x+1].maxx)};
    }
    int Calc(int l,int r,int x,int lx,int rx)
    {
        Propagate(x,lx,rx);
        if (lx>r || rx<l)
            return 0;
        if (lx>=l && rx<=r && ((st[x].maxx>=K && st[x].sum==rx-lx+1) || st[x].maxx<K))
            return st[x].sum;
        int mid=(lx+rx)/2;
        return Calc(l,r,2*x,lx,mid)+Calc(l,r,2*x+1,mid+1,rx);
    }
};
seg_tree S;
void inicjuj(int n, int k, int *D)
{
    N=n;
    K=k;
    S.Init();
    for (int i=0;i<n;i++)
    {
        h[i+1]=D[i];
        S.Add(i+1,i+1,D[i],1,1,m);
    }
}
void podlej(int a, int b)
{
    S.Add(a+1,b+1,1,1,1,m);
}
int dojrzale(int a, int b)
{
    return S.Calc(a+1,b+1,1,1,m);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1721 ms 4212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2514 ms 5748 KB Output is correct
2 Incorrect 132 ms 5664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 7420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4042 ms 10312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 7524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4037 ms 14668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4014 ms 18800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 22944 KB Time limit exceeded
2 Halted 0 ms 0 KB -