oj.uz

Submission #244592

# Submission time Handle Problem Language Result Execution time Memory
244592 2020-07-04T10:29:16 Z TadijaSebez Teams (CEOI11_tea) C++11
100 / 100
 1012 ms 153324 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=1000050;
const int inf=1e9+7;
void ckmx(int&x,int y){x=max(x,y);}
int a[N],ord[N],n,dp[N],go[N],dp_sz[N];
int myx(int x,int y,int t){
	if(x==-1)return y;
	if(y==-1)return x;
	if(dp[x]>dp[y])return x;
	if(dp[y]>dp[x])return y;
	if(t==1){
		if(dp_sz[x]<dp_sz[y])return x;
		else return y;
	}else{
		if(x>y)return x;
		else return y;
	}
	//return x==-1?y:y==-1?x:mp(dp[x],t==1?-dp_sz[x]:x)>mp(dp[y],t==1?-dp_sz[y]:y)?x:y;
}
struct ST{
	int sgt[N*2],t;
	void cl(){for(int i=1;i<n*2;i++)sgt[i]=-1;}
	void Set(int i,int f){i+=n;sgt[i]=f;for(i>>=1;i;i>>=1)sgt[i]=myx(sgt[i<<1],sgt[i<<1|1],t);}
	int Get(int l,int r){
		l=max(l,0);r=min(r,n-1);
		int ans=-1;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l%2==1)ans=myx(ans,sgt[l++],t);
			if(r%2==0)ans=myx(ans,sgt[r--],t);
		}
		return ans;
	}
}ST1;
struct BT{
	int bit[N],t;
	void cl(){for(int i=1;i<=n;i++)bit[i]=-1;}
	void Set(int i,int f){for(i++;i<=n;i+=i&-i)bit[i]=myx(bit[i],f,t);}
	int Get(int l,int r){int ans=-1;for(r++;r>0;r-=r&-r)ans=myx(ans,bit[r],t);return ans;}
}ST2;
vector<int> izb[N];
int DP(){
	dp[0]=0;
	dp_sz[0]=0;
	ST1.cl();ST2.cl();
	for(int i=1;i<=n;i++){
		ST1.Set(i-1,i-1);
		for(int j:izb[i]){
			ST1.Set(j,-1);
			ST2.Set(j,j);
		}
		dp[i]=-inf;
		//go[i]=Get(i-lim,i-a[i]);
		//if(go[i]!=-1)dp[i]=dp[go[i]]+1;
		/*for(int j=0;j<=i-a[i];j++){
			if(dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
				dp_sz[i]=max(dp_sz[j],i-j);
				go[i]=j;
			}else if(dp[i]==dp[j]+1){
				if(dp_sz[i]>max(dp_sz[j],i-j))
					dp_sz[i]=max(dp_sz[j],i-j),
					go[i]=j;
			}
		}*/
		auto cons=[&](int j){
			if(dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
				dp_sz[i]=max(dp_sz[j],i-j);
				go[i]=j;
			}else if(dp[i]==dp[j]+1){
				if(dp_sz[i]>max(dp_sz[j],i-j))
					dp_sz[i]=max(dp_sz[j],i-j),
					go[i]=j;
			}
		};
		int j=ST1.Get(0,i-a[i]);
		if(j!=-1)cons(j);
		int k=ST2.Get(0,i-a[i]);
		if(k!=-1)cons(k);
		if(dp[i]>=0){
			if(i+dp_sz[i]<=n)
				izb[i+dp_sz[i]].pb(i);
		}
	}
	return dp[n];
}
int main(){
	ST1.t=1;
	ST2.t=2;
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),ord[i]=i;
	sort(ord+1,ord+1+n,[&](int i,int j){return a[i]<a[j];});
	sort(a+1,a+1+n);
	DP();
	vector<vector<int>> sol;
	for(int i=n;i>0;i=go[i]){
		vector<int> tmp;
		for(int j=i;j>go[i];j--)
			tmp.push_back(ord[j]);
		sol.push_back(tmp);
	}
	printf("%i\n",sol.size());
	for(auto v:sol){
		printf("%i ",v.size());
		for(int i:v)printf("%i ",i);
		printf("\n");
	}
	return 0;
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:105:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%i\n",sol.size());
                ~~~~~~~~~~^
tea.cpp:107:24: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%i ",v.size());
                ~~~~~~~~^
tea.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
tea.cpp:94:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&a[i]),ord[i]=i;
                       ~~~~~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 24 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 19 ms 23924 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24192 KB Output is correct
2 Correct 24 ms 24184 KB Output is correct
3 Correct 24 ms 24320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24192 KB Output is correct
2 Correct 30 ms 24192 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28700 KB Output is correct
2 Correct 79 ms 29944 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 29816 KB Output is correct
2 Correct 77 ms 29816 KB Output is correct
3 Correct 89 ms 29948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 81876 KB Output is correct
2 Correct 630 ms 81968 KB Output is correct
3 Correct 677 ms 77008 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 95036 KB Output is correct
2 Correct 990 ms 153324 KB Output is correct
3 Correct 833 ms 100816 KB Output is correct
4 Correct 883 ms 92684 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 74512 KB Output is correct
2 Correct 448 ms 69904 KB Output is correct
3 Correct 845 ms 101368 KB Output is correct
4 Correct 1012 ms 101720 KB Output is correct