Submission #897707

#	Time	Username	Problem	Language	Result	Execution time	Memory
897707		lovrot	Construction of Highway (JOI18_construction)	C++17	16 / 100	278 ms	856 KiB

construction

#include <cstdio> 
#include <vector> 
#include <algorithm> 

#define EB emplace_back

using namespace std;

typedef long long ll; 

const int LOG = 12;
const int N = 1 << LOG; 

int n, C[N]; 

int F[N]; 

void add(int x, int val) {
	for(++x; x < N; x += x & -x) F[x] += val;
}

int sum(int x) {
	int sum = 0;
	for(++x; x; x -= x & -x) sum += F[x]; 
	return sum;
}

int P[N];
vector<int> S; 

int main() {
	scanf("%d", &n); 
	for(int i = 1; i <= n; ++i) {
		scanf("%d", C + i); 
		S.EB(C[i]); 
	}

	sort(S.begin(), S.end()); 
	S.erase(unique(S.begin(), S.end()), S.end()); 

	for(int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b); 

		ll cost = 0;
		for(int _a = a; _a; _a = P[_a]) {
			int pos = lower_bound(S.begin(), S.end(), C[_a]) - S.begin() + 1;
			cost += (ll) sum(pos - 1); 
			add(pos, 1); 
		}
		
		printf("%lld\n", cost); 

		for(int _a = a; _a; _a = P[_a]) {
			int pos = lower_bound(S.begin(), S.end(), C[_a]) - S.begin() + 1;
			add(pos, -1);
			C[_a] = C[b];
		}

		P[b] = a;
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
construction.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", C + i);
      |   ~~~~~^~~~~~~~~~~~~
construction.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84