Submission #134317

#	Time	Username	Problem	Language	Result	Execution time	Memory
134317		MoNsTeR_CuBe	Seats (IOI18_seats)	C++17	0 / 100	875 ms	175160 KiB

seats

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

#define int long long

vector<int> r;

map< int, 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){
	int tot = 0;
	for(int i = b; i >= a; 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));
	
	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 
	add(fenwick[indices[a].first], b-a, indices[b].second);
	add(fenwick[indices[b].first], a-b, indices[a].second);
	
	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 n = (xMax - xMin) * (yMax - yMin);
	
		int obj = (n)*(n-1)/2;
		int tot = 0;
		
		for(int j = yMin; j <= yMax; j++){
			tot += query(fenwick[j], xMin, xMax);
		}
		
		if(tot == obj) ans++;
	}
	
	return ans;
}

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