oj.uz

Submission #1064635

# Submission time Handle Problem Language Result Execution time Memory
1064635 2024-08-18T15:55:39 Z n1k Comparing Plants (IOI20_plants) C++17
5 / 100
 2342 ms 118976 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct E {
	ll x = 1e15, lz=0;
	E(){};
	E(ll xx){x=xx;};
	friend E operator+(E a, E b){
		return min(a.x, b.x);
	}
	void aply(ll add){
		x+=add;
		lz+=add;
	}
};

struct node{
	int lb, rb;
	E x;
	node *l=nullptr, *r=nullptr;
	bool ext(){
		if(lb<rb and not l){
			int mb = (lb + rb) / 2;
			l = new node{lb, mb}, r = new node{mb+1, rb};
		}
		// push
		if(l){
			l->x.aply(x.lz);
			r->x.aply(x.lz);
			x.lz=0;
		}
		return l;
	}
	E qry(int lo, int hi){
		if(hi<lb or rb<lo) return E();
		if(lo<=lb and rb<=hi) return x;
		if(ext()) {
			E y = l->qry(lo, hi) + r->qry(lo, hi);
			return y;
		}
		return E();
	}
	void upd(int lo, int hi, ll add){
		if(hi<lb or rb<lo) return;
		if(lo<=lb and rb<=hi) {
			x.aply(add);
			return;
		}
		if(ext()) {
			l->upd(lo, hi, add), r->upd(lo, hi, add);
			x = l->x + r->x;
		}
	}
	void bld(vector<int> &v){
		if(lb==rb) x.x = v[lb];
		if(ext()) {
			l->bld(v), r->bld(v);
			x = l->x + r->x;
		}
	}
};

vector<int> h;
vector<vector<int>> jl, jr;
int K;

void init(int k, std::vector<int> r) {
	K = k;
	int n = r.size(), t=n;
	node seg{0, n-1};
	seg.bld(r);
	h.assign(n, 0);

	auto find = [&](int lb, int rb){
		while(lb<rb){
			int mb = (lb+rb+1)/2;
			if(seg.qry(mb, rb).x==0){
				lb=mb;
			}else{
				rb=mb-1;
			}
		}
		return seg.qry(lb, lb).x==0 ? lb : int(-1e9);
	};
	function<void(int)> get = [&](int id){
		// find 0 in range (id-k+1, id-1)
		// if (id-k+1)<0
		int lb = id - k + 1, rb = id-1;

		while(1){
			int nid = -1e9;
			if(rb>=0){
				nid = max(nid, find(max(lb, 0), rb));
			}if(lb<0 and nid<0){
				nid=max(nid, find((lb+n)%n, n-1));
			}

			if(nid>=0)
				get(nid);
			else
				break;
		}
		if(rb>=0){
			seg.upd(max(lb, 0), rb, -1);
		}if(lb<0){
			seg.upd((lb+n)%n, n-1, -1);
		}
		seg.upd(id, id, 1e9);
		h[id]=t--;
	};
	while(find(0, n-1)>=0){
		//cerr << find(0, n-1) << endl;
		get(find(0, n-1));
		//for(int i=0; i<n; i++) cerr << seg.qry(i, i).x << " "; cout << endl;
	}
	//for(auto x:h) cerr << x-1 << " "; cerr<<endl;

	node best{0, n-1};
	vector<int> pos(n+1);
	for(int i=0; i<n; i++) pos[h[i]] = i;
	auto findbest = [&](int lb, int rb){
		// TODO: check query outside the tree
		ll cur = best.qry(lb, rb).x;
		if(rb>=n) {
			cur = min(cur, best.qry(0, rb%n).x);
		}if(lb<0){
			cur=min(cur, best.qry((lb+n)%n, n-1).x);
		}
		return cur;
	};
	jl.assign(n, vector<int>(20));
	jr.assign(n, vector<int>(20));
	for(int i=n; i>0; i--){
		ll r = findbest(pos[i]+1, pos[i]+k-1);
		ll l = findbest(pos[i]-k+1, pos[i]-1);
		if(r>n) jr[pos[i]][0] = pos[i];
		else jr[pos[i]][0] = pos[r];
		if(l>n) jl[pos[i]][0] = pos[i];
		else jl[pos[i]][0] = pos[l];
		best.upd(pos[i], pos[i], -1e15 + i);
	}
	for(auto y:h) cerr << y-1 << " "; cerr << endl;
	for(int i=0; i<n; i++) cerr << jr[i][0] << " "; cerr << endl;
	for(int i=0; i<n; i++) cerr << jl[i][0] << " "; cerr << endl;

	for(int k=1; k<20; k++){
		for(int i=0; i<n; i++){
			jl[i][k] = jl[jl[i][k-1]][k-1];
			jr[i][k] = jr[jr[i][k-1]][k-1];
		}
	}
}

int compare_plants(int x, int y) {
	// go from x to y right
	int mul = 1;
	if(x>y){
		mul=-1;
		swap(x, y);
	}
	int ans = 0;
	int xx = x;
	for(int i=19; i>=0; i--){
		if(jr[xx][i]<y and jr[xx][i]>x){
			xx=jr[xx][i];
		}
	}
	if(xx < y and y<xx+K and h[xx]<h[y]){
		ans=-1;
	}
	int yy = y;
	for(int i=19; i>=0; i--){
		if(x < jl[yy][i] and jl[yy][i]<y){
			yy=jl[yy][i];
		}
	}
	if(yy - K < x and x < yy and h[x] > h[yy]){
		ans=1;
	}
	yy = y;
	for(int i=19; i>=0; i--){
		if(y < jr[yy][i] or jr[yy][i] < x){
			yy=jr[yy][i];
		}
	}
	
	if(((yy < x and x < yy + K) or (x < yy and yy + K >= h.size() and x < (yy + K) % h.size())) and h[yy] < h[x]){
		ans=1;
	}
	xx = x;
	for(int i=19; i>=0; i--){
		if(jl[xx][i]<x or y<jl[xx][i]){
			xx = jl[xx][i];
		}
	}
	
	if(((y < xx and xx - K < y) or (xx < y and xx-K < 0 and (xx-K+int(h.size())) % h.size() < y)) and h[y]>h[xx]){
		ans=-1;
	}
	return ans * mul;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:146:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  146 |  for(auto y:h) cerr << y-1 << " "; cerr << endl;
      |  ^~~
plants.cpp:146:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  146 |  for(auto y:h) cerr << y-1 << " "; cerr << endl;
      |                                    ^~~~
plants.cpp:147:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  147 |  for(int i=0; i<n; i++) cerr << jr[i][0] << " "; cerr << endl;
      |  ^~~
plants.cpp:147:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  147 |  for(int i=0; i<n; i++) cerr << jr[i][0] << " "; cerr << endl;
      |                                                  ^~~~
plants.cpp:148:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  148 |  for(int i=0; i<n; i++) cerr << jl[i][0] << " "; cerr << endl;
      |  ^~~
plants.cpp:148:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  148 |  for(int i=0; i<n; i++) cerr << jl[i][0] << " "; cerr << endl;
      |                                                  ^~~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:191:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |  if(((yy < x and x < yy + K) or (x < yy and yy + K >= h.size() and x < (yy + K) % h.size())) and h[yy] < h[x]){
      |                                             ~~~~~~~^~~~~~~~~~~
plants.cpp:191:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |  if(((yy < x and x < yy + K) or (x < yy and yy + K >= h.size() and x < (yy + K) % h.size())) and h[yy] < h[x]){
      |                                                                    ~~^~~~~~~~~~~~~~~~~~~~~
plants.cpp:201:90: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  201 |  if(((y < xx and xx - K < y) or (xx < y and xx-K < 0 and (xx-K+int(h.size())) % h.size() < y)) and h[y]>h[xx]){
      |                                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 74 ms 4024 KB Output is correct
7 Correct 261 ms 14508 KB Output is correct
8 Correct 1974 ms 97120 KB Output is correct
9 Correct 2029 ms 97128 KB Output is correct
10 Correct 2041 ms 97736 KB Output is correct
11 Correct 1981 ms 100888 KB Output is correct
12 Correct 1971 ms 108488 KB Output is correct
13 Correct 1779 ms 118976 KB Output is correct
14 Correct 2342 ms 97260 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.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 448 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 20 ms 1316 KB Output is correct
8 Incorrect 27 ms 1416 KB Output isn't correct
9 Halted 0 ms 0 KB -

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 Incorrect 9 ms 892 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 74 ms 4024 KB Output is correct
7 Correct 261 ms 14508 KB Output is correct
8 Correct 1974 ms 97120 KB Output is correct
9 Correct 2029 ms 97128 KB Output is correct
10 Correct 2041 ms 97736 KB Output is correct
11 Correct 1981 ms 100888 KB Output is correct
12 Correct 1971 ms 108488 KB Output is correct
13 Correct 1779 ms 118976 KB Output is correct
14 Correct 2342 ms 97260 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Incorrect 1 ms 344 KB Output isn't correct
20 Halted 0 ms 0 KB -