oj.uz

Submission #1037760

# Submission time Handle Problem Language Result Execution time Memory
1037760 2024-07-29T07:57:29 Z Dan4Life Comparing Plants (IOI20_plants) C++17
44 / 100
 1652 ms 14952 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;
vector<int> v;

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--; v.pb(i);
}

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));
	for(int i = 0; i < sz(v); i++) h[v[i]]=n-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 3420 KB Output is correct
3 Correct 1 ms 3448 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 3520 KB Output is correct
2 Correct 1 ms 3416 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 5 ms 3676 KB Output is correct
7 Correct 55 ms 7372 KB Output is correct
8 Correct 2 ms 3672 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct
10 Correct 55 ms 7536 KB Output is correct
11 Correct 44 ms 7248 KB Output is correct
12 Correct 44 ms 7520 KB Output is correct
13 Correct 57 ms 7308 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3520 KB Output is correct
2 Correct 1 ms 3416 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 5 ms 3676 KB Output is correct
7 Correct 55 ms 7372 KB Output is correct
8 Correct 2 ms 3672 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct
10 Correct 55 ms 7536 KB Output is correct
11 Correct 44 ms 7248 KB Output is correct
12 Correct 44 ms 7520 KB Output is correct
13 Correct 57 ms 7308 KB Output is correct
14 Correct 152 ms 7944 KB Output is correct
15 Correct 1606 ms 11156 KB Output is correct
16 Correct 154 ms 8232 KB Output is correct
17 Correct 1583 ms 11160 KB Output is correct
18 Correct 839 ms 10696 KB Output is correct
19 Correct 901 ms 10888 KB Output is correct
20 Correct 1602 ms 11136 KB Output is correct

Subtask #4
17.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 Correct 45 ms 7468 KB Output is correct
4 Correct 441 ms 14952 KB Output is correct
5 Correct 674 ms 12756 KB Output is correct
6 Correct 1048 ms 12492 KB Output is correct
7 Correct 1427 ms 12904 KB Output is correct
8 Correct 1652 ms 13004 KB Output is correct
9 Correct 522 ms 12492 KB Output is correct
10 Correct 510 ms 12236 KB Output is correct
11 Correct 283 ms 11904 KB Output is correct
12 Correct 491 ms 12236 KB Output is correct
13 Correct 779 ms 12304 KB Output is correct

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 3420 KB Output is correct
3 Correct 1 ms 3448 KB Output is correct
4 Incorrect 1 ms 3420 KB Output isn't correct
5 Halted 0 ms 0 KB -