Submission #580534

#	Time	Username	Problem	Language	Result	Execution time	Memory
580534		Vanilla	Seats (IOI18_seats)	C++17	5 / 100	4054 ms	39728 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
typedef long long int64;
using namespace std;
vector<int> r,c;
const int maxn = 1e4 + 2;
int n = 0, m = 0;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  for (int i = 0; i < H * W; i++){
    R[i]++;
    C[i]++;
  }
  r = R, c = C, n = H, m = W;

}

int swap_seats(int a, int b) {
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  int64 dp[n + 2][m + 2] = {};
  for (int i = 0; i < n * m; i++){
    dp[r[i]][c[i]] = i;
  }
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m; j++){
      dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
    }
  }
  int rs = 0;
  for (int i1 = 1; i1 <= n; i1++){
    for (int j1 = 1; j1 <= m; j1++){
      for (int i2 = i1; i2 <= n; i2++){
        for (int j2 = j1; j2 <= m; j2++){
          int64 area = (j2 - j1 + 1) * (i2 - i1 + 1);
          if (area == 0) continue;
          int64 sum = area * (area - 1) / 2;
          // cout << i1 << " " << j1 << " " << i2 << " " << j2 << " " << area << " " << dp[i2][j2] - dp[i2][j1 - 1] - dp[i1 - 1][j2] + dp[i1 - 1][j1 - 1] << " " << sum << "\n";
          if (dp[i2][j2] - dp[i2][j1 - 1] - dp[i1 - 1][j2] + dp[i1 - 1][j1 - 1] == sum) rs++;
        }
      }
    }
  }
  return rs;
}

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