oj.uz

Submission #796110

# Submission time Handle Problem Language Result Execution time Memory
796110 2023-07-28T06:31:08 Z boyliguanhan Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 4708 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define N 20
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(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]+n-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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Execution timed out 4093 ms 4656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 4061 ms 4708 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 4061 ms 4708 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 4048 ms 4472 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 4067 ms 4492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Execution timed out 4093 ms 4656 KB Time limit exceeded
5 Halted 0 ms 0 KB -