oj.uz

Submission #796129

# Submission time Handle Problem Language Result Execution time Memory
796129 2023-07-28T06:46:02 Z boyliguanhan Comparing Plants (IOI20_plants) C++17
44 / 100
 1998 ms 81768 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200100
int pos[N], cnt, K;
int mval[4*N], mpl[4*N], mpr[4*N], l[4*N],r[4*N], sub[4*N];
set<int> mop[4*N];
void pd(int n) {
    if(sub[n]) {
        mval[n]-=sub[n];
        if(l[n]!=r[n])
            sub[n*2]+=sub[n],
            sub[n*2+1]+=sub[n];
        sub[n] = 0;
    }
}
vector<int> R;
void upd(int n) {
    if(l[n]==r[n]) return;
    if(mval[2*n]!=mval[2*n+1])
        if(mval[2*n]>mval[2*n+1])
            mval[n] = mval[2*n+1],
            mpl[n] = mpl[2*n+1],
            mpr[n] = mpr[2*n+1],
            mop[n] = mop[2*n+1];
        else mval[n] = mval[2*n],
            mop[n] = mop[2*n],
            mpl[n] = mpl[2*n],
            mpr[n] = mpr[2*n];
    else {
        mpl[n] = mpl[2*n];
        mpr[n]=mpr[2*n+1];
        mval[n]=mval[2*n];
        mop[n]=mop[2*n];
        for(auto i: mop[2*n+1]) {
            mop[n].insert(i);
        }
        if(mpl[2*n+1]-mpr[2*n]<K)
            mop[n].erase(mpl[2*n+1]);
        if(mpl[2*n]+(int)R.size()-mpr[2*n+1]<K)
            mop[n].erase(mpl[2*n]);
    }
}
int n;
void build(int i, int lp, int rp) {
    l[i] = lp, r[i] = rp;
    if(lp==rp)
        mval[i] = R[lp-1], mpl[i]=mpr[i]=lp,mop[i].insert(lp);
    else build(i*2,lp,(lp+rp)>>1),
        build(i*2+1,(lp+rp+2)>>1,rp),
        upd(i);
}
void update(int i, int rl, int rr, int v) {
    pd(i);
    if(rl<=l[i]&&r[i]<=rr)
        return (void)(sub[i]-=v,pd(i));
    if(rl<=r[i*2])
        update(i*2,rl,rr,v);
    if(r[i*2]<rr)
        update(i*2+1,rl,rr,v);
    pd(i*2);
    pd(i*2+1);
    upd(i);
}
void UPD(int x) {
    if(x<K) {
        update(1,1,x,-1);
        update(1,n-K+x+1,n,-1);
    } else {
        update(1,x-K+1,x,-1);
    }
    update(1,x,x,1e9);
}
void init(int k, vector<int> _r) {
    n = _r.size();
    K=k;
    R = _r;
    build(1,1,n);
    for(int i = 0; i < n;) {
        ++cnt;
        set<int> x = mop[1];
        i+=x.size();
        for(auto i: x)
            pos[i-1] = cnt, UPD(i), cerr << i << ' ';
        cerr << '\n';
    }
	return;
}
int compare_plants(int x, int y) {
    if(pos[x]<pos[y])
        return 1;
    if(pos[x]-pos[y])
        return -1;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37856 KB Output is correct
2 Correct 17 ms 37828 KB Output is correct
3 Correct 17 ms 37844 KB Output is correct
4 Incorrect 17 ms 37884 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 19 ms 37868 KB Output is correct
2 Correct 20 ms 37868 KB Output is correct
3 Correct 22 ms 37844 KB Output is correct
4 Correct 17 ms 37896 KB Output is correct
5 Correct 18 ms 37948 KB Output is correct
6 Correct 21 ms 38148 KB Output is correct
7 Correct 84 ms 41744 KB Output is correct
8 Correct 18 ms 38020 KB Output is correct
9 Correct 27 ms 38152 KB Output is correct
10 Correct 82 ms 41704 KB Output is correct
11 Correct 77 ms 41560 KB Output is correct
12 Correct 109 ms 41800 KB Output is correct
13 Correct 83 ms 41720 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37868 KB Output is correct
2 Correct 20 ms 37868 KB Output is correct
3 Correct 22 ms 37844 KB Output is correct
4 Correct 17 ms 37896 KB Output is correct
5 Correct 18 ms 37948 KB Output is correct
6 Correct 21 ms 38148 KB Output is correct
7 Correct 84 ms 41744 KB Output is correct
8 Correct 18 ms 38020 KB Output is correct
9 Correct 27 ms 38152 KB Output is correct
10 Correct 82 ms 41704 KB Output is correct
11 Correct 77 ms 41560 KB Output is correct
12 Correct 109 ms 41800 KB Output is correct
13 Correct 83 ms 41720 KB Output is correct
14 Correct 161 ms 44548 KB Output is correct
15 Correct 1658 ms 75940 KB Output is correct
16 Correct 164 ms 44624 KB Output is correct
17 Correct 1880 ms 76476 KB Output is correct
18 Correct 1149 ms 76864 KB Output is correct
19 Correct 1112 ms 76824 KB Output is correct
20 Correct 1363 ms 76812 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37848 KB Output is correct
2 Correct 21 ms 37892 KB Output is correct
3 Correct 88 ms 41528 KB Output is correct
4 Correct 1061 ms 81768 KB Output is correct
5 Correct 1446 ms 78928 KB Output is correct
6 Correct 1998 ms 79056 KB Output is correct
7 Correct 1594 ms 79376 KB Output is correct
8 Correct 1655 ms 79764 KB Output is correct
9 Correct 1128 ms 78792 KB Output is correct
10 Correct 1982 ms 80604 KB Output is correct
11 Correct 1006 ms 78344 KB Output is correct
12 Correct 994 ms 79068 KB Output is correct
13 Correct 1145 ms 79104 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37860 KB Output is correct
2 Correct 20 ms 37844 KB Output is correct
3 Incorrect 20 ms 37896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37856 KB Output is correct
2 Correct 17 ms 37828 KB Output is correct
3 Correct 17 ms 37844 KB Output is correct
4 Incorrect 17 ms 37884 KB Output isn't correct
5 Halted 0 ms 0 KB -