제출 #348854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348854		dennisstar	Teams (IOI15_teams)	C++17	100 / 100	3930 ms	106448 KiB

teams

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

using namespace std;

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, lst;
	int l, r;
}nd[1<<20];
int nc;
int newnode() {
	++nc;
	nd[nc]={0, 0, 0, 0};
	return nc;
}

int use(int n, int i, int s, int e, int w, int v) {
	nd[n].used=max(nd[n].used, (int)(upper_bound(st[i].begin(), st[i].end(), nd[n].lst)-st[i].begin()));
	if (!v) return 0;
	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;
		nd[n].lst=w;
		return r;
	}
	if (s==e) {
		nd[n].used+=v;
		return v;
	}
	int m=(s+e)/2;
	if (!nd[n].l) {
		nd[n].l=newnode();
		nd[n].r=newnode();
	}
	nd[nd[n].l].lst=max(nd[nd[n].l].lst, nd[n].lst);
	nd[nd[n].r].lst=max(nd[nd[n].r].lst, nd[n].lst);
	int x=use(nd[n].l, i*2, s, m, w, v);
	int y=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) {
	nd[n].used=max(nd[n].used, (int)(upper_bound(st[i].begin(), st[i].end(), nd[n].lst)-st[i].begin()));
	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();
	}
	nd[nd[n].l].lst=max(nd[nd[n].l].lst, nd[n].lst);
	nd[nd[n].r].lst=max(nd[nd[n].r].lst, nd[n].lst);
	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;
}

컴파일 시 표준 에러 (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:66:35: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   66 |  if (e<=t) { nd[n].used=st[i].size(); return ; }
      |                         ~~~~~~~~~~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:81:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   81 | void init(int N, int A[], int B[]) {
      |                                  ^
teams.cpp:79:5: note: shadowed declaration is here
   79 | int N, Q;
      |     ^

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