제출 #1224750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224750		PVM_pvm	식물 비교 (IOI20_plants)	C++20	27 / 100	294 ms	18224 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
int prm[MAXN];
struct node
{
    int mks;
    int lm,rm;
    int bdf,bdfi;
    int lazy;
} seg[4*MAXN];
vector<int> rr;
void Push(int ind, bool ps)
{
    if (seg[ind].lazy==0) return;
    seg[ind].mks+=seg[ind].lazy;
    if (!ps)
    {
        seg[ind].lazy=0;
        return;
    }
    seg[ind*2].lazy+=seg[ind].lazy;
    seg[ind*2+1].lazy+=seg[ind].lazy;
    seg[ind].lazy=0;
}
void Merge(int ind, int l, int r)
{
    Push(ind,1);
    Push(ind*2,l!=(r-1));
    Push(ind*2+1,l!=(r-1));
    seg[ind].mks=max(seg[ind*2].mks,seg[ind*2+1].mks);
    if (seg[ind*2].mks!=seg[ind].mks)
    {
        ///copiram ot desniq
        seg[ind].lm=seg[ind*2+1].lm;
        seg[ind].rm=seg[ind*2+1].rm;
        seg[ind].bdf=seg[ind*2+1].bdf;
        seg[ind].bdfi=seg[ind*2+1].bdfi;
        return;
    }
    if (seg[ind*2+1].mks!=seg[ind].mks)
    {
        ///copiram ot leviq
        seg[ind].lm=seg[ind*2].lm;
        seg[ind].rm=seg[ind*2].rm;
        seg[ind].bdf=seg[ind*2].bdf;
        seg[ind].bdfi=seg[ind*2].bdfi;
        return;
    }
    ///actuali merge
    seg[ind].lm=seg[ind*2].lm;
    seg[ind].rm=seg[ind*2+1].rm;
    if (seg[ind*2].bdf>seg[ind*2+1].bdf)
    {
        seg[ind].bdf=seg[ind*2].bdf;
        seg[ind].bdfi=seg[ind*2].bdfi;
    }
    else
    {
        seg[ind].bdf=seg[ind*2+1].bdf;
        seg[ind].bdfi=seg[ind*2+1].bdfi;
    }
    if ((seg[ind*2+1].lm-seg[ind*2].rm)>seg[ind].bdf)
    {
        seg[ind].bdf=seg[ind*2+1].lm-seg[ind*2].rm;
        seg[ind].bdfi=seg[ind*2+1].lm;
    }
}
void Initialise(int ind, int l, int r)
{
    if (l==r)
    {
        seg[ind].mks=rr[l];
        seg[ind].lm=l;
        seg[ind].rm=l;
        seg[ind].lazy=0;
        seg[ind].bdf=-1;
        seg[ind].bdfi=-1;
        return;
    }
    int mid=(l+r)/2;
    Initialise(ind*2,l,mid);
    Initialise(ind*2+1,mid+1,r);
    Merge(ind,l,r);
}
void Update(int ind, int l, int r, int ql, int qr)
{
    Push(ind,l!=r);
    if (ql<=l && qr>=r)
    {
        seg[ind].lazy+=1;
        Push(ind,l!=r);
        return;
    }
    int mid=(l+r)/2;
    if (ql<=mid) Update(ind*2,l,mid,ql,qr);
    if (qr>=mid+1) Update(ind*2+1,mid+1,r,ql,qr);
    Merge(ind,l,r);
}
void Make0(int ind, int l, int r, int ch)
{
    Push(ind,l!=r);
    if (l==r && l==ch)
    {
        seg[ind].mks=0;
        seg[ind].lm=l;
        seg[ind].rm=l;
        seg[ind].lazy=0;
        seg[ind].bdf=-1;
        seg[ind].bdfi=-1;
        return;
    }
    int mid=(l+r)/2;
    if (ch<=mid) Make0(ind*2,l,mid,ch);
    else Make0(ind*2+1,mid+1,r,ch);
    Merge(ind,l,r);
}
void init(int k, vector<int> r) {
    int n=r.size();
    rr=r;
    Initialise(1,0,n-1);
    for (int st=0;st<n;st++)
    {
        int spec=-1;
        if (seg[1].bdf>=k)
        {
            spec=seg[1].bdfi;
            //cout<<"edno\n";
        }
        else
        {
            spec=seg[1].lm;
            //cout<<"dve\n";
        }
        prm[spec]=st;
        //cout<<spec<<" "<<st<<"\n";
        if (spec>=k-1)
        {
            Update(1,0,n-1,spec-k+1,spec-1);
            //cout<<spec-k+1<<" "<<spec-1<<" e dob\n";
        }
        else
        {
            if (spec!=0) Update(1,0,n-1,0,spec-1);
            int klk=(k-1)-spec;
            Update(1,0,n-1,n-klk,n-1);
            //if (spec!=0) cout<<0<<" "<<spec-1<<" e dob\n";
            //cout<<n-klk<<" "<<n-1<<" e dob\n";
        }
        Make0(1,0,n-1,spec);
    }
    //for (int q=0;q<n;q++) cout<<prm[q]<<" ";
	return;
}

int compare_plants(int x, int y) {
	if (prm[x]>prm[y]) return 1;
	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