oj.uz

Submission #1037765

# Submission time Handle Problem Language Result Execution time Memory
1037765 2024-07-29T08:04:19 Z Dan4Life Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 27220 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)5e3+10;
const int INF = (int)1e9;
int n, k, h[mxN];
bool path[mxN][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--;
}

int dis(int a, int b){ return min(abs(a-b),n-abs(a-b)); }

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 < n; i++)
		for(int j = 0; j < n; j++)
			if((i==j or h[i]>h[j]) and dis(i,j)<=k)
				path[i][j]=1;
		
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				path[i][j] |= path[i][k]&path[k][j];
}

int compare_plants(int x, int y){
	if(path[x][y]) return 1;
	if(path[y][x]) return -1;
	return 0;
}

Compilation message

plants.cpp: In member function 'void SegTree<T, SZ>::upd(int, int, int, int, int, int)':
plants.cpp:29:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |   if(i>r or j<l or i>j) return; prop(p,l,r);
      |   ^~
plants.cpp:29:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |   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:38:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |   if(i>r or j<l or i>j) return -1; prop(p,l,r);
      |   ^~
plants.cpp:38:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |   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:48:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |   if(j<l or i>r or i>j) return INF; prop(p,l,r);
      |   ^~
plants.cpp:48:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |   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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 29 ms 6344 KB Output is correct
7 Runtime error 30 ms 7984 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 2492 KB Output is correct
6 Correct 868 ms 6808 KB Output is correct
7 Execution timed out 4050 ms 27220 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 2492 KB Output is correct
6 Correct 868 ms 6808 KB Output is correct
7 Execution timed out 4050 ms 27220 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Execution timed out 4100 ms 13064 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 33 ms 3608 KB Output is correct
8 Correct 34 ms 3604 KB Output is correct
9 Correct 34 ms 3420 KB Output is correct
10 Correct 35 ms 3548 KB Output is correct
11 Correct 34 ms 3420 KB Output is correct
12 Correct 34 ms 3512 KB Output is correct
13 Correct 34 ms 3420 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 883 ms 6768 KB Output is correct
6 Runtime error 59 ms 13816 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 29 ms 6344 KB Output is correct
7 Runtime error 30 ms 7984 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -