oj.uz

Submission #1037278

# Submission time Handle Problem Language Result Execution time Memory
1037278 2024-07-28T12:32:36 Z Dan4Life Comparing Plants (IOI20_plants) C++17
27 / 100
 314 ms 11988 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; 
		if(i<=l and r<=j){ seg[p]+=v; lzy[p]+=v; return; }
		prop(p,l,r);
		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);
		prop(p+1,l,mid);
		if(seg[p+1]==seg[p]) return findFirstMin(i,j,p+1,l,mid);
		return findFirstMin(i,j,rp,mid+1,r);
	}
	
	T query(int i, int p=0, int l=0, int r=n-1){
		if(i<l or i>r) return INF; prop(p,l,r);
		if(l==r) return seg[p]; 
		int mid = (l+r)/2; int rp = p+2*(mid-l+1);
		if(i<=mid) return query(i,p+1,l,mid);
		return query(i,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){
			segTree.upd(0,n-k+i-1,mxN);
			int i1 = segTree.findFirstMin(0,n-1);
			bool ok = 0;
			if(i1!=-1 and !segTree.query(i1)) ok=1;
			segTree.upd(0,n-k+i-1,-mxN); 
			if(ok) i=i1;
		}
		if(i>=k) segTree.upd(i-k,i-1,-1);
		else segTree.upd(0,i-1,-1), segTree.upd(n-k+i,n-1,-1);
		segTree.upd(i,i,mxN); h[i]=_;
	}
}

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

Compilation message

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

Subtask #1
0 / 5.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 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 3420 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 3 ms 3740 KB Output is correct
7 Correct 37 ms 8276 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 37 ms 8184 KB Output is correct
11 Correct 35 ms 8060 KB Output is correct
12 Correct 35 ms 8276 KB Output is correct
13 Correct 44 ms 8272 KB Output is correct

Subtask #3
13.0 / 13.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 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 3 ms 3740 KB Output is correct
7 Correct 37 ms 8276 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 37 ms 8184 KB Output is correct
11 Correct 35 ms 8060 KB Output is correct
12 Correct 35 ms 8276 KB Output is correct
13 Correct 44 ms 8272 KB Output is correct
14 Correct 55 ms 8784 KB Output is correct
15 Correct 294 ms 11988 KB Output is correct
16 Correct 58 ms 8760 KB Output is correct
17 Correct 285 ms 11860 KB Output is correct
18 Correct 201 ms 11348 KB Output is correct
19 Correct 194 ms 11860 KB Output is correct
20 Correct 314 ms 11892 KB Output is correct

Subtask #4
0 / 17.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 34 ms 8040 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 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 3416 KB Output is correct
2 Correct 1 ms 3520 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 3416 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 -