oj.uz

Submission #57459

# Submission time Handle Problem Language Result Execution time Memory
57459 2018-07-15T05:48:51 Z 정원준(#1673) Teams (CEOI11_tea) C++11
0 / 100
 938 ms 87356 KB 
#include <bits/stdc++.h>
#define L long long
#define inf 80000000000000000L

using namespace std;

struct S{
	L gp,ord;
}a[1000010];

bool operator<(S a,S b){
	return a.gp<b.gp;
}

bool cmp(S a,S b){
	return a.ord<b.ord;
}

L n;
L back[1000010];

L tr[4000040],trd[4000040];
pair<L,L>ans[1000010];
vector<vector<L> >ansv;

pair<L,L> gt(L now,L S,L E,L s,L e){
	if(S>e||E<s) return pair<L,L>(0,0);
	if(s<=S&&E<=e) return pair<L,L>(tr[now],trd[now]);
	L mid=(S+E)/2;
	pair<L,L> temp1=gt(now*2,S,mid,s,e);
	pair<L,L> temp2=gt(now*2+1,mid+1,E,s,e);
	if(temp1.first>temp2.first)
		return temp1;
	else return temp2;
}

void update(L now,L S,L E,L loc,L val){
	if(S>loc||E<loc) return;
	if(S==E)
	{
		tr[now]=val;
		trd[now]=S;
	}
	if(S==E) return;
	L mid=(S+E)/2;
	update(now*2,S,mid,loc,val);
	update(now*2+1,mid+1,E,loc,val);
	if(tr[now*2]>tr[now*2+1])
	{
		tr[now]=tr[now*2];
		trd[now]=trd[now*2];
	}
	else
	{
		tr[now]=tr[now*2+1];
		trd[now]=trd[now*2+1];
	}
}

int main()
{
	scanf("%lld",&n);
	L i,j;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i].gp);
		a[i].ord=i;
	}
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	{
		back[i]=a[i].ord;
		//printf("%lld ",back[i]);
	}
	//puts("");
	for(i=1;i<=n;i++)
	{
		//printf("%lld %lld ",a[i].gp,a[i].ord);
		pair<L,L>temp;
		if(a[i].gp>i)
		{
			temp=pair<L,L>(-inf,0);
		}
		else
		{
			//puts("1");
		 	temp=gt(1,1,n,1,i-a[i].gp);
		 	temp.first++;
		}
		//printf("%lld %lld\n",temp.first,temp.second);
		ans[i]=temp;
		update(1,1,n,i,temp.first);
	}
	L prev=n;
	pair<L,L> temp=ans[n];
	while(prev>0)
	{
		vector<L>newv;
		ansv.push_back(newv);
		for(i=temp.second+1;i<=prev;i++)
		{
			ansv[ansv.size()-1].push_back(i);
		}
		prev=temp.second;
		temp=ans[temp.second];
	}
	printf("%lld\n",ansv.size());
	for(i=0;i<ansv.size();i++)
	{
		printf("%lld ",ansv[i].size());
		for(j=0;j<ansv[i].size();j++)
		{
			printf("%lld ",back[ansv[i][j]]);
		}
		puts("");
	}
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:107:29: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'std::vector<std::vector<long long int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%lld\n",ansv.size());
                  ~~~~~~~~~~~^
tea.cpp:108:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ansv.size();i++)
          ~^~~~~~~~~~~~
tea.cpp:110:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'std::vector<long long int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%lld ",ansv[i].size());
                  ~~~~~~~~~~~~~~^
tea.cpp:111:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<ansv[i].size();j++)
           ~^~~~~~~~~~~~~~~
tea.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
tea.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i].gp);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1128 KB Output is correct
2 Incorrect 6 ms 1144 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 9096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 9736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 789 ms 74632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 796 ms 87356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 938 ms 87356 KB Output isn't correct
2 Halted 0 ms 0 KB -