Submission #386766

#	Time	Username	Problem	Language	Result	Execution time	Memory
386766		alishahali1382	Teams (IOI15_teams)	C++14	77 / 100	4085 ms	134228 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<"="<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define all(x) x.begin(), x.end()
#define pb push_back

const int MAXN=500010, SQ=250, SEGSZ=10000010;

int n, m, k, x, y;
int A[MAXN], B[MAXN], C[MAXN], root[MAXN];
int seg[SEGSZ], L[SEGSZ], R[SEGSZ], ts;
int ted[SQ][SQ], cnt[SQ];
priority_queue<int, vector<int>, greater<int>> pq;

int Add(int id, int tl, int tr, int pos){
	if (pos<tl || tr<=pos) return id;
	int res=++ts;
	if (tr-tl==1){
		seg[res]=seg[id]+1;
		return res;
	}
	int mid=(tl+tr)>>1;
	L[res]=Add(L[id], tl, mid, pos);
	R[res]=Add(R[id], mid, tr, pos);
	seg[res]=seg[L[res]]+seg[R[res]];
	return res;
}
int Get(int idl, int idr, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return 0;
	if (l<=tl && tr<=r) return seg[idr]-seg[idl];
	int mid=(tl+tr)>>1;
	return Get(L[idl], L[idr], tl, mid, l, r) + Get(R[idl], R[idr], mid, tr, l, r);
}
void init(int nn, int AA[], int BB[]){
	n=nn;
	vector<pii> vec;
	for (int i=0; i<n; i++) vec.pb({AA[i], BB[i]});
	sort(all(vec));
	for (int i=0; i<n; i++) A[i+1]=vec[i].first, B[i+1]=vec[i].second;
	int j=1;
	for (int i=1; i<=n; i++){
		root[i]=root[i-1];
		while (A[j]==i) root[i]=Add(root[i], 1, n+1, B[j++]);
	}
}
bool SolveBig(){
	while (pq.size()) pq.pop();
	int j=1;
	for (int i=1; i<=m; i++){
		while (j<=n && A[j]<=C[i]) pq.push(B[j++]);
		while (pq.size() && pq.top()<C[i]) pq.pop();
		int t=C[i];
		if (pq.size()<t) return 0;
		while (t--) pq.pop();
	}
	return 1;
}
bool SolveSmall(){
	C[m+1]=n+1;
	for (int i=1; i<=m; i++) for (int j=i; j<=m; j++)
		ted[i][j]=Get(root[C[i-1]], root[C[i]], 1, n+1, C[j], C[j+1]);
	for (int i=1; i<=m; i++) cnt[i]=0;
	for (int i=1; i<=m; i++){
		for (int j=i; j<=m; j++) cnt[j]+=ted[i][j];
		int t=C[i];
		for (int j=i; j<=m && t; j++){
			int tt=min(t, cnt[j]);
			cnt[j]-=tt;
			t-=tt;
		}
		if (t) return 0;
	}
	return 1;
}
int can(int mm, int CC[]){
	m=mm;
	for (int i=0; i<m; i++) C[i+1]=CC[i];
	sort(C+1, C+m+1);
	if (m>=SQ) return SolveBig();
	return SolveSmall();
}

Compilation message (stderr)

teams.cpp: In function 'bool SolveBig()':
teams.cpp:59:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   if (pq.size()<t) return 0;
      |       ~~~~~~~~~^~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23