| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1230755 | phoenix_ | 새로운 문제 (POI11_met) | Java | 0 ms | 0 KiB |
//package algorithmist.poi.meteors.parallelbinarysearch;
import java.io.*;
import java.util.*;
class StandardIO {
BufferedReader br;
StringTokenizer st;
PrintWriter pw;
StandardIO() {
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}
StandardIO(String inputFile, String outputFile) throws IOException {
br = new BufferedReader(new FileReader(inputFile));
pw = new PrintWriter(new BufferedWriter(outputFile)));
}
String readString() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
String readLine() {
String s = "";
try {
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return s;
}
int readInt() {
return Integer.parseInt(readString());
}
long readLong() {
return Long.parseLong(readString());
}
double readDouble() {
return Double.parseDouble(readString());
}
public char readChar() {
return readString().charAt(0);
}
public boolean readBoolean() {
return Boolean.parseBoolean(readString());
}
public void print(Object obj) {
pw.print(obj);
}
public void println(Object obj) {
pw.println(obj);
}
public void println() {
pw.println();
}
public void printf(String format, Object... args) {
pw.printf(format, args);
}
public void flush() {
pw.flush();
}
public void close() {
try {
br.close();
pw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public boolean hasNext() {
while (st == null || !st.hasMoreTokens()) {
try {
String line = br.readLine();
if (line == null) return false;
st = new StringTokenizer(line);
} catch (IOException e) {
return false;
}
}
return true;
}
}
class FenwickTree {
int N;
long[] tree;
FenwickTree(int N) {
this.N = N;
tree = new long[N + 1];
}
void update(int idx, long v) {
for (int x = idx + 1; x <= N; x += x & -x) {
tree[x] += v;
}
}
void rangeUpdate(int low, int high, long val) {
update(low, val);
update(high + 1, -val);
}
long query(int idx) {
long sum = 0;
for (int x = idx + 1; x > 0; x -= x & -x) {
sum += tree[x];
}
return sum;
}
long query(int low, int high) {
return query(high) - query(low - 1);
}
}
class Task {
int N, M, Q;
int[] required;
int[] propertiesStart;
int[] propertiesData;
int[] queryLow;
int[] queryHigh;
int[] queryA;
int[] candidatesNext;
int[] candidatesData;
int[] candidatesHead;
int candidatesCount;
int[] L;
int[] R;
int[] answer;
StandardIO f = new StandardIO();
void readInput() {
N = f.readInt();
M = f.readInt();
// Count total properties
int totalProperties = 0;
int[] tempOwners = new int[M];
for (int i = 0; i < M; ++i) {
tempOwners[i] = f.readInt() - 1;
totalProperties++;
}
// Build compressed representation
propertiesStart = new int[N + 1];
propertiesData = new int[totalProperties];
// Count properties per owner
for (int i = 0; i < M; ++i) {
propertiesStart[tempOwners[i] + 1]++;
}
// Convert to prefix sum
for (int i = 1; i <= N; ++i) {
propertiesStart[i] += propertiesStart[i - 1];
}
// Fill properties data
int[] currentPos = Arrays.copyOf(propertiesStart, N);
for (int i = 0; i < M; ++i) {
int owner = tempOwners[i];
propertiesData[currentPos[owner]++] = i;
}
required = new int[N];
for (int i = 0; i < N; ++i) {
required[i] = f.readInt();
}
Q = f.readInt();
queryLow = new int[Q];
queryHigh = new int[Q];
queryA = new int[Q];
for (int i = 0; i < Q; ++i) {
queryLow[i] = f.readInt() - 1;
queryHigh[i] = f.readInt() - 1;
queryA[i] = f.readInt();
}
}
void solve() {
L = new int[N];
R = new int[N];
answer = new int[N];
Arrays.fill(R, Q - 1);
Arrays.fill(answer, -1);
// Initialize linked list structure for candidates
candidatesNext = new int[N];
candidatesData = new int[N];
candidatesHead = new int[Q + 1];
boolean search = true;
while (search) {
search = false;
Arrays.fill(candidatesHead, -1);
candidatesCount = 0;
FenwickTree tree = new FenwickTree(M);
// Build candidates list
for (int i = 0; i < N; ++i) {
if (L[i] <= R[i]) {
search = true;
int mid = (L[i] + R[i]) / 2;
// Add to linked list for query 'mid'
candidatesData[candidatesCount] = i;
candidatesNext[candidatesCount] = candidatesHead[mid];
candidatesHead[mid] = candidatesCount;
candidatesCount++;
}
}
for (int i = 0; i < Q; ++i) {
int low = queryLow[i];
int high = queryHigh[i];
int a = queryA[i];
if (low > high) {
tree.rangeUpdate(low, M - 1, a);
tree.rangeUpdate(0, high, a);
} else {
tree.rangeUpdate(low, high, a);
}
// Process candidates for this query
int current = candidatesHead[i];
while (current != -1) {
int idx = candidatesData[current];
long sum = 0;
for (int j = propertiesStart[idx]; j < propertiesStart[idx + 1]; ++j) {
sum += tree.query(propertiesData[j]);
if (sum >= required[idx]) {
break;
}
}
if (sum >= required[idx]) {
answer[idx] = i;
R[idx] = i - 1;
} else {
L[idx] = i + 1;
}
current = candidatesNext[current];
}
}
}
for (int i = 0; i < N; ++i) {
if (answer[i] == -1) {
f.println("NIE");
} else {
f.println(answer[i] + 1);
}
}
f.close();
}
void perform() {
readInput();
solve();
}
}
public class met {
public static void main(String[] args) {
Task task = new Task();
task.perform();
}
}