oj.uz

Submission #306054

# Submission time Handle Problem Language Result Execution time Memory
306054 2020-09-24T11:52:56 Z gs18115 Comparing Plants (IOI20_plants) C++14
44 / 100
 1944 ms 87672 KB 
#include"plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
    pi t[mx*4];
    int lz[mx*4];
    void init(int n,int s,int e,vector<int>&v)
    {
        lz[n]=0;
        if(s==e)
        {
            t[n]=pi(v[s],s);
            return;
        }
        int m=s+(e-s)/2;
        init(n*2,s,m,v);
        init(n*2+1,m+1,e,v);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
    inline void put(int n,int p)
    {
        t[n].fi+=p;
        lz[n]+=p;
        return;
    }
    inline void prop(int n)
    {
        if(lz[n]==0)
            return;
        put(n*2,lz[n]);
        put(n*2+1,lz[n]);
        lz[n]=0;
        return;
    }
    void upd(int n,int s,int e,int S,int E,int p)
    {
        if(s>E||S>e)
            return;
        if(S<=s&&e<=E)
            return put(n,p);
        prop(n);
        int m=s+(e-s)/2;
        upd(n*2,s,m,S,E,p);
        upd(n*2+1,m+1,e,S,E,p);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
}st1,st2;
struct seg2
{
    int t[mx*4];
    void init(int n,int s,int e,int v)
    {
        t[n]=v;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        init(n*2,s,m,v);
        init(n*2+1,m+1,e,v);
        return;
    }
    void put(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            t[n]=p;
            return;
        }
        int m=s+(e-s)/2;
        if(x>m)
            put(n*2+1,m+1,e,x,p);
        else
            put(n*2,s,m,x,p);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
    int query(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return inf;
        if(S<=s&&e<=E)
            return t[n];
        int m=s+(e-s)/2;
        return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
    }
}st3;
int ord[mx];
vector<int>ov;
int spa1[mx][20],spd1[mx][20];
int spa2[mx][20],spd2[mx][20];
int n;
void init(int k,vector<int>r)
{
    n=r.size();
    st1.init(1,0,n-1,r);
    st2.init(1,0,n-1,r);
    for(int i=0;i<n;i++)
    {
        while(st2.t[1].fi==0)
        {
            int cur=st2.t[1].se;
            st2.upd(1,0,n-1,cur,cur,inf);
            st1.upd(1,0,n-1,cur+1,cur+k-1,1),st1.upd(1,0,n-1,0,cur+k-1-n,1);
        }
        int cur=st1.t[1].se;
        ord[cur]=i;
        ov.eb(cur);
        st1.upd(1,0,n-1,cur,cur,inf);
        st1.upd(1,0,n-1,cur-k+1+n,n-1,-1),st1.upd(1,0,n-1,cur-k+1,cur-1,-1);
        st1.upd(1,0,n-1,cur+1,cur+k-1,-1),st1.upd(1,0,n-1,0,cur+k-1-n,-1);
        st2.upd(1,0,n-1,cur-k+1+n,n-1,-1),st2.upd(1,0,n-1,cur-k+1,cur-1,-1);
    }
    st3.init(1,0,n-1,n);
    auto get3=[&](const int&p)->int{return min(st3.query(1,0,n-1,p-k+1,p-1),
    st3.query(1,0,n-1,p-k+1+n,n-1));};
    auto get4=[&](const int&p)->int{return min(st3.query(1,0,n-1,p+1,p+k-1),
    st3.query(1,0,n-1,0,p+k-1-n));};
    ov.eb(ord[n]=n);
    for(int i=0;i<20;i++)
        spa1[n][i]=spa2[n][i]=n,spd1[n][i]=spd2[n][i]=0;
    for(int i=n;i-->0;)
    {
        int cur=ov[i];
        int nx=ov[get3(cur)];
        spa1[cur][0]=nx,spd1[cur][0]=nx>cur?1:0;
        nx=ov[get4(cur)];
        spa2[cur][0]=nx,spd2[cur][0]=nx<cur?1:0;
        st3.put(1,0,n-1,cur,i);
    }
    for(int j=0;j<19;j++)
        for(int i=0;i<=n;i++)
            spa1[i][j+1]=spa1[spa1[i][j]][j],
            spd1[i][j+1]=spd1[spa1[i][j]][j]+spd1[i][j],
            spa2[i][j+1]=spa1[spa2[i][j]][j],
            spd2[i][j+1]=spd1[spa2[i][j]][j]+spd2[i][j];
    return;
}
int compare_plants(int x,int y)
{
    int p=1;
    if(ord[x]>ord[y])
        swap(x,y),p=-1;
    int l=x,ld=0;
    int r=x,rd=0;
    for(int i=20;i-->0;)
        if(ord[spa1[l][i]]<=ord[y])
            ld+=spd1[l][i],l=spa1[l][i];
    for(int i=20;i-->0;)
        if(ord[spa2[r][i]]<=ord[y])
            rd+=spd2[r][i],r=spa2[r][i];
    l-=n*min(2,ld),r+=n*min(2,rd);
    for(int i=-1;i<=1;i++)
        if(l+i*n<=y&&y<=r+i*n)
            return p;
    return p;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 8 ms 12928 KB Output is correct
4 Correct 9 ms 12928 KB Output is correct
5 Correct 9 ms 12928 KB Output is correct
6 Correct 14 ms 13312 KB Output is correct
7 Correct 96 ms 17656 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 13 ms 13312 KB Output is correct
10 Correct 122 ms 17656 KB Output is correct
11 Correct 88 ms 17528 KB Output is correct
12 Correct 92 ms 17784 KB Output is correct
13 Correct 95 ms 17656 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 8 ms 12928 KB Output is correct
4 Correct 9 ms 12928 KB Output is correct
5 Correct 9 ms 12928 KB Output is correct
6 Correct 14 ms 13312 KB Output is correct
7 Correct 96 ms 17656 KB Output is correct
8 Correct 10 ms 13056 KB Output is correct
9 Correct 13 ms 13312 KB Output is correct
10 Correct 122 ms 17656 KB Output is correct
11 Correct 88 ms 17528 KB Output is correct
12 Correct 92 ms 17784 KB Output is correct
13 Correct 95 ms 17656 KB Output is correct
14 Correct 190 ms 23196 KB Output is correct
15 Correct 1911 ms 87672 KB Output is correct
16 Correct 185 ms 23220 KB Output is correct
17 Correct 1944 ms 87604 KB Output is correct
18 Correct 953 ms 87412 KB Output is correct
19 Correct 1004 ms 87660 KB Output is correct
20 Correct 1626 ms 87372 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 10 ms 12928 KB Output is correct
3 Correct 80 ms 16380 KB Output is correct
4 Correct 796 ms 87324 KB Output is correct
5 Correct 973 ms 87536 KB Output is correct
6 Correct 1374 ms 87244 KB Output is correct
7 Correct 1731 ms 87440 KB Output is correct
8 Correct 1887 ms 87520 KB Output is correct
9 Correct 844 ms 87432 KB Output is correct
10 Correct 855 ms 87584 KB Output is correct
11 Correct 670 ms 87404 KB Output is correct
12 Correct 785 ms 87360 KB Output is correct
13 Correct 954 ms 87248 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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