Submission #1065162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065162		abczz	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	766 ms	267200 KiB

rainbow

#include "rainbow.h"
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long
 
using namespace std;
 
vector <array<ll, 2>> V;
map <array<ll, 2>, ll> mp, vert, edger, edgec;
string T = "NESW";
vector <ll> X[200001], VR[200001], ER[200001], EC[200001], G[200001];
ll mnx = 1e18, mny = 1e18, mxx = -1e18, mxy = -1e18;
ll x, y, r, c, nx, ny, tot, e, v, f, dj[4][2] = {0, 0, 0, 1, 1, 0, 1, 1}, dr[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
 
struct SegTree2D{
  vector <ll> st[800004];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = X[l];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < st[id*2].size() && j < st[id*2+1].size()) {
      if (st[id*2][i] <= st[id*2+1][j]) st[id].push_back(st[id*2][i++]);
      else st[id].push_back(st[id*2+1][j++]);
    }
    while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
    while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
  }
  ll query(ll id, ll l, ll r, ll xl, ll xr, ll yl, ll yr) {
    if (xr < l || r < xl || xl > xr || yl > yr) return 0;
    else if (xl <= l && r <= xr) {
      auto it = lower_bound(st[id].begin(), st[id].end(), yl);
      auto it2 = lower_bound(st[id].begin(), st[id].end(), yr+1);
      return (it2-st[id].begin())-(it-st[id].begin());
    }
    ll mid = (l+r)/2;
    return query(id*2, l, mid, xl, xr, yl, yr) + query(id*2+1, mid+1, r, xl, xr, yl, yr);
  }
}STV, STER, STEC, ST;

void init(int R, int C, int sr, int sc, int M, char *S) {
  r = R, c = C;
  mp.clear();
  V.clear();
  V.push_back({sr, sc});
  x = sr, y = sc;
  for (int j=0; j<M; ++j) {
    auto u = S[j];
    for (int i=0; i<4; ++i) {
      if (u == T[i]) {
        nx = x + dr[i][0], ny = y + dr[i][1];
        x = nx, y = ny;
        V.push_back({x, y});
        break;
      }
    }
  }
  for (int i=0; i<V.size(); ++i) {
    --V[i][0], --V[i][1];
    mnx = min(mnx, V[i][0]);
    mxx = max(mxx, V[i][0]);
    mny = min(mny, V[i][1]);
    mxy = max(mxy, V[i][1]);
    x = V[i][0], y = V[i][1];
    if (!mp.count({x, y})) ++mp[{x, y}];
    for (int j=0; j<4; ++j) {
      nx = x + dj[j][0], ny = y + dj[j][1];
      ++vert[{nx, ny}];
    }
    ++edger[{x, y}];
    ++edger[{x+1, y}];
    ++edgec[{x, y}];
    ++edgec[{x, y+1}];
  }
  for (auto it = edger.begin(); it != edger.end();) {
    auto nx = next(it);
    auto [x, y] = it->first;
    ER[x].push_back(y);
    it = nx;
  }
  for (auto it = edgec.begin(); it != edgec.end();) {
    auto nx = next(it);
    auto [x, y] = it->first;
    EC[y].push_back(x);
    it = nx;
  }
  for (auto it = vert.begin(); it != vert.end();) {
    auto nxt = next(it);
    auto [x, y] = it->first;
    VR[x].push_back(y);
    it = nxt;
  }
  for (auto it = mp.begin(); it != mp.end();) {
    auto nxt = next(it);
    auto [x, y] = it->first;
    G[x].push_back(y);
    it = nxt;
  }
  for (int i=0; i<=R; ++i) {
    sort(VR[i].begin(), VR[i].end());
    sort(ER[i].begin(), ER[i].end());
  }
  for (int i=0; i<=C; ++i) {
    sort(EC[i].begin(), EC[i].end());
  }
  for (int i=0; i<=R; ++i) swap(X[i], VR[i]);
  STV.build(1, 0, R);
  for (int i=0; i<=R; ++i) swap(X[i], ER[i]);
  STER.build(1, 0, R);
  for (int i=0; i<=C; ++i) swap(X[i], EC[i]);
  STEC.build(1, 0, C);
  for (int i=0; i<=R; ++i) swap(X[i], G[i]);
  ST.build(1, 0, R);
}
 
int colour(int ar, int ac, int br, int bc) {
  --ar, --ac;
  f = 0;
  if (ar < mnx && mxx+1 < br && ac < mny && mxy+1 < bc) f = 1;
  e = STER.query(1, 0, r, ar+1, br-1, ac, bc-1) + STEC.query(1, 0, c, ac+1, bc-1, ar, br-1) + (br-ar+bc-ac) * 2;
  v = STV.query(1, 0, r, ar+1, br-1, ac+1, bc-1) + (br-ar+bc-ac) * 2;
  f += e-v+1;
  return f-ST.query(1, 0, r, ar, br-1, ac, bc-1);
}

Compilation message (stderr)

rainbow.cpp: In member function 'void SegTree2D::build(long long int, long long int, long long int)':
rainbow.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:29:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp:33:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~

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