oj.uz

답안 #721236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721236 2023-04-10T14:18:30 Z bin9638 식물 비교 (IOI20_plants) C++17
25 / 100
 4000 ms 71884 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[i][k-1]==-1 ? -1 : pre[pre[i][k-1]][k-1]);
            nxt[i][k]=(nxt[i][k-1]==-1 ? -1 :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;
    for(int t=0;t<=n;t++)
    {
        if(vt!=-1&&dis(vt,y)<=k-1&&h[vt]>=h[y])
            return 1;
        if(vt!=-1)
            vt=pre[vt][0];
                else break;
    }
    vt=x;
    for(int t=0;t<=n;t++)
    {
        if(vt!=-1&&dis(vt,y)<=k-1&&h[vt]>=h[y])
            return 1;
        if(vt!=-1)
            vt=nxt[vt][0];
                else break;
    }
    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 24 ms 66004 KB Output is correct
2 Correct 24 ms 66012 KB Output is correct
3 Correct 26 ms 66036 KB Output is correct
4 Correct 26 ms 66052 KB Output is correct
5 Correct 27 ms 66064 KB Output is correct
6 Correct 79 ms 68788 KB Output is correct
7 Correct 404 ms 71884 KB Output is correct
8 Execution timed out 4062 ms 26088 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 66124 KB Output is correct
2 Correct 32 ms 66004 KB Output is correct
3 Correct 28 ms 66036 KB Output is correct
4 Correct 27 ms 66004 KB Output is correct
5 Correct 25 ms 65972 KB Output is correct
6 Correct 45 ms 66124 KB Output is correct
7 Correct 2955 ms 69624 KB Output is correct
8 Correct 27 ms 66068 KB Output is correct
9 Correct 46 ms 66204 KB Output is correct
10 Correct 2707 ms 69628 KB Output is correct
11 Correct 219 ms 69544 KB Output is correct
12 Correct 1407 ms 69800 KB Output is correct
13 Correct 3933 ms 69620 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 66124 KB Output is correct
2 Correct 32 ms 66004 KB Output is correct
3 Correct 28 ms 66036 KB Output is correct
4 Correct 27 ms 66004 KB Output is correct
5 Correct 25 ms 65972 KB Output is correct
6 Correct 45 ms 66124 KB Output is correct
7 Correct 2955 ms 69624 KB Output is correct
8 Correct 27 ms 66068 KB Output is correct
9 Correct 46 ms 66204 KB Output is correct
10 Correct 2707 ms 69628 KB Output is correct
11 Correct 219 ms 69544 KB Output is correct
12 Correct 1407 ms 69800 KB Output is correct
13 Correct 3933 ms 69620 KB Output is correct
14 Execution timed out 4025 ms 71840 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 65996 KB Output is correct
2 Correct 25 ms 66072 KB Output is correct
3 Correct 707 ms 69036 KB Output is correct
4 Execution timed out 4053 ms 25744 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 66040 KB Output is correct
2 Correct 27 ms 66004 KB Output is correct
3 Correct 28 ms 66040 KB Output is correct
4 Correct 28 ms 66024 KB Output is correct
5 Correct 31 ms 66044 KB Output is correct
6 Correct 36 ms 66112 KB Output is correct
7 Correct 50 ms 66640 KB Output is correct
8 Correct 49 ms 66724 KB Output is correct
9 Correct 56 ms 66684 KB Output is correct
10 Correct 52 ms 66680 KB Output is correct
11 Correct 45 ms 66624 KB Output is correct
12 Correct 46 ms 66676 KB Output is correct
13 Correct 60 ms 66648 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 65996 KB Output is correct
2 Correct 27 ms 65956 KB Output is correct
3 Correct 27 ms 66032 KB Output is correct
4 Correct 32 ms 65996 KB Output is correct
5 Correct 29 ms 66180 KB Output is correct
6 Execution timed out 4086 ms 25720 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 66004 KB Output is correct
2 Correct 24 ms 66012 KB Output is correct
3 Correct 26 ms 66036 KB Output is correct
4 Correct 26 ms 66052 KB Output is correct
5 Correct 27 ms 66064 KB Output is correct
6 Correct 79 ms 68788 KB Output is correct
7 Correct 404 ms 71884 KB Output is correct
8 Execution timed out 4062 ms 26088 KB Time limit exceeded
9 Halted 0 ms 0 KB -