oj.uz

Submission #1038335

# Submission time Handle Problem Language Result Execution time Memory
1038335 2024-07-29T16:56:52 Z Dan4Life Comparing Plants (IOI20_plants) C++17
100 / 100
 1852 ms 81488 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 mxLg = (int)19;
const int INF = (int)1e9;
int n, k, h[mxN*2];
int jmp[2][mxLg][mxN*2];

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--;
}

void init(int K, vector<int> r){
	n = sz(r); k=K-1; cur = n; 
	memset(jmp,-1, sizeof jmp);
	segTree.init(); 
	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 = n; i < 2*n; i++) h[i] = h[i-n];
	set<ar2> S; int j = 0;
	for(int i = 0; i < 2*n; i++){
		while(j<2*n and abs(i-j)<=k)
			S.insert({h[j],j}),j++;
		S.erase({h[i],i});
		auto itr = S.lower_bound({h[i],i});
		if(itr!=end(S)) jmp[0][0][i]=(*itr)[1];
		if(itr!=begin(S)) jmp[1][0][i]=(*prev(itr))[1];
	}
	for(int t = 0; t < 2; t++)
		for(int i = 1; i < mxLg; i++)
			for(int j = 0; j < 2*n; j++)
				if(jmp[t][i-1][j]!=-1) jmp[t][i][j]
					=jmp[t][i-1][jmp[t][i-1][j]];
}

int comp(int x, int y, bool g){
	for(int i = mxLg-1; i>=0; i--){
		int j = jmp[g][i][x];
		if(j!=-1 and j<=y) x=j;
	}
	return y-x<=k and (g?h[x]>=h[y]:h[x]<=h[y]);
}

int compare_plants(int x, int y){
	if(comp(x,y,1) or comp(y,x+n,0)) return 1;
	if(comp(x,y,0) or comp(y,x+n,1)) 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64092 KB Output is correct
2 Correct 8 ms 64092 KB Output is correct
3 Correct 8 ms 64048 KB Output is correct
4 Correct 8 ms 64088 KB Output is correct
5 Correct 8 ms 64024 KB Output is correct
6 Correct 55 ms 67796 KB Output is correct
7 Correct 102 ms 69200 KB Output is correct
8 Correct 349 ms 71248 KB Output is correct
9 Correct 350 ms 71332 KB Output is correct
10 Correct 390 ms 71412 KB Output is correct
11 Correct 356 ms 71248 KB Output is correct
12 Correct 365 ms 71248 KB Output is correct
13 Correct 338 ms 71508 KB Output is correct
14 Correct 382 ms 71252 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64092 KB Output is correct
2 Correct 8 ms 64188 KB Output is correct
3 Correct 8 ms 64044 KB Output is correct
4 Correct 9 ms 64196 KB Output is correct
5 Correct 8 ms 64092 KB Output is correct
6 Correct 12 ms 64344 KB Output is correct
7 Correct 85 ms 69072 KB Output is correct
8 Correct 10 ms 64132 KB Output is correct
9 Correct 13 ms 64348 KB Output is correct
10 Correct 85 ms 69004 KB Output is correct
11 Correct 61 ms 68996 KB Output is correct
12 Correct 98 ms 69364 KB Output is correct
13 Correct 82 ms 69200 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64092 KB Output is correct
2 Correct 8 ms 64188 KB Output is correct
3 Correct 8 ms 64044 KB Output is correct
4 Correct 9 ms 64196 KB Output is correct
5 Correct 8 ms 64092 KB Output is correct
6 Correct 12 ms 64344 KB Output is correct
7 Correct 85 ms 69072 KB Output is correct
8 Correct 10 ms 64132 KB Output is correct
9 Correct 13 ms 64348 KB Output is correct
10 Correct 85 ms 69004 KB Output is correct
11 Correct 61 ms 68996 KB Output is correct
12 Correct 98 ms 69364 KB Output is correct
13 Correct 82 ms 69200 KB Output is correct
14 Correct 183 ms 69716 KB Output is correct
15 Correct 1781 ms 77988 KB Output is correct
16 Correct 202 ms 69716 KB Output is correct
17 Correct 1852 ms 77984 KB Output is correct
18 Correct 1000 ms 76284 KB Output is correct
19 Correct 1192 ms 77008 KB Output is correct
20 Correct 1675 ms 81488 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64192 KB Output is correct
2 Correct 8 ms 64192 KB Output is correct
3 Correct 67 ms 68692 KB Output is correct
4 Correct 570 ms 74132 KB Output is correct
5 Correct 833 ms 71708 KB Output is correct
6 Correct 1127 ms 71760 KB Output is correct
7 Correct 1623 ms 72364 KB Output is correct
8 Correct 1773 ms 76372 KB Output is correct
9 Correct 570 ms 71612 KB Output is correct
10 Correct 613 ms 71508 KB Output is correct
11 Correct 317 ms 71508 KB Output is correct
12 Correct 556 ms 71764 KB Output is correct
13 Correct 827 ms 74416 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 64088 KB Output is correct
2 Correct 7 ms 63968 KB Output is correct
3 Correct 7 ms 64048 KB Output is correct
4 Correct 8 ms 64092 KB Output is correct
5 Correct 7 ms 64092 KB Output is correct
6 Correct 8 ms 64304 KB Output is correct
7 Correct 19 ms 65052 KB Output is correct
8 Correct 17 ms 65116 KB Output is correct
9 Correct 18 ms 65116 KB Output is correct
10 Correct 17 ms 65076 KB Output is correct
11 Correct 23 ms 65116 KB Output is correct
12 Correct 19 ms 65112 KB Output is correct
13 Correct 17 ms 65112 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 64092 KB Output is correct
2 Correct 7 ms 64000 KB Output is correct
3 Correct 7 ms 64092 KB Output is correct
4 Correct 7 ms 64220 KB Output is correct
5 Correct 10 ms 64240 KB Output is correct
6 Correct 716 ms 70604 KB Output is correct
7 Correct 1063 ms 70996 KB Output is correct
8 Correct 1428 ms 71508 KB Output is correct
9 Correct 1670 ms 75544 KB Output is correct
10 Correct 602 ms 70740 KB Output is correct
11 Correct 1124 ms 74936 KB Output is correct
12 Correct 496 ms 74012 KB Output is correct
13 Correct 746 ms 70924 KB Output is correct
14 Correct 1010 ms 70996 KB Output is correct
15 Correct 1398 ms 71516 KB Output is correct
16 Correct 519 ms 70484 KB Output is correct
17 Correct 702 ms 70740 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 64092 KB Output is correct
2 Correct 8 ms 64092 KB Output is correct
3 Correct 8 ms 64048 KB Output is correct
4 Correct 8 ms 64088 KB Output is correct
5 Correct 8 ms 64024 KB Output is correct
6 Correct 55 ms 67796 KB Output is correct
7 Correct 102 ms 69200 KB Output is correct
8 Correct 349 ms 71248 KB Output is correct
9 Correct 350 ms 71332 KB Output is correct
10 Correct 390 ms 71412 KB Output is correct
11 Correct 356 ms 71248 KB Output is correct
12 Correct 365 ms 71248 KB Output is correct
13 Correct 338 ms 71508 KB Output is correct
14 Correct 382 ms 71252 KB Output is correct
15 Correct 8 ms 64092 KB Output is correct
16 Correct 8 ms 64188 KB Output is correct
17 Correct 8 ms 64044 KB Output is correct
18 Correct 9 ms 64196 KB Output is correct
19 Correct 8 ms 64092 KB Output is correct
20 Correct 12 ms 64344 KB Output is correct
21 Correct 85 ms 69072 KB Output is correct
22 Correct 10 ms 64132 KB Output is correct
23 Correct 13 ms 64348 KB Output is correct
24 Correct 85 ms 69004 KB Output is correct
25 Correct 61 ms 68996 KB Output is correct
26 Correct 98 ms 69364 KB Output is correct
27 Correct 82 ms 69200 KB Output is correct
28 Correct 183 ms 69716 KB Output is correct
29 Correct 1781 ms 77988 KB Output is correct
30 Correct 202 ms 69716 KB Output is correct
31 Correct 1852 ms 77984 KB Output is correct
32 Correct 1000 ms 76284 KB Output is correct
33 Correct 1192 ms 77008 KB Output is correct
34 Correct 1675 ms 81488 KB Output is correct
35 Correct 8 ms 64192 KB Output is correct
36 Correct 8 ms 64192 KB Output is correct
37 Correct 67 ms 68692 KB Output is correct
38 Correct 570 ms 74132 KB Output is correct
39 Correct 833 ms 71708 KB Output is correct
40 Correct 1127 ms 71760 KB Output is correct
41 Correct 1623 ms 72364 KB Output is correct
42 Correct 1773 ms 76372 KB Output is correct
43 Correct 570 ms 71612 KB Output is correct
44 Correct 613 ms 71508 KB Output is correct
45 Correct 317 ms 71508 KB Output is correct
46 Correct 556 ms 71764 KB Output is correct
47 Correct 827 ms 74416 KB Output is correct
48 Correct 7 ms 64088 KB Output is correct
49 Correct 7 ms 63968 KB Output is correct
50 Correct 7 ms 64048 KB Output is correct
51 Correct 8 ms 64092 KB Output is correct
52 Correct 7 ms 64092 KB Output is correct
53 Correct 8 ms 64304 KB Output is correct
54 Correct 19 ms 65052 KB Output is correct
55 Correct 17 ms 65116 KB Output is correct
56 Correct 18 ms 65116 KB Output is correct
57 Correct 17 ms 65076 KB Output is correct
58 Correct 23 ms 65116 KB Output is correct
59 Correct 19 ms 65112 KB Output is correct
60 Correct 17 ms 65112 KB Output is correct
61 Correct 69 ms 68728 KB Output is correct
62 Correct 104 ms 69204 KB Output is correct
63 Correct 482 ms 71296 KB Output is correct
64 Correct 723 ms 71508 KB Output is correct
65 Correct 1103 ms 71668 KB Output is correct
66 Correct 1417 ms 72376 KB Output is correct
67 Correct 1683 ms 76372 KB Output is correct
68 Correct 673 ms 72020 KB Output is correct
69 Correct 1081 ms 75868 KB Output is correct
70 Correct 590 ms 74580 KB Output is correct
71 Correct 829 ms 71764 KB Output is correct
72 Correct 1154 ms 71764 KB Output is correct
73 Correct 1480 ms 72596 KB Output is correct
74 Correct 555 ms 71508 KB Output is correct
75 Correct 723 ms 71508 KB Output is correct