a574. ITSA2012 桂冠 n維區間查詢 - 高中生程式解題系統

內容

n維區間查詢

Background

由於在賽後無法得到題目描述與測資，小光盡可能地將原本題目描述清楚。

The Problem

什麼是 n 維區間查詢呢？

對於一個資料庫有很多筆 n 維的資料，一筆資料的維度 d，
可以表示成 A[d]，若對於一個 query(L, U) 符合的集合 S

S = {A | L[i] <= A[i] <= U[i], 0<= i < d, A∈Database}

對於每一筆資料求 S 集合的大小。

輸入說明

只會有一組測資。

接下來有 N 個 d 維的資料，每個元素以 ',' 逗號隔開。

結束於一行 "-1" 表示。

接著有 Q 個詢問，每組詢問 L, U，以 "-1" 一行為間隔。

數據範圍

N <= 200000, Q < 1000, d = 10

所有資料元素(包含 L, U) E (0 <= E <= 100)

輸出說明

對於每組查詢輸出 S 的大小。

範例輸入 #1

98,22,82,100,34,58,57,77,55,97
56,52,58,84,54,14,83,87,67,12
27,81,57,2,27,73,20,53,8,78
89,44,3,87,3,64,85,37,9,73
45,88,49,19,73,100,16,72,29,88
94,84,28,94,12,25,37,15,40,92
11,59,92,89,2,87,24,60,39,82
34,46,53,35,2,41,77,92,27,82
60,49,20,75,6,57,0,22,28,54
59,41,78,32,64,37,62,100,47,81
-1
0,11,11,25,0,20,0,11,26,3
84,57,98,71,64,82,78,100,90,86
-1
0,0,0,0,0,0,0,0,0,0
100,100,100,100,100,100,100,100,100,100
-1

範例輸出 #1

2
10

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (50%): 1.0s , <10M
公開測資點#1 (30%): 2.0s , <10M
公開測資點#2 (20%): 2.0s , <10M

提示：

標籤:

出處:

ITSA 2012 [管理者： morris821028@gmail.com

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」