oj.uz

Submission #1037761

# Submission time Handle Problem Language Result Execution time Memory
1037761 2024-07-29T07:57:59 Z Dan4Life Comparing Plants (IOI20_plants) C++17
44 / 100
 1631 ms 11088 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, k, 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;

int cur;

void solve(int i){
	bool ok = 1;
	while(ok){
		ok = 0;
		if(i<k){
			int i1 = segTree.findFirstMin(n-k+i,n-1);
			if(i1!=-1 and !segTree.query(i1,i1)) solve(i1), ok=1;
		}
		int i1 = segTree.findFirstMin(max(0,i-k),i-1);
		if(i1!=-1 and !segTree.query(i1,i1)) solve(i1), ok=1;
	}
	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]=cur--;
}

void init(int K, vector<int> r){
	n = sz(r); k=K-1; segTree.init(); cur = n;
	for(int i = 0; i < n; i++) segTree.upd(i,i,r[i]);
	while(!segTree.query(0,n-1)) solve(segTree.findFirstMin(0,n-1));
}

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 3420 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 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 52 ms 6252 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 67 ms 6228 KB Output is correct
11 Correct 45 ms 6228 KB Output is correct
12 Correct 44 ms 6484 KB Output is correct
13 Correct 54 ms 6228 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 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 52 ms 6252 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 67 ms 6228 KB Output is correct
11 Correct 45 ms 6228 KB Output is correct
12 Correct 44 ms 6484 KB Output is correct
13 Correct 54 ms 6228 KB Output is correct
14 Correct 143 ms 6740 KB Output is correct
15 Correct 1509 ms 8264 KB Output is correct
16 Correct 161 ms 6484 KB Output is correct
17 Correct 1631 ms 8268 KB Output is correct
18 Correct 816 ms 8020 KB Output is correct
19 Correct 899 ms 8172 KB Output is correct
20 Correct 1596 ms 8256 KB Output is correct

Subtask #4
17.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 Correct 34 ms 6244 KB Output is correct
4 Correct 471 ms 11088 KB Output is correct
5 Correct 660 ms 8528 KB Output is correct
6 Correct 995 ms 8304 KB Output is correct
7 Correct 1336 ms 8260 KB Output is correct
8 Correct 1551 ms 8264 KB Output is correct
9 Correct 515 ms 8472 KB Output is correct
10 Correct 462 ms 8196 KB Output is correct
11 Correct 272 ms 8020 KB Output is correct
12 Correct 456 ms 8272 KB Output is correct
13 Correct 730 ms 8016 KB Output is correct

Subtask #5
0 / 11.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 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 3420 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 -