oj.uz

Submission #755238

# Submission time Handle Problem Language Result Execution time Memory
755238 2023-06-09T16:02:07 Z Rafi22 Comparing Plants (IOI20_plants) C++14
44 / 100
 945 ms 21092 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;

int n;
int p[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]);
    }
};



void init(int k,vector<int>r)
{
    n=sz(r);
    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;
       // cout<<i<<endl;
        if(ile.seg[1].st!=0) exit(2137);
        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=1;i<=n;i++) cout<<p[i]<<" ";
   // cout<<endl;
}

int compare_plants(int x,int y)
{
    if(p[x+1]>p[y+1]) return 1;
    else return -1;
}

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

Compilation message

plants.cpp: In constructor 'T::T()':
plants.cpp:27: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]
   27 |         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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12500 KB Output is correct
2 Correct 10 ms 12500 KB Output is correct
3 Correct 9 ms 12616 KB Output is correct
4 Incorrect 11 ms 12496 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 10 ms 12612 KB Output is correct
2 Correct 11 ms 12500 KB Output is correct
3 Correct 9 ms 12500 KB Output is correct
4 Correct 10 ms 12548 KB Output is correct
5 Correct 11 ms 12536 KB Output is correct
6 Correct 18 ms 12732 KB Output is correct
7 Correct 95 ms 17384 KB Output is correct
8 Correct 11 ms 12628 KB Output is correct
9 Correct 12 ms 12736 KB Output is correct
10 Correct 92 ms 17304 KB Output is correct
11 Correct 88 ms 17268 KB Output is correct
12 Correct 74 ms 17424 KB Output is correct
13 Correct 81 ms 17328 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12612 KB Output is correct
2 Correct 11 ms 12500 KB Output is correct
3 Correct 9 ms 12500 KB Output is correct
4 Correct 10 ms 12548 KB Output is correct
5 Correct 11 ms 12536 KB Output is correct
6 Correct 18 ms 12732 KB Output is correct
7 Correct 95 ms 17384 KB Output is correct
8 Correct 11 ms 12628 KB Output is correct
9 Correct 12 ms 12736 KB Output is correct
10 Correct 92 ms 17304 KB Output is correct
11 Correct 88 ms 17268 KB Output is correct
12 Correct 74 ms 17424 KB Output is correct
13 Correct 81 ms 17328 KB Output is correct
14 Correct 132 ms 17812 KB Output is correct
15 Correct 945 ms 21036 KB Output is correct
16 Correct 124 ms 17904 KB Output is correct
17 Correct 853 ms 21064 KB Output is correct
18 Correct 553 ms 20540 KB Output is correct
19 Correct 594 ms 21060 KB Output is correct
20 Correct 810 ms 21092 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12620 KB Output is correct
2 Correct 11 ms 12600 KB Output is correct
3 Correct 86 ms 17172 KB Output is correct
4 Correct 431 ms 20236 KB Output is correct
5 Correct 537 ms 20412 KB Output is correct
6 Correct 738 ms 20592 KB Output is correct
7 Correct 806 ms 20800 KB Output is correct
8 Correct 931 ms 21012 KB Output is correct
9 Correct 505 ms 20332 KB Output is correct
10 Correct 471 ms 20348 KB Output is correct
11 Correct 437 ms 20228 KB Output is correct
12 Correct 438 ms 20328 KB Output is correct
13 Correct 541 ms 20424 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12500 KB Output is correct
2 Correct 10 ms 12500 KB Output is correct
3 Correct 9 ms 12616 KB Output is correct
4 Incorrect 11 ms 12496 KB Output isn't correct
5 Halted 0 ms 0 KB -