제출 #228633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228633		mieszko11b	팀들 (IOI15_teams)	C++14	0 / 100	4089 ms	397396 KiB

teams

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

using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define X first
#define Y second

struct SegmentTree {
	int lv;
	int n;
	vector<int> x[1100007], gel[1100007], lel[1100007], ger[1100007], ler[1100007];
	int y[600007];
	
	SegmentTree(int n, int A[], int B[]) {
		lv = 2;
		this->n = n;
		while(lv < n + 2)
			lv *= 2;
			
		vector<ii> V(n);
		for(int i = 0 ; i < n ; i++)
			V[i] = {B[i], A[i]};
		sort(V.begin(), V.end());
		
		for(int i = 0 ; i < n ; i++) {
			y[i] = V[i].X;
			x[lv + i].push_back(V[i].Y);
		}
		
		for(int i = lv - 1 ; i >= 1 ; i--) {
			int l = 2 * i;
			int r = 2 * i + 1;
			
			x[i].resize(x[l].size() + x[r].size());
			merge(x[l].begin(), x[l].end(), x[r].begin(), x[r].end(), x[i].begin());
			
			int ind;
			
			ind = 0;
			gel[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind < x[l].size() && x[l][ind] < x[i][j])
					ind++;
				gel[i][j] = ind;
			}
			
			ind = 0;
			ger[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind < x[r].size() && x[r][ind] < x[i][j])
					ind++;
				ger[i][j] = ind;
			}
			
			ind = -1;
			lel[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind + 1 < x[l].size() && x[l][ind + 1] <= x[i][j])
					ind++;
				lel[i][j] = ind;
			}
			
			ind = -1;
			ler[i].resize(x[i].size());
			for(int j = 0 ; j < x[i].size() ; j++) {
				while(ind + 1 < x[r].size() && x[r][ind + 1] <= x[i][j])
					ind++;
				ler[i][j] = ind;
			}		
		}
	}
	
	int query(int a, int b, int l, int r, int w, int i1, int i2) {
		if(b < l || a > r || l > r || i1 > i2)
			return 0;
		if(a <= l && r <= b)
			return i2 - i1 + 1;
		return query(a, b, l, (l + r) / 2, 2 * w, gel[w][i1], lel[w][i2])
			 + query(a, b, (l + r) / 2 + 1, r, 2 * w + 1, ger[w][i1], gel[w][i2]);
	}
	
	int count(int x1, int x2, int y1, int y2) {
		int a = lower_bound(y, y + n, y1) - y;
		int b = upper_bound(y, y + n, y2) - y - 1;
		if(a > b)
			return 0;
		int l = 0;
		int r = lv - 1;
		int w = 1;
		int i1 = lower_bound(x[w].begin(), x[w].end(), x1) - x[w].begin();
		int i2 = upper_bound(x[w].begin(), x[w].end(), x2) - x[w].begin() - 1;
		return query(a, b, l, r, w, i1, i2);
	}
};

SegmentTree *ST;

void init(int N, int A[], int B[]) {
	ST = new SegmentTree(N, A, B);
}

ll dp[200007];

int can(int M, int K[]) {
	sort(K, K + M);
	set<int> cand;
	dp[0] = 0;
	cand.insert(0);
	vector<ii> V;
	V.emplace_back(0, 0);
	for(int i = 0 ; i < M ; i++) {
		int k = K[i];
		if(V.empty() || V.back().Y != k)
			V.emplace_back(k, 1);
		else
			V.back().Y++;
	}
	
	ll res = 1e18;
	for(int i = 1 ; i < V.size() ; i++) {
		dp[i] = 1e18;
		for(int j = 0 ; j < i ; j++) {
			dp[i] = min(dp[i], dp[j] + ST->count(V[j].X + 1, V[i].X, V[i].X, 1e9) - (ll)V[i].X * V[i].Y);
		}
		res = min(res, dp[i]);
	}
	
	return res >= 0;
}

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

teams.cpp: In constructor 'SegmentTree::SegmentTree(int, int*, int*)':
teams.cpp:18:39: warning: declaration of 'n' shadows a member of 'SegmentTree' [-Wshadow]
  SegmentTree(int n, int A[], int B[]) {
                                       ^
teams.cpp:14:6: note: shadowed declaration is here
  int n;
      ^
teams.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind < x[l].size() && x[l][ind] < x[i][j])
           ~~~~^~~~~~~~~~~~~
teams.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind < x[r].size() && x[r][ind] < x[i][j])
           ~~~~^~~~~~~~~~~~~
teams.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind + 1 < x[l].size() && x[l][ind + 1] <= x[i][j])
           ~~~~~~~~^~~~~~~~~~~~~
teams.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < x[i].size() ; j++) {
                    ~~^~~~~~~~~~~~~
teams.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ind + 1 < x[r].size() && x[r][ind + 1] <= x[i][j])
           ~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In member function 'int SegmentTree::count(int, int, int, int)':
teams.cpp:87:37: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int a = lower_bound(y, y + n, y1) - y;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:88:41: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int b = upper_bound(y, y + n, y2) - y - 1;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:94:54: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int i1 = lower_bound(x[w].begin(), x[w].end(), x1) - x[w].begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:95:69: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int i2 = upper_bound(x[w].begin(), x[w].end(), x2) - x[w].begin() - 1;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < V.size() ; i++) {
                  ~~^~~~~~~~~~

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