제출 #432131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432131		alishahali1382	식물 비교 (IOI20_plants)	C++14	100 / 100	1866 ms	75056 KiB

plants

#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=20;

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

		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]=min(L[j-1][i] + L[j-1][(i-L[j-1][i]+n)%n], n);
		R[j][i]=min(R[j-1][i] + R[j-1][(i+R[j-1][i])%n], 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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25