Submission #1277298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277298		papaulo	팀들 (IOI15_teams)	C++20	100 / 100	844 ms	309288 KiB

teams

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

struct Node {
	vector<int> vals;
	vector<pair<int, int>> mp;
	int debt, lazy;
};

#define MAXN 500500
vector<int> byb[MAXN];
Node nodes[4*MAXN];

int gn=0;

void build(int n, int l, int r) {
	Node &nd=nodes[n];
	nd.debt=nd.lazy=0;
	nd.vals.clear();
	nd.mp.clear();
	if(l==r) {
		nd.vals=byb[l];
		sort(nd.vals.begin(), nd.vals.end());
		return;
	}
	int mid=(l+r)/2;
	build(2*n, l, mid);
	build(2*n+1, mid+1, r);
	vector<int> &vl=nodes[2*n].vals, &vr=nodes[2*n+1].vals;
	int i=0, j=0;
	nd.mp.push_back({0, 0});
	while(i<(int)vl.size()&&j<(int)vr.size()) {
		if(vl[i]<=vr[j]) {
			nd.vals.push_back(vl[i]);
			++i;
		} else {
			nd.vals.push_back(vr[j]);
			++j;
		}
		nd.mp.push_back({i, j});
	}
	while(i<(int)vl.size()) {
		nd.vals.push_back(vl[i]);
		++i;
		nd.mp.push_back({i, j});
	}
	while(j<(int)vr.size()) {
		nd.vals.push_back(vr[j]);
		++j;
		nd.mp.push_back({i, j});
	}
}

void lazyPropagation(int n, int l, int r) {
	Node &nd=nodes[n];
	if(!nd.lazy) return;
	nd.lazy=0;
	if(l==r) return;
	nodes[2*n].debt=nd.mp[nd.debt].first;
	nodes[2*n+1].debt=nd.mp[nd.debt].second;
	nodes[2*n].lazy=nodes[2*n+1].lazy=1;
}

int query(int n, int l, int r, int p, int a, int s) {
	lazyPropagation(n, l, r);
	if(p>r||!s) return 0;
	Node &nd=nodes[n];
	int mid=(l+r)/2;
	if(p>l) {
		int lv=query(2*n, l, mid, p, nd.mp[a].first, s);
		nd.debt+=lv;
		int rv=query(2*n+1, mid+1, r, p, nd.mp[a].second, s-lv);
		nd.debt+=rv;
		return lv+rv;
	}
	int can=max(0, a-nd.debt);
	if(!can) return 0;
	if(l==r) {
		can=min(can, s);
		nd.debt+=can;
		return can;
	}
	if(can<=s) {
		nd.debt+=can;
		nd.lazy=1;
		return can;
	}
	int lv=query(2*n, l, mid, p, nd.mp[a].first, s);
	nd.debt+=lv;
	int rv=query(2*n+1, mid+1, r, p, nd.mp[a].second, s-lv);
	nd.debt+=rv;
	return lv+rv;
}

void init(int N, int A[], int B[]) {
	for(int i=0;i<N;i++) {
		byb[B[i]].push_back(A[i]);
	}
	build(1, 1, N);
	gn=N;
}

int can(int M, int K[]) {
	sort(K, K+M);
	int ans=1;
	for(int i=0;i<M;i++) {
		int r=query(1, 1, gn, K[i], (int)(upper_bound(nodes[1].vals.begin(), nodes[1].vals.end(), K[i])-nodes[1].vals.begin()), K[i]);
		if(r<K[i]) {
			ans=0;
			break;
		}
	}
	nodes[1].debt=0;
	nodes[1].lazy=1;
	return ans;
}

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