Submission #1230070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230070		peter-007	Comparing Plants (IOI20_plants)	C++20	44 / 100	378 ms	27024 KiB

plants

//#include "plants.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
int nv;
struct seg_tree
{
    vector<pair<int,int>>tree;
    vector<int>lazy;
    void build(int v,int tl,int tr)
    {
        if(tl==tr)
        {
            tree[v]={0,tl};
            return;
        }
        int tm=(tl+tr)/2;
        build(v*2,tl,tm),build(v*2+1,tm+1,tr);
        tree[v]=min(tree[v*2],tree[v*2+1]);
    }
    void push(int v,int tl,int tr)
    {
        tree[v].first+=lazy[v];
        if(tl!=tr)lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
        lazy[v]=0;
    }
    seg_tree(int sz)
    {
        tree.resize(sz*4);
        lazy.resize(sz*4);
        build(1,0,sz-1);
    }
    void update(int l,int r,int val,int v,int tl,int tr)
    {
        push(v,tl,tr);
        if(tr<l||tl>r)return;
        if(tr<=r&&tl>=l)
        {
            lazy[v]+=val;
            push(v,tl,tr);
            return;
        }
        int tm=(tl+tr)/2;
        update(l,r,val,v*2,tl,tm),update(l,r,val,v*2+1,tm+1,tr);
        tree[v]=min(tree[v*2],tree[v*2+1]);
    }
    pair<int,int> min_v()
    {
        push(1,0,tree.size()/4-1);
        return tree[1];
    }
};
struct st_v
{
    priority_queue<pair<int,int>>q;
    set<int>st;
    int back_len(int x)
    {
        auto y=st.lower_bound(x);
        if(y!=st.begin())
        {
            y--;
            return x-*y;
        }
        y=st.end();
        y--;
        return nv-*y+x;
    }
    void insert(int x)
    {
        st.insert(x);
        q.push({back_len(x),x});
        auto y=st.lower_bound(x);
        y++;
        if(y==st.end())y=st.begin();
        q.push({back_len(*y),*y});
    }
    int ret_back()
    {
        while(q.size())
        {
            auto x=q.top();
            q.pop();
            if(!st.count(x.second)||back_len(x.second)!=x.first)continue;
            st.erase(x.second);
            if(st.size())
            {
                auto it=st.lower_bound(x.second);
                if(it==st.end())it=st.begin();
                q.push({back_len(*it),*it});
            }
            return x.second;
        }
    }
};
vector<int>ans;
void init(int k,vector<int>a)
{
    k--;
    st_v v;
    nv=a.size();
    ans.resize(nv);
    int n=nv;
    seg_tree st(n);
    for(int i=0;i<n;i++)st.update(i,i,a[i],1,0,n-1);
    while(st.min_v().first==0)
    {
        v.insert(st.min_v().second);
        st.update(st.min_v().second,st.min_v().second,1000000,1,0,n-1);
    }
    for(int i=0;i<n;i++)
    {
        while(st.min_v().first==0)
        {
            v.insert(st.min_v().second);
            st.update(st.min_v().second,st.min_v().second,1000000,1,0,n-1);
        }
        int x=v.ret_back();
        ans[x]=n-i-1;
        int l=x-k,r=x-1;
        st.update(max(0,l),r,-1,1,0,n-1);
        st.update(n+l,n-1,-1,1,0,n-1);
    }
}
int compare_plants(int x,int y)
{
    return (ans[x]<ans[y]?-1:1);
}

Compilation message (stderr)

plants.cpp: In member function 'int st_v::ret_back()':
plants.cpp:100:5: warning: control reaches end of non-void function [-Wreturn-type]
  100 |     }
      |     ^

• 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