oj.uz

Submission #432112

# Submission time Handle Problem Language Result Execution time Memory
432112 2021-06-17T21:11:10 Z alishahali1382 Comparing Plants (IOI20_plants) C++14
14 / 100
 2120 ms 71788 KB 
#include "plants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=200010, LOG=18;

int n, m, k, x, y, u, v, t, a, b, posmx;
int A[MAXN], B[MAXN];
int mark1[MAXN], mark2[MAXN];
int L[LOG][MAXN], R[LOG][MAXN];
vector<int> G[MAXN], GR[MAXN];

struct Segment{
	pii seg[MAXN<<2];
	int lazy[MAXN<<2];
	pii Build(int id, int tl, int tr, int *A){
		if (tr-tl==1) return seg[id]={A[tl], tl};
		int mid=(tl+tr)>>1;
		return seg[id]=min(Build(id<<1, tl, mid, A), Build(id<<1 | 1, mid, tr, A));
	}
	inline void add_lazy(int id, int val){
		seg[id].first+=val;
		lazy[id]+=val;
	}
	inline void shift(int id){
		if (lazy[id]){
			add_lazy(id<<1, lazy[id]);
			add_lazy(id<<1 | 1, lazy[id]);
			lazy[id]=0;
		}
	}
	void Add(int id, int tl, int tr, int l, int r, int val){
		if (r<=tl || tr<=l) return ;
		if (l<=tl && tr<=r){
			add_lazy(id, val);
			return ;
		}
		shift(id);
		int mid=(tl+tr)>>1;
		Add(id<<1, tl, mid, l, r, val);
		Add(id<<1 | 1, mid, tr, l, r, val);
		seg[id]=min(seg[id<<1], seg[id<<1 | 1]);
	}
	pii Get(int id, int tl, int tr, int l, int r){
		if (r<=tl || tr<=l) return {inf, 0};
		if (l<=tl && tr<=r) return seg[id];
		shift(id);
		int mid=(tl+tr)>>1;
		return min(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
	}
} seg1, seg2, seg3;

void relax(){
	while (!seg1.seg[1].first){
		int mx=seg1.seg[1].second;
		// cerr<<mx<<" became 0\n";
		seg1.Add(1, 0, n, mx, mx+1, inf);
		seg2.Add(1, 0, n, mx, mx+1, -inf);
		seg2.Add(1, 0, n, mx+1, mx+k, +1);
		seg2.Add(1, 0, n, 0, mx+k-n, +1);
	}
}

inline void add_edge(int u, int v){
	G[u].pb(v);
	GR[v].pb(u);
}

void init(int _k, vi _A){
	n=SZ(_A);
	k=_k;
	for (int i=0; i<n; i++) A[i]=_A[i];
	seg1.Build(1, 0, n, A);
	seg2.Build(1, 0, n, B); // any empty array
	seg3.Build(1, 0, n, B);
	seg2.Add(1, 0, n, 0, n, inf);
	seg3.Add(1, 0, n, 0, n, inf);
	relax();
	for (int i=0; i<n; i++){
		int mx=seg2.seg[1].second;
		B[mx]=n-i;
		
		seg2.Add(1, 0, n, mx, mx+1, inf);
		seg2.Add(1, 0, n, mx+1, mx+k, -1);
		seg2.Add(1, 0, n, 0, mx+k-n, -1);
		
		seg1.Add(1, 0, n, mx-k+1, mx, -1);
		seg1.Add(1, 0, n, n+mx-k+1, n, -1);
		relax();



		seg3.Add(1, 0, n, mx, mx+1, -inf+B[mx]);
		pii l=min(seg3.Get(1, 0, n, mx-k+1, mx), seg3.Get(1, 0, n, mx-k+1+n, n));
		pii r=min(seg3.Get(1, 0, n, mx+1, mx+k), seg3.Get(1, 0, n, 0, mx+k-n));

		L[0][mx]=R[0][mx]=mx;
		if (l.first<inf) L[0][mx]=(n+mx-l.second)%n; //add_edge(mx, l.second);
		if (r.first<inf) R[0][mx]=(r.second-mx+n)%n; //add_edge(mx, r.second);
	}
	// for (int i=0; i<n; i++) cerr<<B[i]-1<<" \n"[i==n-1];
	for (int j=1; j<LOG; j++) for (int i=0; i<n; i++){
		L[j][i]=L[j-1][i] + L[j-1][(i-L[j-1][i])%n];
		R[j][i]=R[j-1][i] + R[j-1][(i+R[j-1][i])%n];
	}
	return ;
}

int compare_plants(int x, int y){
	if (B[x]>B[y]) return -compare_plants(y, x);
	int l=x, dl=(x-y+n)%n;
	int r=x, dr=(y-x+n)%n;
	for (int i=LOG-1; ~i; i--){
		if (L[i][l]<=dl){
			dl-=L[i][l];
			l=(l-L[i][l]+n)%n;
		}
		if (R[i][r]<=dr){
			dr-=R[i][r];
			r=(r+R[i][r]+n)%n;
		}
	}
	if (B[l]<=B[y] && dl<k) return -1;
	if (B[r]<=B[y] && dr<k) return -1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28624 KB Output is correct
2 Correct 14 ms 28632 KB Output is correct
3 Correct 14 ms 28672 KB Output is correct
4 Incorrect 14 ms 28620 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28632 KB Output is correct
2 Correct 14 ms 28700 KB Output is correct
3 Correct 14 ms 28632 KB Output is correct
4 Correct 14 ms 28628 KB Output is correct
5 Correct 15 ms 28616 KB Output is correct
6 Correct 22 ms 29004 KB Output is correct
7 Correct 127 ms 34316 KB Output is correct
8 Correct 18 ms 28812 KB Output is correct
9 Correct 22 ms 28876 KB Output is correct
10 Correct 123 ms 34264 KB Output is correct
11 Correct 139 ms 34176 KB Output is correct
12 Correct 138 ms 34436 KB Output is correct
13 Correct 126 ms 34336 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28632 KB Output is correct
2 Correct 14 ms 28700 KB Output is correct
3 Correct 14 ms 28632 KB Output is correct
4 Correct 14 ms 28628 KB Output is correct
5 Correct 15 ms 28616 KB Output is correct
6 Correct 22 ms 29004 KB Output is correct
7 Correct 127 ms 34316 KB Output is correct
8 Correct 18 ms 28812 KB Output is correct
9 Correct 22 ms 28876 KB Output is correct
10 Correct 123 ms 34264 KB Output is correct
11 Correct 139 ms 34176 KB Output is correct
12 Correct 138 ms 34436 KB Output is correct
13 Correct 126 ms 34336 KB Output is correct
14 Correct 220 ms 37480 KB Output is correct
15 Incorrect 2120 ms 71788 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28620 KB Output is correct
2 Correct 19 ms 28620 KB Output is correct
3 Correct 131 ms 33564 KB Output is correct
4 Correct 1054 ms 71084 KB Output is correct
5 Incorrect 1289 ms 70072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28620 KB Output is correct
2 Correct 17 ms 28608 KB Output is correct
3 Incorrect 18 ms 28680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28624 KB Output is correct
2 Correct 14 ms 28632 KB Output is correct
3 Correct 14 ms 28672 KB Output is correct
4 Incorrect 14 ms 28620 KB Output isn't correct
5 Halted 0 ms 0 KB -