Submission #1215844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215844		byunjaewoo	Teams (IOI15_teams)	C++20	0 / 100	1641 ms	348644 KiB

teams

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

const int N=500010, S=1<<19;
int n=0;
vector<int> vec[N];

class PST {
public:
	struct Node {
		Node *l, *r;
		int val;
	};
	Node *root[N];
	void update(int k, int v) {Node *node=update(root[k], 0, S-1, v); root[k]=node;}
	int query(int k, int l, int r) {return query(root[k], 0, S-1, l, r);}
	int query(int s, int e, int l, int r) {
		if(!s) return query(e, l, r);
		return query(e, l, r)-query(s-1, l, r);
	}
private:
	Node* update(Node *prev, int s, int e, int k) {
		Node *curr=new Node();
		if(prev) curr->l=prev->l, curr->r=prev->r, curr->val=prev->val+1;
		else curr->val=1;
		if(s==e) return curr;
		int m=(s+e)/2;
		if(k<=m) curr->l=update(prev?prev->l:NULL, s, m, k);
		else curr->r=update(prev?prev->r:NULL, m+1, e, k);
		return curr;
	}
	int query(Node *node, int s, int e, int l, int r) {
		if(!node || s>r || l>e) return 0;
		if(l<=s && e<=r) return node->val;
		int m=(s+e)/2;
		return query(node->l, s, m, l, r)+query(node->r, m+1, e, l, r);
	}
}T;

void init(int N, int A[], int B[]) {
	n=N;
	for(int i=0; i<N; i++) vec[A[i]].push_back(B[i]);
	for(int i=0; i<N; i++) {
		T.root[i]=T.root[i-1];
		for(int j:vec[i]) T.update(i, j);
	}
}

int can(int M, int K[]) {
	vector<int> vec;
	vector<array<int, 3>> stk;
	stk.push_back({-1, n, 0});
	for(int i=0; i<M; i++) vec.push_back(K[i]);
	sort(vec.begin(), vec.end());
	for(int i=0; i<vec.size(); i++) {
		int x=vec[i], sum=vec[i], p=i, d=0;
		for(int j=i+1; j<vec.size() && vec[i]==vec[j]; j++) p=j, sum+=x;
		while(!stk.empty()) {
			int tmp=T.query(stk.back()[0]+1, x, d, stk.back()[1]);
			if(tmp<=sum) sum-=tmp, sum+=stk.back()[2], d=stk.back()[1]+1, stk.pop_back();
			else break;
		}
		if(stk.empty() && sum) return false;
		int h=d, v=0;
		for(int s=d, e=stk.back()[1]; s<=e; ) {
			int m=(s+e)/2;
			int tmp=T.query(stk.back()[0]+1, x, d, m);
			if(tmp<=sum) h=m, v=sum-tmp, s=m+1;
			else e=m-1;
		}
		stk.push_back({x, h, v});
		i=p;
	}
	return true;
}

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