제출 #1276379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276379		LucaLucaM	Land of the Rainbow Gold (APIO17_rainbow)	C++20	50 / 100	785 ms	51320 KiB

rainbow

#include "rainbow.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

const int MAXN = 1000 + 7;
using ll = long long;

struct Fenwick2D { // ah wait defapt pot face doar niste cautari binare
  std::set<std::pair<int, int>> cells;

  std::vector<int> ys[MAXN + 1];
  
  void add(int x, int y) {
    if (cells.count({x, y})) { // sa am grija sa nu inserez aceeasi pozitie de mai multe ori
      return;
    }
    cells.insert({x, y});
    x++;
    for (int i = x; i <= MAXN; i += i & -i) {
      ys[i].push_back(y);
    }
  }
  void build() {
    for (int i = 1; i <= MAXN; i++) {
      ys[i].push_back(0);
      ys[i].push_back(MAXN + 7);
      std::sort(ys[i].begin(), ys[i].end());
    }
  }
  int query(int x, int y) {
    x++;
    int ret = 0;
    for (int i = x; i > 0; i -= i & -i) {
      ret += std::upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();
    }
    return ret;
  }
  int query(int x1, int y1, int x2, int y2) {
    return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
  }
};

namespace {
  int minX, maxX, minY, maxY;
  Fenwick2D vert, horizontalEdges, verticalEdges, boxes; 
};

void init(int R, int C, int sr, int sc, int M, char *S) {
  int x = sr, y = sc;
  minX = R + 1;
  minY = C + 1;
  maxX = 0;
  maxY = 0;

  auto add = [&](int x, int y) {
    minX = std::min(minX, x);
    maxX = std::max(maxX, x);
    minY = std::min(minY, y);
    maxY = std::max(maxY, y);
    vert.add(x, y);
    horizontalEdges.add(x, y);
    horizontalEdges.add(x, y - 1);
    verticalEdges.add(x, y);
    verticalEdges.add(x - 1, y);
    boxes.add(x, y);
    boxes.add(x, y - 1);
    boxes.add(x - 1, y);
    boxes.add(x - 1, y - 1);
  };

  add(x, y);
  for (int i = 0; i < M; i++) {
    if (S[i] == 'N') {
      x--;
    } else if (S[i] == 'S') {
      x++;
    } else if (S[i] == 'W') {
      y--;
    } else {
      y++;
    }
    add(x, y);
  }

  vert.build();
  horizontalEdges.build();
  verticalEdges.build();
  boxes.build();
}

int colour(int x1, int y1, int x2, int y2) {
  ll V = (ll) (x2 - x1 + 1) * (y2 - y1 + 1) - vert.query(x1, y1, x2, y2);
  ll E = 0;
  E += (ll) (x2 - x1 + 1) * (y2 - y1) - horizontalEdges.query(x1, y1, x2, y2 - 1);
  E += (ll) (x2 - x1) * (y2 - y1 + 1) - verticalEdges.query(x1, y1, x2 - 1, y2);
  ll F = (ll) (x2 - x1) * (y2 - y1) - boxes.query(x1, y1, x2 - 1, y2 - 1);
  F++;
  if (x1 < minX && maxX < x2 && y1 < minY && maxY < y2) {
    F++;
  }
  // V + F = E + C + 1 (cred)
  return V + F - E - 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 27 / 27
• Subtask 5: 0 / 26