Submission #348851

#	Time	Username	Problem	Language	Result	Execution time	Memory
348851		dennisstar	Teams (IOI15_teams)	C++17	0 / 100	1370 ms	185072 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define eb emplace_back

using namespace std;

const int MX = 5e5 + 5;

vector<int> st[1<<20];

void upd(int i, int s, int e, int t, int v) {
	st[i].eb(v);
	if (s==e) return ;
	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, v);
	else upd(i*2+1, m+1, e, t, v);
}

void _init(int i, int s, int e) {
	sort(st[i].begin(), st[i].end());
	if (s==e) return ;
	int m=(s+e)/2;
	_init(i*2, s, m);
	_init(i*2+1, m+1, e);
}

struct {
	int used;
	int l, r;
}nd[1<<20];
int nc;
int newnode() {
	++nc;
	nd[nc]={0, 0, 0};
	return nc;
}

int use(int n, int i, int s, int e, int w, int v) {
	int t=upper_bound(st[i].begin(), st[i].end(), w)-st[i].begin();
	if (t-nd[n].used<=v) {
		int r=t-nd[n].used;
		nd[n].used=t;
		return r;
	}
	if (s==e) {
		nd[n].used+=v;
		return v;
	}
	int m=(s+e)/2;
	if (!nd[n].l) {
		assert(nd[n].used==0);
		nd[n].l=newnode();
		nd[n].r=newnode();
	}
	int x=use(nd[n].l, i*2, s, m, w, v);
	int y=(x==v?0:use(nd[n].r, i*2+1, m+1, e, w, v-x));
	nd[n].used=nd[nd[n].l].used+nd[nd[n].r].used;
	return x+y;
}

void kill(int n, int i, int s, int e, int t) {
	if (t<s) return ;
	if (e<=t) { nd[n].used=st[i].size(); return ; }
	int m=(s+e)/2;
	if (!nd[n].l) {
		nd[n].l=newnode();
		nd[n].r=newnode();
	}
	kill(nd[n].l, i*2, s, m, t);
	kill(nd[n].r, i*2+1, m+1, e, t);
	nd[n].used=nd[nd[n].l].used+nd[nd[n].r].used;
}

int N, Q;

void init(int N, int A[], int B[]) {
	::N=N;
	for (int i=0; i<N; i++) upd(1, 1, N, B[i], A[i]);
	_init(1, 1, N);
}

int can(int M, int K[]) {
	nc=0;
	sort(K, K+M);
	int rt=newnode();
	for (int i=0; i<M; i++) {
		kill(rt, 1, 1, N, K[i]-1);
		if (use(rt, 1, 1, N, K[i], K[i])<K[i]) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int use(int, int, int, int, int, int)':
teams.cpp:39:50: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   39 |  int t=upper_bound(st[i].begin(), st[i].end(), w)-st[i].begin();
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp: In function 'void kill(int, int, int, int, int)':
teams.cpp:63:35: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |  if (e<=t) { nd[n].used=st[i].size(); return ; }
      |                         ~~~~~~~~~~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:76:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   76 | void init(int N, int A[], int B[]) {
      |                                  ^
teams.cpp:74:5: note: shadowed declaration is here
   74 | int N, Q;
      |     ^

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