답안 #711504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711504 2023-03-17T06:31:36 Z Cyanmond Bubble Sort 2 (JOI18_bubblesort2) C++17
컴파일 오류
0 ms 0 KB
#include "bubblesort2.h"
#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
    const int N = (int)A.size(), Q = (int)X.size();
    {
        std::vector<int> vals;
        std::copy(A.begin(), A.end(), std::back_inserter(vals));
        std::copy(V.begin(), V.end(), std::back_inserter(vals));
        std::sort(vals.begin(), vals.end());
        for (auto &e : A) e = (int)(std::lower_bound(vals.begin(), vals.end(), e) - vals.begin());
        for (auto &e : V) e = (int)(std::lower_bound(vals.begin(), vals.end(), e) - vals.begin());
    }
    // subtask 1, 2
    const int M =
        std::max(*std::max_element(A.begin(), A.end()), *std::max_element(V.begin(), V.end())) + 1;
    std::vector<int> countL(N);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (A[i] > A[j]) {
                ++countL[j];
            }
        }
    }

    std::vector<int> answer(Q);
    for (int q = 0; q < Q; ++q) {
        const int x = X[q], newVal = V[q];
        const int preVal = A[x];
        for (int i = x + 1; i < N; ++i) {
            if (preVal > A[i]) {
                --countL[i];
            }
        }
        A[x] = newVal;
        for (int i = x + 1; i < N; ++i) {
            if (newVal > A[i]) {
                ++countL[i];
            }
        }
        countL[x] = 0;
        for (int i = 0; i < x; ++i) {
            if (A[i] > newVal) {
                ++countL[x];
            }
        }
        answer[q] = *std::max_element(countL.begin(), countL.end());
    }
    return answer;
}

#include "bubblesort2.h"

#include <cstdio>
#include <cstdlib>
#include <vector>

int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();
	
	std::vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
	
	std::vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
	
	std::vector<int> res=countScans(A,X,V);
	
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:17:15: warning: unused variable 'M' [-Wunused-variable]
   17 |     const int M =
      |               ^
/usr/bin/ld: /tmp/cc8zLul0.o: in function `readInt()':
grader.cpp:(.text+0x0): multiple definition of `readInt()'; /tmp/ccp0sHJ0.o:bubblesort2.cpp:(.text+0x3d0): first defined here
/usr/bin/ld: /tmp/cc8zLul0.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccp0sHJ0.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status