oj.uz

Submission #866216

# Submission time Handle Problem Language Result Execution time Memory
866216 2023-10-25T15:30:49 Z andrei_boaca Comparing Plants (IOI20_plants) C++17
5 / 100
 80 ms 16476 KB 
#include "plants.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
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<int> 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(int K, std::vector<int> 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;
            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);
            }
        }
    }
}
int compare_plants(int x, int 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 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10424 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 48 ms 13088 KB Output is correct
7 Correct 52 ms 13352 KB Output is correct
8 Correct 77 ms 15168 KB Output is correct
9 Correct 74 ms 15148 KB Output is correct
10 Correct 72 ms 15044 KB Output is correct
11 Correct 67 ms 15188 KB Output is correct
12 Correct 70 ms 15212 KB Output is correct
13 Correct 75 ms 15172 KB Output is correct
14 Correct 80 ms 15180 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10328 KB Output is correct
2 Correct 2 ms 10500 KB Output is correct
3 Incorrect 3 ms 16476 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 10328 KB Output is correct
2 Correct 2 ms 10500 KB Output is correct
3 Incorrect 3 ms 16476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Incorrect 3 ms 16476 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 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Incorrect 3 ms 16472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Incorrect 3 ms 16476 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 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10424 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 48 ms 13088 KB Output is correct
7 Correct 52 ms 13352 KB Output is correct
8 Correct 77 ms 15168 KB Output is correct
9 Correct 74 ms 15148 KB Output is correct
10 Correct 72 ms 15044 KB Output is correct
11 Correct 67 ms 15188 KB Output is correct
12 Correct 70 ms 15212 KB Output is correct
13 Correct 75 ms 15172 KB Output is correct
14 Correct 80 ms 15180 KB Output is correct
15 Correct 3 ms 10328 KB Output is correct
16 Correct 2 ms 10500 KB Output is correct
17 Incorrect 3 ms 16476 KB Output isn't correct
18 Halted 0 ms 0 KB -