oj.uz

Submission #1037714

# Submission time Handle Problem Language Result Execution time Memory
1037714 2024-07-29T07:17:50 Z Dan4Life Comparing Plants (IOI20_plants) C++17
27 / 100
 1087 ms 11340 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ar2 = array<int,2>;
const int mxN = (int)2e5+10;
const int INF = (int)1e9;
int n, h[mxN];
 
template<class T, int SZ> struct SegTree{
	T seg[SZ], lzy[SZ];
	
	void init(){ fill(seg,seg+SZ,0), fill(lzy,lzy+SZ,0); }
	
	void prop(int p, int l, int r){
		if(!lzy[p] or l==r) return;
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		seg[p+1]+=lzy[p];
		seg[rp]+=lzy[p];
		lzy[p+1]+=lzy[p];
		lzy[rp]+=lzy[p];
		lzy[p]=0;
	}
	
	void upd(int i, int j, int v, int p=0, int l=0, int r=n-1){
		if(i>r or j<l or i>j) return; prop(p,l,r);
		if(i<=l and r<=j){ seg[p]+=v; lzy[p]+=v; return; }
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		if(i<=mid) upd(i,j,v,p+1,l,mid);
		if(j>mid) upd(i,j,v,rp,mid+1,r);
		seg[p] = min(seg[p+1],seg[rp]);
	}
	
	int findFirstMin(int i, int j, int p=0, int l=0, int r=n-1){
		if(i>r or j<l or i>j) return -1; prop(p,l,r);
		if(l==r) return l; 
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		if(i>mid) return findFirstMin(i,j,rp,mid+1,r);
		if(j<=mid) return findFirstMin(i,j,p+1,l,mid);
		if(query(i,mid)==query(i,j)) return findFirstMin(i,j,p+1,l,mid);
		return findFirstMin(i,j,rp,mid+1,r);
	}
	
	T query(int i, int j, int p=0, int l=0, int r=n-1){
		if(j<l or i>r or i>j) return INF; prop(p,l,r);
		if(i<=l and r<=j) return seg[p];
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		return min(query(i,j,p+1,l,mid), query(i,j,rp,mid+1,r)); 
	}
};
const int mxSeg = 2*mxN;
SegTree<int,mxSeg> segTree;
 
void init(int k, vector<int> r) {
	n = sz(r); k--; segTree.init();
	for(int i = 0; i < n; i++) segTree.upd(i,i,r[i]);
	for(int _ = n; _ > 0; _--){
		int i = segTree.findFirstMin(0,n-1);
		if(i<k){
			int i1 = segTree.findFirstMin(n-k+i,n-1);
			if(i1!=-1 and !segTree.query(i1,i1)) i=i1;
		}
		if(i<k) segTree.upd(0,i-1,-1), segTree.upd(n-k+i,n-1,-1);
		else segTree.upd(i-k,i-1,-1);
		segTree.upd(i,i,INF); h[i]=_;
	}
}
 
int compare_plants(int x, int y) {
	return h[x]>h[y]?1:-1;
}

Compilation message

plants.cpp: In member function 'void SegTree<T, SZ>::upd(int, int, int, int, int, int)':
plants.cpp:28:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   28 |   if(i>r or j<l or i>j) return; prop(p,l,r);
      |   ^~
plants.cpp:28:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |   if(i>r or j<l or i>j) return; prop(p,l,r);
      |                                 ^~~~
plants.cpp: In member function 'int SegTree<T, SZ>::findFirstMin(int, int, int, int, int)':
plants.cpp:37:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |   if(i>r or j<l or i>j) return -1; prop(p,l,r);
      |   ^~
plants.cpp:37:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |   if(i>r or j<l or i>j) return -1; prop(p,l,r);
      |                                    ^~~~
plants.cpp: In member function 'T SegTree<T, SZ>::query(int, int, int, int, int)':
plants.cpp:47:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   47 |   if(j<l or i>r or i>j) return INF; prop(p,l,r);
      |   ^~
plants.cpp:47:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   47 |   if(j<l or i>r or i>j) return INF; prop(p,l,r);
      |                                     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3524 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Incorrect 1 ms 3420 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 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3416 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 46 ms 8200 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 4 ms 3680 KB Output is correct
10 Correct 47 ms 8040 KB Output is correct
11 Correct 41 ms 8012 KB Output is correct
12 Correct 39 ms 8280 KB Output is correct
13 Correct 52 ms 8020 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3416 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 46 ms 8200 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 4 ms 3680 KB Output is correct
10 Correct 47 ms 8040 KB Output is correct
11 Correct 41 ms 8012 KB Output is correct
12 Correct 39 ms 8280 KB Output is correct
13 Correct 52 ms 8020 KB Output is correct
14 Correct 92 ms 8632 KB Output is correct
15 Correct 873 ms 11332 KB Output is correct
16 Correct 92 ms 8532 KB Output is correct
17 Correct 889 ms 11092 KB Output is correct
18 Correct 441 ms 11092 KB Output is correct
19 Correct 575 ms 11320 KB Output is correct
20 Correct 1087 ms 11340 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3416 KB Output is correct
3 Incorrect 34 ms 7788 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 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Incorrect 1 ms 3420 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 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Incorrect 1 ms 3420 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 3420 KB Output is correct
2 Correct 1 ms 3524 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Incorrect 1 ms 3420 KB Output isn't correct
5 Halted 0 ms 0 KB -