oj.uz

Submission #796052

# Submission time Handle Problem Language Result Execution time Memory
796052 2023-07-28T05:28:32 Z vjudge1 Comparing Plants (IOI20_plants) C++17
27 / 100
 744 ms 21244 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define N 200100
int pos[N], cnt, K;
int mval[4*N], mpos[4*N], l[4*N],r[4*N], sub[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;
    }
}
std::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],
            mpos[n] = mpos[2*n+1];
        else mval[n] = mval[2*n],
            mpos[n] = mpos[2*n];
    else {
        int dist = mpos[2*n+1]-mpos[2*n];
        int dist2 = R.size() - dist;
        if(dist>=K)
            mval[n] = mval[2*n+1],
            mpos[n] = mpos[2*n+1];
        else mval[n] = mval[2*n],
            mpos[n] = mpos[2*n];
    }
}
void build(int i, int lp, int rp) {
    l[i] = lp, r[i] = rp;
    if(lp==rp)
        mval[i] = R[lp-1],
        mpos[i] = lp;
    else build(i*2,lp,lp+rp>>1),
        build(i*2+1,lp+rp+2>>1,rp),
        upd(i);
}
#define n R.size()
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 init(int k, std::vector<int> r) {
    K=k;
    R = r;
    build(1,1,n);
    for(int i = 0; i < n; i++) {
        int x = mpos[1];
        std::cerr << x << '\n';
        pos[x-1] = ++cnt;
        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);
    }
	return;
}

int compare_plants(int x, int y) {
	return pos[x]<pos[y]?1:-1;
}

Compilation message

plants.cpp: In function 'void upd(int)':
plants.cpp:25:13: warning: unused variable 'dist2' [-Wunused-variable]
   25 |         int dist2 = R.size() - dist;
      |             ^~~~~
plants.cpp: In function 'void build(int, int, int)':
plants.cpp:38:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     else build(i*2,lp,lp+rp>>1),
      |                       ~~^~~
plants.cpp:39:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         build(i*2+1,lp+rp+2>>1,rp),
      |                     ~~~~~^~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < n; i++) {
      |                      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 60 ms 5500 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 4 ms 408 KB Output is correct
10 Correct 57 ms 5492 KB Output is correct
11 Correct 53 ms 5332 KB Output is correct
12 Correct 56 ms 5596 KB Output is correct
13 Correct 54 ms 5476 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 60 ms 5500 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 4 ms 408 KB Output is correct
10 Correct 57 ms 5492 KB Output is correct
11 Correct 53 ms 5332 KB Output is correct
12 Correct 56 ms 5596 KB Output is correct
13 Correct 54 ms 5476 KB Output is correct
14 Correct 115 ms 7012 KB Output is correct
15 Correct 744 ms 21192 KB Output is correct
16 Correct 105 ms 7116 KB Output is correct
17 Correct 710 ms 21056 KB Output is correct
18 Correct 613 ms 20556 KB Output is correct
19 Correct 613 ms 21244 KB Output is correct
20 Correct 689 ms 21036 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 46 ms 5092 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 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Incorrect 1 ms 312 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 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -