Submission #883165

#	Time	Username	Problem	Language	Result	Execution time	Memory
883165		nguyentunglam	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	364 ms	286976 KiB

rainbow

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 2e5 + 10, S = 2e5 * 100 + 10;

vector<int> cell[N], one[N], two[N], three[N];

struct node {
  int left, right;
  int sum[4];
};

node T[S];

int r, c, cnt;

void up(int s, int l, int r, int pos, int val, int type) {
  if (l == r) {
    T[s].sum[type] += val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) {
    T[++cnt] = T[T[s].left];
    T[s].left = cnt;
    up(T[s].left, l, mid, pos, val, type);
  }
  else {
    T[++cnt] = T[T[s].right];
    T[s].right = cnt;
    up(T[s].right, mid + 1, r, pos, val, type);
  }
  T[s].sum[type] = T[T[s].left].sum[type] + T[T[s].right].sum[type];
}

int get(int s, int l, int r, int from, int to, int type) {
  if (l > to || r < from || !s) return 0;
  if (from <= l && r <= to) return T[s].sum[type];
  int mid = l + r >> 1;
  return get(T[s].left, l, mid, from, to, type) + get(T[s].right, mid + 1, r, from, to, type);
}

int it[N];

bool check (int x, int y) {
  int idx = lower_bound(cell[x].begin(), cell[x].end(), y) - cell[x].begin();
  if (idx < cell[x].size() && cell[x][idx] == y) return 1;
  return 0;
}

int query (int x, int y, int u, int v, int type) {
  return get(it[u], 1, c, y, v, type) - get(it[x - 1], 1, c, y, v, type);
}

int x, y, minx, miny, maxx, maxy;


void init(int R, int C, int sr, int sc, int m, char *s) {
  r = R;
  c = C;

  x = sr, y = sc, minx = x, maxx = x, miny = y, maxy = y;
  auto add = [&] () {
    cell[x].push_back(y);
    one[x].push_back(y);
    one[x - 1].push_back(y);
    two[x].push_back(y);
    two[x].push_back(y - 1);
    three[x].push_back(y);
    three[x].push_back(y - 1);
    three[x - 1].push_back(y);
    three[x - 1].push_back(y - 1);
    minx = min(minx, x);
    maxx = max(maxx, x);
    miny = min(miny, y);
    maxy = max(maxy, y);
  };

  add();
  for(int i = 0; i < m; i++) {
    if (s[i] == 'N') x--;
    if (s[i] == 'S') x++;

    if (s[i] == 'W') y--;
    if (s[i] == 'E') y++;
    add();
  }


  auto zip = [&] (vector<int> &v) {
    sort(all(v));
    v.resize(unique(all(v)) - v.begin());
  };


  for(int i = 1; i <= r; i++) {
    T[it[i] = ++cnt] = T[it[i - 1]];

    zip(cell[i]);
    zip(one[i]);
    zip(two[i]);
    zip(three[i]);

    for(int &j : cell[i]) {
      up(it[i], 1, c, j, 1, 0);
    }
    for(int &j : one[i]) if (j) {
      up(it[i], 1, c, j, 1, 1);
    }
    for(int &j : two[i]) if (j) up(it[i], 1, c, j, 1, 2);
    for(int &j : three[i]) if (j) up(it[i], 1, c, j, 1, 3);
  }
}


int colour(int x, int y, int u, int v) {
  int E = (u - x + 2) * 2 + (v - y + 2) * 2;
  if (x < u) E += query(x, y, u - 1, v, 1);
  if (y < v) E += query(x, y, u, v - 1, 2);
  int R = (u - x + 3) * (v - y + 3) - (u - x + 1) * (v - y + 1) + query(x, y, u, v, 0);
  if (x < u && y < v) E -= query(x, y, u - 1, v - 1, 3);
  int ans = E + 1 - R;
  if (x < minx && maxx < u && y < miny && maxy < v) ans++;
  return ans;
}



#ifdef ngu
int32_t main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  int r, c, m, q; cin >> r >> c >> m >> q;

  int sr, sc; cin >> sr >> sc;

  string s; cin >> s;

  init(r, c, sr, sc, m, &s[0]);

  for(int i = 1; i <= q; i++) {
    int ar, ac, br, bc; cin >> ar >> ac >> br >> bc;
    cout << colour(ar, ac, br, bc) << endl;
  }
}
#endif // ngu

Compilation message (stderr)

rainbow.cpp: In function 'void up(int, int, int, int, int, int)':
rainbow.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid = l + r >> 1;
      |             ~~^~~
rainbow.cpp: In function 'int get(int, int, int, int, int, int)':
rainbow.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = l + r >> 1;
      |             ~~^~~
rainbow.cpp: In function 'bool check(int, int)':
rainbow.cpp:49:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   if (idx < cell[x].size() && cell[x][idx] == y) return 1;
      |       ~~~~^~~~~~~~~~~~~~~~

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