제출 #1032858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032858		socpite	팀들 (IOI15_teams)	C++17	0 / 100	1115 ms	111284 KiB

teams

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

const int maxn = 5e5+5;
const long long INF = 1e18;

vector<int> FW[maxn];
vector<int> d[maxn];

int pfx_all[maxn], sfx_all[maxn];

int n;

void add(int x, int y){
	for(x; x <= n; x += x&(-x)){
		for(int idx = lower_bound(d[x].begin(), d[x].end(), y) - d[x].begin(); idx < d[x].size(); idx += idx&(-idx))FW[x][idx]++;
	}
}

int gt(int x, int y){
	int re = 0;
	for(x; x > 0; x -= x&(-x)){
		for(int idx = upper_bound(d[x].begin(), d[x].end(), y) - d[x].begin() - 1; idx > 0; idx -= idx&(-idx))re += FW[x][idx];
	}
	return re;
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++){
		for(int x = B[i]; x <= n; x += x&(-x))d[x].push_back(A[i]);
		pfx_all[B[i]]++;
		sfx_all[A[i]]++;
	}
	for(int i = 1; i <= n; i++){
		pfx_all[i] += pfx_all[i-1];
		d[i].push_back(-1);
		sort(d[i].begin(), d[i].end());
		d[i].erase(unique(d[i].begin(), d[i].end()), d[i].end());
		FW[i].assign(d[i].size(), 0);
	}
	for(int i = n; i >= 1; i--)sfx_all[i] += sfx_all[i+1];
	for(int i = 0; i < n; i++)add(B[i], A[i]);
}

int can(int M, int K[]) {
	long long pfx_M = 0, pfx_gap = 0, mn = INF;
	sort(K, K+M);
	// sum_segment - sum_M < 0 => bad
	// sum_segment = pfx_all - sumgap
	for(int i = 0; i < M; i++){
		mn = min(mn, pfx_M + pfx_gap - pfx_all[K[i]-1]);
		pfx_M += K[i];
		// cout << pfx_M << " " << pfx_gap << " " << pfx_all[K[i]] << " " << mn << endl;
		if(mn - pfx_M - pfx_gap + n - sfx_all[K[i]+1] < 0)return 0;
		if(i + 1 < M)pfx_gap += pfx_all[K[i+1] - 1] - gt(K[i+1]-1, K[i]);
	}
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void add(int, int)':
teams.cpp:16:6: warning: statement has no effect [-Wunused-value]
   16 |  for(x; x <= n; x += x&(-x)){
      |      ^
teams.cpp:17:58: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   17 |   for(int idx = lower_bound(d[x].begin(), d[x].end(), y) - d[x].begin(); idx < d[x].size(); idx += idx&(-idx))FW[x][idx]++;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:17:78: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int idx = lower_bound(d[x].begin(), d[x].end(), y) - d[x].begin(); idx < d[x].size(); idx += idx&(-idx))FW[x][idx]++;
      |                                                                          ~~~~^~~~~~~~~~~~~
teams.cpp: In function 'int gt(int, int)':
teams.cpp:23:6: warning: statement has no effect [-Wunused-value]
   23 |  for(x; x > 0; x -= x&(-x)){
      |      ^
teams.cpp:24:73: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   24 |   for(int idx = upper_bound(d[x].begin(), d[x].end(), y) - d[x].begin() - 1; idx > 0; idx -= idx&(-idx))re += FW[x][idx];
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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