Submission #134334

#	Time	Username	Problem	Language	Result	Execution time	Memory
134334		MoNsTeR_CuBe	Seats (IOI18_seats)	C++17	11 / 100	4066 ms	27896 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) { 
	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]);
	
	int dp[h+1][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;
	
	int obj = 0;
	
	for(int i = 0; i < h*w; i++){
		if(xMin > indices[i].second) xMin = indices[i].second;
		if(xMax < indices[i].second) xMax = indices[i].second;
		
		if(yMin > indices[i].first) yMin = indices[i].first;
		if(yMax < indices[i].first) yMax = indices[i].first;
	
		obj+=i;
		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: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30