oj.uz

Submission #1036560

# Submission time Handle Problem Language Result Execution time Memory
1036560 2024-07-27T13:59:24 Z Dan4Life Comparing Plants (IOI20_plants) C++17
0 / 100
 4 ms 8284 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, comp[mxN], COMP;
vector<int> adj[mxN];
int deg[mxN], ord[mxN];
int h[mxN];

template<int SZ> struct SegTree{
	int seg[SZ], lzy[SZ];
	
	void init(){
		for(int i = 0; i < SZ; i++) seg[i]=0, lzy[i]=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]+=(mid-l+1)*lzy[p];
		seg[rp]+=(r-mid)*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);
		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);
	}
	
	int query(int i, int p=0, int l=0, int r=n-1){
		if(l==r) return seg[p]; prop(p,l,r);
		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<mxSeg> segTree;

void init(int k, vector<int> r) {
	n = sz(r); k--; int xd = n;
	segTree.init();
	for(int i = 0; i < n; i++) segTree.upd(i,i,r[i]);
	while(1){
		int i = segTree.findFirstMin(0,n-1);
		if(i==-1) break;
		int cur = segTree.query(i);
		if(cur) break;
		if(i<k){
			int i1 = segTree.findFirstMin(n-k+1,n-1);
			if(i1!=-1 and segTree.query(i1)==0) 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,INF); h[i]=xd; xd--;
	}
}

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

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Incorrect 3 ms 8284 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Incorrect 3 ms 8284 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Incorrect 3 ms 8284 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Incorrect 3 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Incorrect 4 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Incorrect 4 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Incorrect 3 ms 8284 KB Output isn't correct
5 Halted 0 ms 0 KB -