oj.uz

Submission #892380

# Submission time Handle Problem Language Result Execution time Memory
892380 2023-12-25T09:26:31 Z abcvuitunggio Comparing Plants (IOI20_plants) C++17
27 / 100
 569 ms 13652 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--){
        int tmp=j;
        j=get(j,j+k-1).pos;
        if (get(1,0,n-1,j,j).mn)
            j=get(tmp-k+1,tmp).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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 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 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2424 KB Output is correct
6 Correct 3 ms 2552 KB Output is correct
7 Correct 51 ms 5340 KB Output is correct
8 Correct 2 ms 2804 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 51 ms 5248 KB Output is correct
11 Correct 46 ms 5360 KB Output is correct
12 Correct 48 ms 5456 KB Output is correct
13 Correct 50 ms 5380 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2424 KB Output is correct
6 Correct 3 ms 2552 KB Output is correct
7 Correct 51 ms 5340 KB Output is correct
8 Correct 2 ms 2804 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 51 ms 5248 KB Output is correct
11 Correct 46 ms 5360 KB Output is correct
12 Correct 48 ms 5456 KB Output is correct
13 Correct 50 ms 5380 KB Output is correct
14 Correct 85 ms 7764 KB Output is correct
15 Correct 569 ms 13524 KB Output is correct
16 Correct 91 ms 7760 KB Output is correct
17 Correct 547 ms 13520 KB Output is correct
18 Correct 360 ms 13312 KB Output is correct
19 Correct 456 ms 13652 KB Output is correct
20 Correct 491 ms 13392 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 0 ms 2396 KB Output is correct
3 Incorrect 45 ms 5348 KB Output isn't correct
4 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 0 ms 2392 KB Output is correct
3 Incorrect 1 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 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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