oj.uz

Submission #951118

# Submission time Handle Problem Language Result Execution time Memory
951118 2024-03-21T07:26:57 Z Trisanu_Das Comparing Plants (IOI20_plants) C++17
44 / 100
 2017 ms 87808 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 24 ms 49840 KB Output is correct
2 Correct 12 ms 49756 KB Output is correct
3 Correct 12 ms 50012 KB Output is correct
4 Incorrect 11 ms 49768 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 49756 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49756 KB Output is correct
4 Correct 12 ms 49756 KB Output is correct
5 Correct 10 ms 49760 KB Output is correct
6 Correct 15 ms 49932 KB Output is correct
7 Correct 78 ms 55424 KB Output is correct
8 Correct 11 ms 49756 KB Output is correct
9 Correct 15 ms 50012 KB Output is correct
10 Correct 74 ms 55168 KB Output is correct
11 Correct 74 ms 54836 KB Output is correct
12 Correct 74 ms 55264 KB Output is correct
13 Correct 72 ms 55184 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49756 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49756 KB Output is correct
4 Correct 12 ms 49756 KB Output is correct
5 Correct 10 ms 49760 KB Output is correct
6 Correct 15 ms 49932 KB Output is correct
7 Correct 78 ms 55424 KB Output is correct
8 Correct 11 ms 49756 KB Output is correct
9 Correct 15 ms 50012 KB Output is correct
10 Correct 74 ms 55168 KB Output is correct
11 Correct 74 ms 54836 KB Output is correct
12 Correct 74 ms 55264 KB Output is correct
13 Correct 72 ms 55184 KB Output is correct
14 Correct 166 ms 57244 KB Output is correct
15 Correct 1634 ms 85756 KB Output is correct
16 Correct 156 ms 57220 KB Output is correct
17 Correct 1602 ms 85648 KB Output is correct
18 Correct 1175 ms 84904 KB Output is correct
19 Correct 1083 ms 85576 KB Output is correct
20 Correct 1390 ms 85464 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 49752 KB Output is correct
2 Correct 10 ms 49756 KB Output is correct
3 Correct 71 ms 54620 KB Output is correct
4 Correct 1051 ms 87808 KB Output is correct
5 Correct 1378 ms 84772 KB Output is correct
6 Correct 1907 ms 84948 KB Output is correct
7 Correct 1526 ms 85372 KB Output is correct
8 Correct 1574 ms 85576 KB Output is correct
9 Correct 1135 ms 84396 KB Output is correct
10 Correct 2017 ms 86464 KB Output is correct
11 Correct 1016 ms 84796 KB Output is correct
12 Correct 1066 ms 84656 KB Output is correct
13 Correct 1190 ms 84744 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49756 KB Output is correct
2 Correct 11 ms 49752 KB Output is correct
3 Incorrect 11 ms 49756 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 49756 KB Output is correct
2 Correct 10 ms 49756 KB Output is correct
3 Incorrect 10 ms 49756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49840 KB Output is correct
2 Correct 12 ms 49756 KB Output is correct
3 Correct 12 ms 50012 KB Output is correct
4 Incorrect 11 ms 49768 KB Output isn't correct
5 Halted 0 ms 0 KB -