oj.uz

Submission #57443

# Submission time Handle Problem Language Result Execution time Memory
57443 2018-07-15T04:44:31 Z 정원준(#1673) Teams (CEOI11_tea) C++11
0 / 100
 936 ms 87448 KB 
#include <bits/stdc++.h>
#define L long long

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\n",a[i].gp,a[i].ord);
		pair<L,L>temp;
		if(a[i].gp>=i)
		{
			temp=pair<L,L>(1,0);
		}
		else
		{
			//puts("1");
		 	temp=gt(1,1,n,1,i-a[i].gp);
		 	temp.first++;
		}
		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:105: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:106:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ansv.size();i++)
          ~^~~~~~~~~~~~
tea.cpp:108: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:109:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<ansv[i].size();j++)
           ~^~~~~~~~~~~~~~~
tea.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
tea.cpp:65: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 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 432 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 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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