제출 #134323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134323		MoNsTeR_CuBe	자리 배치 (IOI18_seats)	C++17	5 / 100	4051 ms	39560 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
vector< pair<int, int> > indices;

vector< vector< int > > fenwick;

int h, w;

void add(vector< int > &v, int a, int index){
	for(int i = index; i <= w; i+=i&-i){
		v[i] += a;
	}
}

int query(vector< int> &v, int a, int b){
	//cout << v.size() << endl;
	int tot = 0;
	for(int i = b; i >= 1; i-=i&-i){
		tot += v[i];
	}
	for(int i = a-1; i >= 1; i-=i&-i){
		tot -= v[i];
	}
	return tot;
}

#undef int

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	#define int long long 
	fenwick.resize(H+1, vector< int > (W+1));
	indices.resize(H*W);
	
	h = H;
	w = W;
	
	for(int i = 0; i < H*W; i++){
		indices[i] = make_pair(R[i]+1, C[i]+1);
		add(fenwick[R[i]+1], i, C[i]+1);
	}
	#undef int
}

int swap_seats(int a, int b) {
	#define int long long 
	//cout << fenwick[indices[a].first].size() << endl;
	add(fenwick[indices[a].first], b-a, indices[a].second);
	add(fenwick[indices[b].first], a-b, indices[b].second);
	
	swap(indices[a], indices[b]);
	
	int xMin = INT_MAX, yMin = INT_MAX, xMax = INT_MIN, yMax = INT_MIN;
	
	int ans = 0;
	
	for(int i = 0; i < h*w; i++){
		xMin = min(xMin, (indices[i].second));
		yMin = min(yMin, indices[i].first);
		xMax = max(xMax, indices[i].second);
		yMax = max(yMax, indices[i].first);
	
		int obj = i * (i+1) /2;
		int tot = 0;
		
		for(int j = yMin; j <= yMax; j++){
			tot += query(fenwick[j], xMin, xMax);
		}
		
		if(tot == obj) ans++;
	}
	
	return ans;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30