제출 #1150354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150354		mychecksedad	팀들 (IOI15_teams)	C++20	0 / 100	827 ms	358548 KiB

teams

/* Author : Mychecksdead  */
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, MX = 30;

struct Node{
	Node *L=nullptr, *R=nullptr;
	int sum=0,val=0;
	Node(){}
	Node(int v){val=sum=	v;}
	Node(Node*l,Node*r){
		L=l,R=r;
		sum+=L->sum;
		sum+=R->sum;
	}
};
int n;
Node* build(int l, int r){
	if(l==r) return new Node(0);
	int m=l+r>>1;
	return new Node(build(l, m), build(m+1, r));
}
Node* upd(Node *v, int l, int r, int p){
	if(l == r){
		return new Node(v->val+1);
	}
	int m = l+r>>1;
	if(p <= m) return new Node(upd(v->L, l, m, p), v->R);
	return new Node(v->L, upd(v->R, m+1, r, p));
}
int get(Node *v, int l, int r, int ql, int qr){
	if(ql>r||l>qr) return 0;
	if(ql<=l&&r<=qr) return v->sum;
	int m = l+r>>1;
	return get(v->L, l,m ,ql,qr)+get(v->R,m+1,r,ql,qr);
}
vector<Node*> root;
void init(int nn, int A[], int B[]) { n=nn;
	root.pb(build(1, n));
	vector<pii> V;
	for(int i = 1; i <= n; ++i){
		V.pb({A[i-1], B[i-1]});
	}
	sort(all(V));
	int ptr = 0;
	for(int i = 1; i <= n; ++i){
		root.pb(root.back());
		while(ptr < V.size() && V[ptr].ff == i){
			root.back() = upd(root.back(), 1, n, V[ptr].ss);
			++ptr;
		}
	}
}

int can(int m, int K[]) {
	int sum = 0;
	sort(K, K+m);
	bool ok = 1;
	vi c(m);
	for(int i = 0; i < m; ++i){
		sum += K[i];
		if(sum > n) return 0;
		if((c[i] = get(root[K[i]], 1, n, K[i], n)) < K[i]) ok = 0;
		if(i > 0 && - get(root[K[i - 1]], 1, n, K[i], n) + c[i] + c[i - 1] < K[i] + K[i - 1]) ok = 0;
	}
	return ok;
}

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