Submission #274846

#	Time	Username	Problem	Language	Result	Execution time	Memory
274846		Haunted_Cpp	Seats (IOI18_seats)	C++17	17 / 100	4100 ms	59512 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
int r, c;
vector<pair<int, int>> where;

vector<int> d;
vector<int> mn_column;
vector<int> mn_row;
vector<int> mx_column;
vector<int> mx_row;

int global_score = 0;

const int INF = 1e9;

void solve(int lo, int hi) {
  for (int i = lo; i <= hi; i++) {
    mn_column[i] = min(i - 1 >= 0 ? mn_column[i - 1] : INF, where[i].second);
    mx_column[i] = max(i - 1 >= 0 ? mx_column[i - 1] : -INF, where[i].second);
    mn_row[i] = min(i - 1 >= 0 ? mn_row[i - 1] : INF, where[i].first);
    mx_row[i] = max(i - 1 >= 0 ? mx_row[i - 1] : -INF, where[i].first);
    global_score -= d[i];
    d[i] = (((mx_row[i] - mn_row[i] + 1) * (mx_column[i] - mn_column[i] + 1)) == (i + 1));
    global_score += d[i];
  }
}
 
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  r = H;
  c = W;
  where.resize(r * c);
  d.resize(r * c);
  mn_column = mn_row = vector<int>(r * c, 1e9);
  mx_column = mx_row = vector<int>(r * c, -1e9);
  
  for (int i = 0; i < r * c; i++) {
    where[i] = {R[i], C[i]};
  }
  solve(0, r * c - 1);
}
 

int swap_seats(int a, int b) {
  swap(where[a], where[b]);
  solve(min(a, b), max(a, b));
  return global_score;
}

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