Submission #287452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
287452	2020-08-31T17:07:42 Z	Namnamseo	Teams (CEOI11_tea)	C++17	100 / 100	941 ms	147844 KB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define data Data

const int max_n = int(1e6) + 10, inf = 1e9;

typedef pair<int,int> pp;
pp data[max_n];
int n;

int dpTN[max_n];
int dpMX[max_n];

struct indi {
	int team_num;
	int max_size;
	int from;
	indi(int a=-1, int b=inf, int c=-1){
		team_num = a; max_size = b; from = c;
	}
	bool operator<(const indi& r) const {
		return make_pair(team_num, -max_size) <
			   make_pair(r.team_num, -r.max_size);
	}
};

const int M =1048576;
indi tree[M<<1];
indi tree_add[M<<1];
indi dp[max_n];
int bef[max_n];

indi getMax(indi* tree, int p){
	indi ret;
	p+=M;
	while(p) ret=max(ret, tree[p]), p>>=1;
	return ret;
}

void upd(indi* tree, int l, int r, indi val){
	l+=M; r+=M;
	while(l<=r){
		if(l%2==1) tree[l]=max(tree[l], val), ++l;
		if(r%2==0) tree[r]=max(tree[r], val), --r;
		l>>=1; r>>=1;
	}
}

vector<vector<int>> ans;

struct cmp {
	bool operator()(const int& a, const int& b){
		return ans[a].size() > ans[b].size();
	}
};
priority_queue<int,vector<int>,cmp> PQ;

int main()
{
    read(n);
    for(int i=1; i<=n; ++i){
		read(data[i].first); data[i].second=i;
    }
    sort(data+1, data+n+1, greater<pp>());
    for(int i=0; i<=n; ++i){
		indi v1 = getMax(tree, i);
		indi v2 = getMax(tree_add, i);
		v2.max_size += i;
		indi my = max(v1, v2);
		if(i == 0) my = indi(0, 0, -1);
		dp[i] = my;
		bef[i] = my.from;
		if(i == n) break;
		if(my.team_num == -1) continue;
		int tn = my.team_num;
		int mt = my.max_size;
		ll pt = tn * 1LL * mt;
		int mv=data[i+1].first;
		upd(tree, i+1, min(pt, ll(n)), indi(tn, mt, -i));
		upd(tree, i+mv, min(i+mt-1, n), indi(tn+1, mt, i));
		upd(tree_add, i+max(mv, mt), n, indi(tn+1, -i, i));
    }
    
    printf("%d\n", dp[n].team_num);
	
	vector<pp> pend;
    int p=n;
    while(p){
		int x=bef[p];
		if(x < 0){
			x=-x;
			for(int i=x+1; i<=p; ++i){
				pend.pb(pp{int(ans.size()), data[i].second});
			}
		} else {
			vector<int> v;
			for(int i=x+1; i<=p; ++i){
				v.pb(data[i].second);
			}
			ans.pb(v);
		}
		p=x;
    }
    int an=ans.size();
    for(int i=an-1; i>=0; --i){
		PQ.push(i);
		while(pend.size()){
			int x, y;
			tie(x, y) = pend.back();
			if(x != i) break;
			pend.pop_back();
			int p=PQ.top(); PQ.pop();
			ans[p].pb(y);
			PQ.push(p);
		}
    }
    for(auto& tmp:ans){
		printf("%d ", int(tmp.size()));
		for(int x:tmp) printf("%d ", x);
		putchar(10);
	}
    return 0;
}

Compilation message

tea.cpp: In function 'void read(int&)':
tea.cpp:5:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	61312 KB	Output is correct
2	Correct	46 ms	61352 KB	Output is correct
3	Correct	44 ms	61304 KB	Output is correct
4	Correct	38 ms	61304 KB	Output is correct
5	Correct	38 ms	61304 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	61304 KB	Output is correct
2	Correct	38 ms	61304 KB	Output is correct
3	Correct	39 ms	61304 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	61304 KB	Output is correct
2	Correct	38 ms	61304 KB	Output is correct
3	Correct	42 ms	61308 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	61432 KB	Output is correct
2	Correct	44 ms	61432 KB	Output is correct
3	Correct	45 ms	61432 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	61432 KB	Output is correct
2	Correct	44 ms	61432 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	63936 KB	Output is correct
2	Correct	104 ms	63352 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	63940 KB	Output is correct
2	Correct	97 ms	63428 KB	Output is correct
3	Correct	107 ms	63812 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	768 ms	81884 KB	Output is correct
2	Correct	670 ms	81492 KB	Output is correct
3	Correct	649 ms	83264 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	898 ms	90348 KB	Output is correct
2	Correct	839 ms	147844 KB	Output is correct
3	Correct	862 ms	87476 KB	Output is correct
4	Correct	923 ms	86532 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	621 ms	92820 KB	Output is correct
2	Correct	470 ms	92048 KB	Output is correct
3	Correct	937 ms	87844 KB	Output is correct
4	Correct	941 ms	90488 KB	Output is correct