oj.uz

답안 #1037769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037769 2024-07-29T08:11:31 Z Dan4Life 식물 비교 (IOI20_plants) C++17
0 / 100
 4000 ms 32096 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];
bitset<mxN> path[2];
vector<int> adj[mxN], radj[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)); }
bitset<mxN> vis;

void dfs(int s){
	vis[s]=1;
	path[0][s]=1;
	for(auto u : adj[s])
		if(!vis[u]) dfs(u);
}

void dfs2(int s){
	vis[s]=1;
	path[1][s]=1;
	for(auto u : radj[s])
		if(!vis[u]) dfs2(u);
}

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)
				adj[i].pb(j), radj[j].pb(i);
	dfs(0); vis.reset(); dfs2(0);
}

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

Compilation message

plants.cpp: In member function 'void SegTree<T, SZ>::upd(int, int, int, int, int, int)':
plants.cpp:30:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   30 |   if(i>r or j<l or i>j) return; prop(p,l,r);
      |   ^~
plants.cpp:30:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |   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:39:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |   if(i>r or j<l or i>j) return -1; prop(p,l,r);
      |   ^~
plants.cpp:39:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |   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:49:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |   if(j<l or i>r or i>j) return INF; prop(p,l,r);
      |   ^~
plants.cpp:49:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |   if(j<l or i>r or i>j) return INF; prop(p,l,r);
      |                                     ^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12976 KB Output is correct
3 Incorrect 2 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Incorrect 2 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Incorrect 2 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Incorrect 2 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 8 ms 14172 KB Output is correct
6 Execution timed out 4100 ms 32096 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12976 KB Output is correct
3 Incorrect 2 ms 12892 KB Output isn't correct
4 Halted 0 ms 0 KB -