oj.uz

답안 #721188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721188 2023-04-10T13:25:53 Z bin9638 식물 비교 (IOI20_plants) C++17
14 / 100
 4000 ms 74132 KB 
#include <bits/stdc++.h>

#ifndef SKY
#include "plants.h"
#endif // SKY

using namespace std;

#define N 400010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int dem,k,n,h[N],a[N],pre[N][21],nxt[N][21],LOG;

struct IT
{
    struct node
    {
        ii min_val,max_val;
        int t=0;
    }ST[N*4];

    void down(int id)
    {
        ST[id*2].min_val.fs+=ST[id].t;
        ST[id*2].max_val.fs+=ST[id].t;
        ST[id*2].t+=ST[id].t;
        ST[id*2+1].min_val.fs+=ST[id].t;
        ST[id*2+1].max_val.fs+=ST[id].t;
        ST[id*2+1].t+=ST[id].t;
        ST[id].t=0;
    }

    void update(int id,int l,int r,int i,ii val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id].min_val=ST[id].max_val=val;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id].min_val=min(ST[id*2].min_val,ST[id*2+1].min_val);
        ST[id].max_val=max(ST[id*2].max_val,ST[id*2+1].max_val);
    }

    void them(int id,int l,int r,int u,int v,int val)
    {
        if(l>r||l>v||r<u)
            return;
        if(l>=u&&r<=v)
        {
            ST[id].t+=val;
            ST[id].min_val.fs+=val;
            ST[id].max_val.fs+=val;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        them(id*2,l,mid,u,v,val);
        them(id*2+1,mid+1,r,u,v,val);
        ST[id].min_val=min(ST[id*2].min_val,ST[id*2+1].min_val);
        ST[id].max_val=max(ST[id*2].max_val,ST[id*2+1].max_val);
    }

    ii get_min(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return {1e9,-1};
        if(l>=u&&r<=v)
            return ST[id].min_val;
        down(id);
        int mid=(l+r)/2;
        return min(get_min(id*2,l,mid,u,v),get_min(id*2+1,mid+1,r,u,v));
    }

    ii get_max(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return {-1e9,-1};
        if(l>=u&&r<=v)
            return ST[id].max_val;
        down(id);
        int mid=(l+r)/2;
        return max(get_max(id*2,l,mid,u,v),get_max(id*2+1,mid+1,r,u,v));
    }
}T;

void build(int i)
{
    while(T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).fs==0)
    {
        build(T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).sc);
    }
    T.them(1,1,n*2,i+1+n-k+1,i+1+n-1,-1);
    if(i-k+1>=0)
    {
        T.them(1,1,n*2,i+1-k+1,i+1-1,-1);
    }else
    {
        T.them(1,1,n*2,1,i+1-1,-1);
        T.them(1,1,n*2,n*2-(k-i-2),n*2,-1);
    }
    T.update(1,1,n*2,i+1,{1e9,i});
    T.update(1,1,n*2,i+n+1,{1e9,i});
    h[i]=--dem;
}

bool check_hihi(int u)
{
    if(a[u]!=0)
        return 0;
    for(int j=1;j<k;j++)
        if(a[(u-j+n)%n]==0)
            return 0;
    return 1;
}

void init(int cc, vector<int> r)
{
	k=cc;
	n=r.size();
	for(int i=0;i<n;i++)
    {
        a[i]=r[i];
        T.update(1,1,n*2,i+1,{a[i],i});
        T.update(1,1,n*2,i+n+1,{a[i],i});
    }
   /* dem=n;
    for(int i=0;i<n;i++)
    {
        build(T.get_min(1,1,n*2,1,n*2).sc);
     //   for(int i=0;i<n;i++)cout<<T.get_max(1,1,n*2,i+1,i+1).fs<<" ";cout<<endl;
    }*/
        int dem=n;
    for(int t=0;t<n;t++)
    {
    for(int i=0;i<n;i++)
        if(check_hihi(i))
        {
            h[i]=--dem;
            for(int j=0;j<k;j++)
                a[(i-j+n)%n]--;
            break;
        }
    }
    //for(int i=0;i<n;i++)cout<<h[i]<<" ";
    for(int i=0;i<n;i++)
    {
        T.update(1,1,n*2,i+1,{-1e9,-1});
        T.update(1,1,n*2,i+n+1,{-1e9,-1});
    }
    vector<ii>s;
    for(int i=0;i<n;i++)
        s.pb({h[i],i});
    sort(s.begin(),s.end());
    memset(pre,-1,sizeof(pre));
    memset(nxt,-1,sizeof(nxt));
    for(auto cc:s)
    {
        int i=cc.sc;
        pre[i][0]=T.get_max(1,1,n*2,i+1+n-k+1,i+1+n-1).sc;
        nxt[i][0]=T.get_max(1,1,n*2,i+1+1,i+1+k-1).sc;
        T.update(1,1,n*2,i+1,cc);
        T.update(1,1,n*2,i+n+1,cc);
        //cout<<i<<" "<<pre[i][0]<<" "<<nxt[i][0]<<endl;
    }
    LOG=log2(n);
    for(int k=1;k<=LOG;k++)
        for(int i=0;i<n;i++)
        {
            pre[i][k]=pre[pre[i][k-1]][k-1];
            nxt[i][k]=nxt[nxt[i][k-1]][k-1];
        }
}

int dis(int x,int y)
{
    return min(min(abs(x-y),abs(x+n-y)),abs(y+n-x));
}

bool check(int x,int y)
{
   // cout<<x<<" "<<y<<endl;
    int vt=x;
  //  cout<<dis(x,y)<<endl;
    if(dis(vt,y)>k-1)
    {
        for(int k=LOG;k>=0;k--)
            if(pre[vt][k]!=-1&&dis(pre[vt][k],y)>k-1)
                vt=pre[vt][k];
    }
    if(dis(vt,y)>k-1)
        vt=pre[vt][0];
    if(vt!=-1&&h[vt]>=h[y])
        return 1;
    vt=x;
     if(dis(vt,y)>k-1)
     {
    for(int k=LOG;k>=0;k--)
        if(nxt[vt][k]!=-1&&dis(nxt[vt][k],y)>k-1)
            vt=nxt[vt][k];
     }
     if(dis(vt,y)>k-1)
        vt=nxt[vt][0];
     if(vt!=-1&&h[vt]>=h[y])
        return 1;
    return 0;
}

int compare_plants(int x, int y)
{
    if(check(x,y))
        return 1;
    if(check(y,x))
        return -1;
    return 0;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    vector<int>r(n);
    for(int i=0;i<n;i++)
        cin>>r[i];//,cout<<r[i]<<endl;
    init(k,r);
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        cout<<compare_plants(x,y)<<endl;
    }
    return 0;
}
#endif

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 66132 KB Output is correct
2 Correct 27 ms 65960 KB Output is correct
3 Correct 25 ms 65996 KB Output is correct
4 Correct 27 ms 65964 KB Output is correct
5 Incorrect 26 ms 66020 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 65956 KB Output is correct
2 Correct 28 ms 66044 KB Output is correct
3 Correct 28 ms 65988 KB Output is correct
4 Correct 27 ms 65996 KB Output is correct
5 Correct 28 ms 65972 KB Output is correct
6 Correct 36 ms 66232 KB Output is correct
7 Correct 276 ms 71580 KB Output is correct
8 Correct 31 ms 66124 KB Output is correct
9 Correct 40 ms 66224 KB Output is correct
10 Correct 298 ms 71568 KB Output is correct
11 Correct 227 ms 71624 KB Output is correct
12 Correct 218 ms 71644 KB Output is correct
13 Correct 334 ms 71588 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 65956 KB Output is correct
2 Correct 28 ms 66044 KB Output is correct
3 Correct 28 ms 65988 KB Output is correct
4 Correct 27 ms 65996 KB Output is correct
5 Correct 28 ms 65972 KB Output is correct
6 Correct 36 ms 66232 KB Output is correct
7 Correct 276 ms 71580 KB Output is correct
8 Correct 31 ms 66124 KB Output is correct
9 Correct 40 ms 66224 KB Output is correct
10 Correct 298 ms 71568 KB Output is correct
11 Correct 227 ms 71624 KB Output is correct
12 Correct 218 ms 71644 KB Output is correct
13 Correct 334 ms 71588 KB Output is correct
14 Correct 2371 ms 74132 KB Output is correct
15 Execution timed out 4069 ms 30032 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 65996 KB Output is correct
2 Correct 25 ms 65980 KB Output is correct
3 Incorrect 149 ms 69488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 66048 KB Output is correct
2 Correct 27 ms 66020 KB Output is correct
3 Incorrect 30 ms 65952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 66004 KB Output is correct
2 Correct 25 ms 66020 KB Output is correct
3 Correct 25 ms 66004 KB Output is correct
4 Correct 26 ms 66052 KB Output is correct
5 Incorrect 34 ms 66088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 66132 KB Output is correct
2 Correct 27 ms 65960 KB Output is correct
3 Correct 25 ms 65996 KB Output is correct
4 Correct 27 ms 65964 KB Output is correct
5 Incorrect 26 ms 66020 KB Output isn't correct
6 Halted 0 ms 0 KB -