Submission #134333

#	Time	Username	Problem	Language	Result	Execution time	Memory
134333		MoNsTeR_CuBe	Seats (IOI18_seats)	C++17	5 / 100	4005 ms	32260 KiB

seats

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

vector< pair<int, int> > indices;
vector< vector< int > > grid;
int h, w;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { 
	assert(H*W <= 10000);
	grid.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);
		grid[R[i]+1][C[i]+1] = i;
	}
}

int swap_seats(int a, int b) {
	swap(indices[a], indices[b]);
	swap(grid[indices[a].first][indices[a].second], grid[indices[b].first][indices[b].second]);
	
	vector< vector< int > > dp(h+1, vector< int > (w+1));
	
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + grid[i][j];
		}
	}
	
	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 = dp[yMax][xMax] + dp[yMin-1][xMin-1] - dp[yMax][xMin-1] - dp[yMin-1][xMax];
		if(tot == obj) ans++;
	}
	
	return ans;
}

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