Submission #1268984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268984		abdelhakim	Comparing Plants (IOI20_plants)	C++20	44 / 100	797 ms	31016 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"
#define ll long long
#define inf (ll) 1e17
#define dbg(x) cerr << #x << ' ' << x << endl;
using namespace std;
vector<ll> p;
ll n;
void printvec(vector<ll>& vec)
{
    for (auto &&e : vec)
    {
        cout << e << ' ';   
    }
    
    cout << endl;
}
ll maxn=2e5;
vector<ll> tree(4*maxn+4);
vector<ll> lazy(4*maxn+4);
vector<ll> chajara(4*maxn+4);
vector<ll> kassoul(4*maxn+4);
void prop(ll node, ll l, ll r, vector<ll>& tre, vector<ll>& laz)
{
    tre[node]+=laz[node];
    if(l==r)
    {
        laz[node]=0;
        return;
    }
    laz[node*2+1]+=laz[node];
    laz[node*2+2]+=laz[node];
    laz[node]=0;
}
void update(ll node, ll l, ll r, ll x, ll y, ll val, vector<ll>& tre, vector<ll>& laz)
{
    prop(node,l, r, tre, laz);
    if(max(l,x) > min(r,y)) return;
    if(x<=l && r<=y)
    {
        laz[node]+=val;
        prop(node,l,r,tre, laz);
        return;
    }
    ll mid=(l+r)/2;
    update(node*2+1,l,mid,x,y,val, tre, laz);
    update(node*2+2,mid+1,r,x,y,val, tre, laz);
    tre[node]=min(tre[node*2+1],tre[node*2+2]);
}
ll query(ll node, ll l, ll r, ll x, ll y, vector<ll>& tre, vector<ll>& laz)
{
    prop(node,l,r, tre, laz);
    if(max(l,x) > min(r,y)) return inf;
    if(x<=l && r<=y)
    {
        return tre[node];
    }
    ll mid=(l+r)>>1;
    return min(query(node*2+1,l,mid,x,y, tre, laz),query(node*2+2,mid+1,r,x,y, tre, laz));
}
void decrease(ll l, ll r)
{
    if(l<=r)
    {
        update(0,0,n-1,l,r,-1,tree, lazy);
    }
    else
    {
        update(0,0,n-1,l,n-1,-1, tree, lazy);
        if(r>=0)
        update(0,0,n-1,0,r,-1, tree, lazy);
    }
}
// ll findsmallest(ll l, ll r, vector<ll>& tre, vector<ll>& laz)
// {
//     ll ans=r+1;
//     ll oldl=l;
//     while(l<=r)
//     {
//         ll mid=(l+r)>>1;
//         ll vl=query(0,0,n-1,oldl,mid, tre, laz);
//         if(vl==0)
//         {
//             ans=mid;
//             r=mid-1;
//         }
//         else
//         {
//             l=mid+1;
//         }
//     }
//     return ans;
// } 
// returns first position in [ql, qr] with value == 0, or (qr+1) if none
ll find_first_zero(ll node, ll l, ll r, ll ql, ll qr,
                   vector<ll>& tre, vector<ll>& laz) {
    prop(node, l, r, tre, laz);
    if (r < ql || qr < l || tre[node] > 0) return qr + 1; // no zero here
    if (l == r) return l;
    ll m = (l + r) >> 1;
    ll left = find_first_zero(node*2+1, l, m, ql, qr, tre, laz);
    if (left <= qr) return left;
    return find_first_zero(node*2+2, m+1, r, ql, qr, tre, laz);
}

void init(int k, std::vector<int> r)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    n=r.size();
    p.resize(n);

    vector<bool> vis(n);
    for (int i=0;i<n;i++)
    {
        r[i]=k-1-r[i];
    }
    for (int i=0;i<n;i++)
    {
        if(r[i]==0)
        {
            if(i+k<=n)
            {
                update(0,0,n-1,i+1,i+k-1,1,chajara, kassoul);
            }
            else
            {
                if(i<n-1)update(0,0,n-1,i+1,n-1,1,chajara,kassoul);
                update(0,0,n-1,0,(i+k-1)%n,1,chajara,kassoul);
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        update(0,0,n-1,i,i,r[i], tree, lazy);
    }
    for (int i=0;i<n;i++)
    {
        
        ll ind = find_first_zero(0, 0, n-1, 0, n-1, tree, lazy);
       
        ll index=ind+k;
        if(ind<n-1) index = find_first_zero(0, 0, n-1, ind+1, n-1, chajara, kassoul);


        if(index<n)
        {
        ll vl  = find_first_zero(0, 0, n-1, index,  n-1, tree,    lazy);
            if(vl!=n)
            {
                ind=vl;
            }
        }
        
        vis[ind]=true;
        update(0,0,n-1,ind,ind,inf,tree,lazy);
        p[ind]=i;
        decrease((ind-k+1+n)%n,ind-1);  
        if(ind+k<=n)
        {
            update(0,0,n-1,ind+1,ind+k-1,-1,chajara, kassoul);
        }
        else
        {
            if(ind<n-1)update(0,0,n-1,ind+1,n-1,-1,chajara,kassoul);
            update(0,0,n-1,0,(ind+k-1)%n,-1,chajara,kassoul);
        }
        ll j=max(0ll,ind-k+1);
        while(j<=ind-1)
        {
            j = find_first_zero(0, 0, n-1, j, ind-1, tree, lazy);
            if(j==ind) break;
            if(j+k<=n)
            {
                update(0,0,n-1,j+1,j+k-1,1,chajara, kassoul);
            }
            else
            {
                if(j<n-1)update(0,0,n-1,j+1,n-1,1,chajara,kassoul);
                update(0,0,n-1,0,(j+k-1)%n,1,chajara,kassoul);
            }
            j++;
        }
        if(ind-k+1 < 0)
        {
            j=ind-k+1+n;
            while(j<n)
            {
                j = find_first_zero(0, 0, n-1, j, n-1, tree, lazy);
                if(j==n) break;
                if(j+k<=n)
                {
                    update(0,0,n-1,j+1,j+k-1,1,chajara, kassoul);
                }
                else
                {
                    if(j<n-1)update(0,0,n-1,j+1,n-1,1,chajara,kassoul);
                    update(0,0,n-1,0,(j+k-1)%n,1,chajara,kassoul);
                }
                j++;
            }
        }
    }
}
int compare_plants(int x, int y)
{
    if(p[x]<p[y]) return -1;
    else return 1;
}

// we can use binary search to find each element when its r is 0, so total complexity is O(nlog(n))

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25