oj.uz

Submission #755267

# Submission time Handle Problem Language Result Execution time Memory
755267 2023-06-09T16:26:20 Z Rafi22 Comparing Plants (IOI20_plants) C++14
5 / 100
 730 ms 49240 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int pot=1<<18,N=200007,L=18;

int n;

struct T
{
    pair<int,int> seg[2*pot+7];
    int lzy[2*pot+7];
    T()
    {
        memset(seg,0,sizeof seg);
        memset(lzy,0,sizeof lzy);
    }
    void push(int v)
    {
        lzy[2*v]+=lzy[v];
        lzy[2*v+1]+=lzy[v];
        seg[2*v].st+=lzy[v];
        seg[2*v+1].st+=lzy[v];
        lzy[v]=0;
    }
    void add(int v,int a,int b,int l,int r,int x)
    {
        if(a<=l&&b>=r)
        {
            lzy[v]+=x;
            seg[v].st+=x;
            return ;
        }
        if(r<a||l>b) return ;
        push(v);
        add(2*v,a,b,l,(l+r)/2,x);
        add(2*v+1,a,b,(l+r)/2+1,r,x);
        seg[v]=min(seg[2*v],seg[2*v+1]);
    }
};

vector<int>p;

int skokR[N][L];
int skokL[N][L];

void init(int k,vector<int>r)
{
    n=sz(r);
    p.resize(2*n+2);
    T R,ile;
    for(int i=0;i<n;i++) R.seg[i+pot]={r[i],i+1};
    for(int i=n+1;i<=pot;i++) R.seg[i+pot-1]={inf,i};
    for(int i=1;i<=pot;i++) ile.seg[i+pot-1]={inf,i};
    for(int i=pot-1;i>0;i--)
    {
        R.seg[i]=min(R.seg[2*i],R.seg[2*i+1]);
        ile.seg[i]=min(ile.seg[2*i],ile.seg[2*i+1]);
    }
    int it=0;
    while(it<n)
    {
        while(R.seg[1].st==0)
        {
            int i=R.seg[1].nd;
            R.add(1,i,i,1,pot,inf);
            ile.add(1,i,i,1,pot,-inf);
            if(i+k-1<=n) ile.add(1,i+1,i+k-1,1,pot,1);
            else
            {
                ile.add(1,i+1,n,1,pot,1);
                ile.add(1,1,i+k-1-n,1,pot,1);
            }
        }
        int i=ile.seg[1].nd;
        ile.add(1,i,i,1,pot,inf);
        p[i]=n-it++;
        if(i+k-1<=n) ile.add(1,i+1,i+k-1,1,pot,-1);
        else
        {
            ile.add(1,i+1,n,1,pot,-1);
            ile.add(1,1,i+k-1-n,1,pot,-1);
        }
        if(i-k+1>0) R.add(1,i-k+1,i-1,1,pot,-1);
        else
        {
            R.add(1,i-k+1+n,n,1,pot,-1);
            R.add(1,1,i-1,1,pot,-1);
        }
    }
    for(int i=n+1;i<=2*n;i++) p[i]=p[i-n];
    p[2*n+1]=inf;
    p[0]=inf;
    set<pair<int,int>>S;
    S.insert({inf,0});
    for(int i=0;i<2*n;i++)
    {
        if(i-k>=0) S.erase({p[i-k+1],i-k});
        if(i>=n)
        {
            pair<int,int>x=*S.upper_bound({p[i+1],i});
            if(x.st==inf) skokR[i-n+1][0]=i-n+1;
            else skokR[i-n+1][0]=x.nd%n+1;
        }
        S.insert({p[i+1],i});
    }
    S.clear();
    S.insert({inf,0});
    for(int i=2*n-1;i>=0;i--)
    {
        if(i+k<2*n) S.erase({p[i+k+1],i+k});
        if(i<n)
        {
            pair<int,int>x=*S.upper_bound({p[i+1],i});
            if(x.st==inf) skokL[i+1][0]=i+1;
            else skokL[i+1][0]=x.nd%n+1;
        }
        S.insert({p[i+1],i});
    }
    for(int j=1;j<L;j++)
    {
        for(int i=1;i<=n;i++)
        {
            skokL[i][j]=skokL[skokL[i][j-1]][j-1];
            skokR[i][j]=skokR[skokR[i][j-1]][j-1];
        }
    }
}

int compare_plants(int x,int y)
{
    x++,y++;
    bool is=0;
    if(p[x]<p[y])
    {
        int X=x;
        for(int j=L-1;j>=0;j--) if(p[skokL[X][j]]<=p[y]) X=skokL[X][j];
        if(X==y) is=1;
        X=x;
        for(int j=L-1;j>=0;j--) if(p[skokR[X][j]]<=p[y]) X=skokR[X][j];
        if(X==y) is=1;
        if(is) return -1;
        else return 0;
    }
    else
    {
        int Y=y;
        for(int j=L-1;j>=0;j--) if(p[skokL[Y][j]]<=p[x]) Y=skokL[Y][j];
        if(Y==x) is=1;
        Y=y;
        for(int j=L-1;j>=0;j--) if(p[skokR[Y][j]]<=p[x]) Y=skokR[Y][j];
        if(Y==x) is=1;
        if(is) return 1;
        else return 0;
    }
}
/*

int main()
{
    init(2, {0, 1, 0, 1});
    cout<<compare_plants(0, 3)<<endl;
    cout<<compare_plants(1, 3)<<endl;

   /* int n,k;
    cin>>n>>k;
    vector<int>q(n);
    for(int i=0;i<n;i++) q[i]=i+1;
    random_shuffle(all(q));
    vector<int>r(n,0);
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<i+k;j++) if(q[i]<q[j%n]) r[i]++;
    }
    for(int i=0;i<n;i++) cout<<q[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++) cout<<r[i]<<" ";
    cout<<endl;
    init(k,r);
    return 0;
}*/

Compilation message

plants.cpp:176:4: warning: "/*" within comment [-Wcomment]
  176 |    /* int n,k;
      |     
plants.cpp: In constructor 'T::T()':
plants.cpp:26:32: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   26 |         memset(seg,0,sizeof seg);
      |                                ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from plants.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12628 KB Output is correct
2 Correct 9 ms 12628 KB Output is correct
3 Correct 8 ms 12628 KB Output is correct
4 Correct 9 ms 12628 KB Output is correct
5 Correct 9 ms 12616 KB Output is correct
6 Correct 85 ms 16336 KB Output is correct
7 Correct 153 ms 20616 KB Output is correct
8 Correct 554 ms 49196 KB Output is correct
9 Correct 583 ms 49176 KB Output is correct
10 Correct 578 ms 49240 KB Output is correct
11 Correct 629 ms 49180 KB Output is correct
12 Correct 608 ms 49100 KB Output is correct
13 Correct 730 ms 49180 KB Output is correct
14 Correct 698 ms 49176 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12628 KB Output is correct
2 Correct 10 ms 12580 KB Output is correct
3 Correct 7 ms 12600 KB Output is correct
4 Incorrect 8 ms 12628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12628 KB Output is correct
2 Correct 9 ms 12628 KB Output is correct
3 Correct 8 ms 12628 KB Output is correct
4 Correct 9 ms 12628 KB Output is correct
5 Correct 9 ms 12616 KB Output is correct
6 Correct 85 ms 16336 KB Output is correct
7 Correct 153 ms 20616 KB Output is correct
8 Correct 554 ms 49196 KB Output is correct
9 Correct 583 ms 49176 KB Output is correct
10 Correct 578 ms 49240 KB Output is correct
11 Correct 629 ms 49180 KB Output is correct
12 Correct 608 ms 49100 KB Output is correct
13 Correct 730 ms 49180 KB Output is correct
14 Correct 698 ms 49176 KB Output is correct
15 Correct 7 ms 12628 KB Output is correct
16 Correct 8 ms 12628 KB Output is correct
17 Correct 7 ms 12628 KB Output is correct
18 Correct 8 ms 12628 KB Output is correct
19 Incorrect 8 ms 12628 KB Output isn't correct
20 Halted 0 ms 0 KB -