oj.uz

Submission #866222

# Submission time Handle Problem Language Result Execution time Memory
866222 2023-10-25T15:35:10 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
5 / 100
 75 ms 18272 KB 
#include "plants.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#define int long long
using namespace std;
typedef long long ll;
vector<int> muchii[200005];
int n,bigger[200005],smaller[200005],lastsmall[200005],lastbig[200005],k,v[200005];
bool use[200005];
ll mars[500005],can[500005];
vector<signed> R;
int dist(int a,int b)
{
    return (b-a+n)%n;
}
int myprv(int x)
{
    return (x-1+n)%n;
}
struct aint
{
    int maxim,minim,pozmax,pozmin;
    int toprop;
} arb[3][4*200005];
vector<int> who;
aint combine(aint a,aint b)
{
    aint rez;
    rez.toprop=0;
    rez.maxim=a.maxim;
    rez.pozmax=a.pozmax;
    if(b.maxim>rez.maxim)
    {
        rez.maxim=b.maxim;
        rez.pozmax=b.pozmax;
    }

    rez.minim=a.minim;
    rez.pozmin=a.pozmin;
    if(b.minim<rez.minim)
    {
        rez.minim=b.minim;
        rez.pozmin=b.pozmin;
    }
    return rez;
}
void prop(int ind,int nod)
{
    int val=arb[ind][nod].toprop;
    arb[ind][nod*2].toprop+=val;
    arb[ind][nod*2].maxim+=val;
    arb[ind][nod*2].minim+=val;

    arb[ind][nod*2+1].toprop+=val;
    arb[ind][nod*2+1].maxim+=val;
    arb[ind][nod*2+1].minim+=val;
}
void build(int ind,int nod,int st,int dr)
{
    arb[ind][nod].toprop=0;
    if(st==dr)
    {
        arb[ind][nod].minim=arb[ind][nod].maxim=R[st]*(ind==1);
        arb[ind][nod].pozmin=arb[ind][nod].pozmax=st;
        return;
    }
    int mij=(st+dr)/2;
    build(ind,nod*2,st,mij);
    build(ind,nod*2+1,mij+1,dr);
    arb[ind][nod]=combine(arb[ind][nod*2],arb[ind][nod*2+1]);
}
void update(int ind,int nod,int st,int dr,int a,int b,int val)
{
    if(st!=dr)
        prop(ind,nod);
    arb[ind][nod].toprop=0;
    if(st>=a&&dr<=b)
    {
        arb[ind][nod].maxim+=val;
        arb[ind][nod].minim+=val;
        arb[ind][nod].toprop+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(ind,nod*2,st,mij,a,b,val);
    if(b>mij)
        update(ind,nod*2+1,mij+1,dr,a,b,val);
    arb[ind][nod]=combine(arb[ind][nod*2],arb[ind][nod*2+1]);
}
void getwho(int ind,int nod,int st,int dr,int a,int b)
{
    if(st!=dr)
        prop(ind,nod);
    arb[ind][nod].toprop=0;
    if(arb[ind][nod].maxim<k-1)
        return;
    if(st==dr)
    {
        who.push_back(st);
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        getwho(ind,nod*2,st,mij,a,b);
    if(b>mij)
        getwho(ind,nod*2+1,mij+1,dr,a,b);
}
void plsadd(int ind,int st,int lg,int val)
{
    if(st+lg-1<=n-1)
    {
        update(ind,1,0,n-1,st,st+lg-1,val);
        return;
    }
    update(ind,1,0,n-1,st,n-1,val);
    update(ind,1,0,n-1,0,(st+lg-1)%n,val);
}
void guesswho(int ind,int st,int lg)
{
    who.clear();
    if(st+lg-1<=n-1)
    {
        getwho(ind,1,0,n-1,st,st+lg-1);
        return;
    }
    getwho(ind,1,0,n-1,st,n-1);
    getwho(ind,1,0,n-1,0,(st+lg-1)%n);
}
void init(signed K, std::vector<signed> r)
{
    R=r;
    n=r.size();
    k=K;
    for(int i=0;i<n;i++)
    {
        lastbig[i]=-1;
        lastsmall[i]=-1;
    }
    for(int i=0;i<n;i++)
    {
        if(r[i]==0)
        {
            int j=(i-1+n)%n;
            while(r[j]==1)
            {
                lastsmall[j]=i;
                j=(j-1+n)%n;
            }
        }
        if(r[i]==1)
        {
            int j=(i-1+n)%n;
            while(r[j]==0)
            {
                lastbig[j]=i;
                j=(j-1+n)%n;
            }
        }
    }
    if(k>2)
    {
        build(1,1,0,n-1);
        build(2,1,0,n-1);
        for(int i=0;i<n;i++)
        {
            if(r[i]==k-1)
                plsadd(2,(i+1)%n,k-1,1);
            else
                plsadd(2,i,1,1);
        }
        for(int value=1;value<=n;value++)
        {
            int poz=arb[2][1].pozmin;
            v[poz]=value;
            cout<<poz<<' ';
            plsadd(2,poz,1,1e6);
            plsadd(2,(poz+1)%n,k-1,-1);
            int p=(poz-(k-1)+n)%n;
            plsadd(1,p,k-1,1);
            guesswho(1,(poz+1)%n,k-1);
            for(auto i:who)
            {
                plsadd(2,i,1,-1);
                plsadd(2,(i+1)%n,k-1,1);
            }
        }
    }
}
signed compare_plants(signed x, signed y)
{
    if(k==2)
    {
        if(lastsmall[x]!=-1&&dist(x,y)+dist(y,lastsmall[x])==dist(x,lastsmall[x]))
            return -1;
        if(lastbig[x]!=-1&&dist(x,y)+dist(y,lastbig[x])==dist(x,lastbig[x]))
            return 1;
        if(lastsmall[y]!=-1&&dist(y,x)+dist(x,lastsmall[y])==dist(y,lastsmall[y]))
            return 1;
        if(lastbig[y]!=-1&&dist(y,x)+dist(x,lastbig[y])==dist(y,lastbig[y]))
            return -1;
        return 0;
    }
    if(v[x]<v[y])
        return -1;
    if(v[x]>v[y])
        return 1;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 11936 KB Output is correct
4 Correct 2 ms 12124 KB Output is correct
5 Correct 2 ms 12140 KB Output is correct
6 Correct 51 ms 15020 KB Output is correct
7 Correct 53 ms 15196 KB Output is correct
8 Correct 66 ms 16724 KB Output is correct
9 Correct 65 ms 16784 KB Output is correct
10 Correct 65 ms 16712 KB Output is correct
11 Correct 65 ms 16728 KB Output is correct
12 Correct 69 ms 16724 KB Output is correct
13 Correct 75 ms 16720 KB Output is correct
14 Correct 65 ms 16820 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Incorrect 3 ms 18268 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Incorrect 3 ms 18268 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Incorrect 3 ms 18272 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Incorrect 3 ms 18268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 11936 KB Output is correct
4 Correct 2 ms 12124 KB Output is correct
5 Correct 2 ms 12140 KB Output is correct
6 Correct 51 ms 15020 KB Output is correct
7 Correct 53 ms 15196 KB Output is correct
8 Correct 66 ms 16724 KB Output is correct
9 Correct 65 ms 16784 KB Output is correct
10 Correct 65 ms 16712 KB Output is correct
11 Correct 65 ms 16728 KB Output is correct
12 Correct 69 ms 16724 KB Output is correct
13 Correct 75 ms 16720 KB Output is correct
14 Correct 65 ms 16820 KB Output is correct
15 Correct 3 ms 12124 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Incorrect 3 ms 18268 KB Output isn't correct
18 Halted 0 ms 0 KB -