oj.uz

Submission #306053

# Submission time Handle Problem Language Result Execution time Memory
306053 2020-09-24T11:51:57 Z gs18115 Comparing Plants (IOI20_plants) C++14
0 / 100
 123 ms 16376 KB 
#include"plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
	pi t[mx*4];
	int lz[mx*4];
	void init(int n,int s,int e,vector<int>&v)
	{
		lz[n]=0;
		if(s==e)
		{
			t[n]=pi(v[s],s);
			return;
		}
		int m=s+(e-s)/2;
		init(n*2,s,m,v);
		init(n*2+1,m+1,e,v);
		t[n]=min(t[n*2],t[n*2+1]);
		return;
	}
	inline void put(int n,int p)
	{
		t[n].fi+=p;
		lz[n]+=p;
		return;
	}
	inline void prop(int n)
	{
		if(lz[n]==0)
			return;
		put(n*2,lz[n]);
		put(n*2+1,lz[n]);
		lz[n]=0;
		return;
	}
	void upd(int n,int s,int e,int S,int E,int p)
	{
		if(s>E||S>e)
			return;
		if(S<=s&&e<=E)
			return put(n,p);
		prop(n);
		int m=s+(e-s)/2;
		upd(n*2,s,m,S,E,p);
		upd(n*2+1,m+1,e,S,E,p);
		t[n]=min(t[n*2],t[n*2+1]);
		return;
	}
}st1,st2;
struct seg2
{
	int t[mx*4];
	void init(int n,int s,int e,int v)
	{
		t[n]=v;
		if(s==e)
			return;
		int m=s+(e-s)/2;
		init(n*2,s,m,v);
		init(n*2+1,m+1,e,v);
		return;
	}
	void put(int n,int s,int e,int x,int p)
	{
		if(s==e)
		{
			t[n]=p;
			return;
		}
		int m=s+(e-s)/2;
		if(x>m)
			put(n*2+1,m+1,e,x,p);
		else
			put(n*2,s,m,x,p);
		t[n]=min(t[n*2],t[n*2+1]);
		return;
	}
	int query(int n,int s,int e,int S,int E)
	{
		if(s>E||S>e)
			return inf;
		if(S<=s&&e<=E)
			return t[n];
		int m=s+(e-s)/2;
		return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
	}
}st3;
int ord[mx];
vector<int>ov;
int spa1[mx][20],spd1[mx][20];
int spa2[mx][20],spd2[mx][20];
int n;
void init(int k,vector<int>r)
{
	n=r.size();
	st1.init(1,0,n-1,r);
	st2.init(1,0,n-1,r);
	for(int i=0;i<n;i++)
	{
		while(st2.t[1].fi==0)
		{
			int cur=st2.t[1].se;
			st2.upd(1,0,n-1,cur,cur,inf);
			st1.upd(1,0,n-1,cur+1,cur+k-1,1),st1.upd(1,0,n-1,0,cur+k-1-n,1);
		}
		int cur=st1.t[1].se;
		ord[cur]=i;
		ov.eb(cur);
		st1.upd(1,0,n-1,cur,cur,inf);
		st1.upd(1,0,n-1,cur-k+1+n,n-1,-1),st1.upd(1,0,n-1,cur-k+1,cur-1,-1);
		st1.upd(1,0,n-1,cur+1,cur+k-1,-1),st1.upd(1,0,n-1,0,cur+k-1-n,-1);
		st2.upd(1,0,n-1,cur-k+1+n,n-1,-1),st2.upd(1,0,n-1,cur-k+1,cur-1,-1);
	}
	st3.init(1,0,n-1,n);
	auto get3=[&](const int&p)->int{return min(st3.query(1,0,n-1,p-k+1,p-1),
	st3.query(1,0,n-1,p-k+1+n,n-1));};
	auto get4=[&](const int&p)->int{return min(st3.query(1,0,n-1,p+1,p+k-1),
	st3.query(1,0,n-1,0,p+k-1-n));};
	ov.eb(ord[n]=n);
	for(int i=0;i<20;i++)
		spa1[n][i]=spa2[n][i]=n,spd1[n][i]=spd2[n][i]=0;
	for(int i=n;i-->0;)
	{
		int cur=ov[i];
		int nx=ov[get3(cur)];
		spa1[cur][0]=nx,spd1[cur][0]=nx>cur?1:0;
		nx=ov[get4(cur)];
		spa2[cur][0]=nx,spd2[cur][0]=nx<cur?1:0;
		st3.put(1,0,n-1,cur,i);
	}
	for(int j=0;j<19;j++)
		for(int i=0;i<=n;i++)
			spa1[i][j+1]=spa1[spa1[i][j]][j],
			spd1[i][j+1]=spd1[spa1[i][j]][j]+spd1[i][j],
			spa2[i][j+1]=spa1[spa2[i][j]][j],
			spd2[i][j+1]=spd1[spa2[i][j]][j]+spd2[i][j];
	return;
}
int compare_plants(int x,int y)
{
	int p=1;
	if(ord[x]>ord[y])
		swap(x,y),p=-1;
	int l=x,ld=0;
	int r=x,rd=0;
	for(int i=20;i-->0;)
		if(ord[spa1[l][i]]<=ord[y])
			ld+=spd1[l][i],l=spa1[l][i];
	for(int i=20;i-->0;)
		if(ord[spa2[r][i]]<=ord[y])
			rd+=spd2[r][i],r=spa2[r][i];
	l-=n*min(2,ld),r+=n*min(2,rd);
	for(int i=-1;i<=1;i++)
		if(l+i*n<=y&&y<=r+i*n)
			return p;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 8 ms 12928 KB Output is correct
4 Correct 8 ms 12928 KB Output is correct
5 Incorrect 8 ms 12928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 8 ms 12928 KB Output is correct
4 Correct 9 ms 12928 KB Output is correct
5 Correct 9 ms 12928 KB Output is correct
6 Incorrect 15 ms 13312 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 8 ms 12928 KB Output is correct
4 Correct 9 ms 12928 KB Output is correct
5 Correct 9 ms 12928 KB Output is correct
6 Incorrect 15 ms 13312 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Incorrect 123 ms 16376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 8 ms 12928 KB Output is correct
4 Correct 8 ms 12928 KB Output is correct
5 Incorrect 8 ms 12928 KB Output isn't correct
6 Halted 0 ms 0 KB -