Submission #1268478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268478		abdelhakim	Comparing Plants (IOI20_plants)	C++20	27 / 100	1372 ms	18460 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"
#define ll long long
#define inf (ll) 1e17
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);
void prop(ll node, ll l, ll r)
{
    tree[node]+=lazy[node];
    if(l==r)
    {
        lazy[node]=0;
        return;
    }
    lazy[node*2+1]+=lazy[node];
    lazy[node*2+2]+=lazy[node];
    lazy[node]=0;
}
void update(ll node, ll l, ll r, ll x, ll y, ll val)
{
    prop(node,l,r);
    if(max(l,x) > min(r,y)) return;
    if(x<=l && r<=y)
    {
        lazy[node]+=val;
        prop(node,l,r);
        return;
    }
    ll mid=(l+r)/2;
    update(node*2+1,l,mid,x,y,val);
    update(node*2+2,mid+1,r,x,y,val);
    tree[node]=min(tree[node*2+1],tree[node*2+2]);
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
    prop(node,l,r);
    if(max(l,x) > min(r,y)) return inf;
    if(x<=l && r<=y)
    {
        return tree[node];
    }
    ll mid=(l+r)>>1;
    return min(query(node*2+1,l,mid,x,y),query(node*2+2,mid+1,r,x,y));
}
void decrease(ll l, ll r)
{
    if(l<=r)
    {
        update(0,0,n-1,l,r,-1);
    }
    else
    {
        update(0,0,n-1,l,n-1,-1);
        if(r>=0)
        update(0,0,n-1,0,r,-1);
    }
}
ll findsmallest(ll l, ll r)
{
    ll ans=-1;
    ll oldl=l;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        ll vl=query(0,0,n-1,oldl,mid);
        if(vl==0)
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return ans;
}
void init(int k, std::vector<int> r)
{
    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++)
    {
        update(0,0,n-1,i,i,r[i]);
    }
    for (int i=0;i<n;i++)
    {
        ll ind=findsmallest(0,n-1);
        if(ind+k<n)
        {
            ll vl=findsmallest(ind+k,n-1);
            if(vl!=-1)
            {
                ind=vl;
            }
        }
        vis[ind]=true;
        update(0,0,n-1,ind,ind,inf);
        p[ind]=i;
        decrease((ind-k+1+n)%n,ind-1);  
    }
}
int compare_plants(int x, int y)
{
    if(p[x]<p[y]) return -1;
    else return 1;
}

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