oj.uz

Submission #892374

# Submission time Handle Problem Language Result Execution time Memory
892374 2023-12-25T09:17:58 Z abcvuitunggio Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 15812 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct T{
    int mn,pos;
}st[800001];
T operator +(T a, T b){
    return (a.mn>b.mn?b:a);
}
int n,k,lazy[800001],p[200001];
vector <int> a;
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    st[node<<1].mn+=lazy[node];
    st[node<<1|1].mn+=lazy[node];
    lazy[node<<1]+=lazy[node];
    lazy[node<<1|1]+=lazy[node];
    lazy[node]=0;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={a[l],l};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v)
        return;
    if (l>=u&&r<=v){
        st[node].mn+=val;
        lazy[node]+=val;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=st[node<<1]+st[node<<1|1];
}
T get(int node, int l, int r, int u, int v){
    if (l>v||r<u||u>v)
        return {INF,0};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
int calc(int j){
    T t={INF,0};
    if (j<k)
        t=get(1,0,n-1,0,j-1)+get(1,0,n-1,n+j-k+1,n-1);
    else
        t=get(1,0,n-1,j-k+1,j-1);
    if (t.mn)
        return -1;
    return t.pos;
}
T get(int l, int r){
    l=(l%n+n)%n;
    r=(r%n+n)%n;
    if (l<=r)
        return get(1,0,n-1,l,r);
    else{
        T t=get(1,0,n-1,l,n-1);
        if (!t.mn)
            return t;
        else
            return get(1,0,n-1,0,r);
    }
}
void init(int K, vector <int> r){
    k=K;
    a=r;
    n=a.size();
    build(1,0,n-1);
    int j=st[1].pos;
    while (true){
        int tmp=calc(j);
        if (tmp==-1)
            break;
        j=tmp;
    }
    p[j]=n-1;
    if (j<k){
        update(1,0,n-1,0,j-1,-1);
        update(1,0,n-1,n+j-k+1,n-1,-1);
    }
    else
        update(1,0,n-1,j-k+1,j-1,-1);
    update(1,0,n-1,j,j,INF);
    for (int i=n-2;i;i--){
        j=st[1].pos;
        while (true){
            int tmp=calc(j);
            if (tmp==-1)
                break;
            j=tmp;
        }
        p[j]=i;
        if (j<k){
            update(1,0,n-1,0,j-1,-1);
            update(1,0,n-1,n+j-k+1,n-1,-1);
        }
        else
            update(1,0,n-1,j-k+1,j-1,-1);
        update(1,0,n-1,j,j,INF);
    }
}
int compare_plants(int x, int y){
	return (p[x]>p[y]?1:(p[x]<p[y]?-1:0));
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 0 ms 2396 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 47 ms 6712 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 3 ms 2500 KB Output is correct
10 Correct 49 ms 6580 KB Output is correct
11 Correct 43 ms 6448 KB Output is correct
12 Correct 43 ms 6748 KB Output is correct
13 Correct 46 ms 6740 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 47 ms 6712 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 3 ms 2500 KB Output is correct
10 Correct 49 ms 6580 KB Output is correct
11 Correct 43 ms 6448 KB Output is correct
12 Correct 43 ms 6748 KB Output is correct
13 Correct 46 ms 6740 KB Output is correct
14 Correct 70 ms 9044 KB Output is correct
15 Correct 401 ms 15696 KB Output is correct
16 Correct 70 ms 9000 KB Output is correct
17 Correct 393 ms 15812 KB Output is correct
18 Correct 271 ms 15240 KB Output is correct
19 Correct 304 ms 15700 KB Output is correct
20 Correct 364 ms 15572 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 56 ms 5412 KB Output is correct
4 Execution timed out 4019 ms 13248 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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