Submission #883122

#	Time	Username	Problem	Language	Result	Execution time	Memory
883122		nguyentunglam	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	326 ms	101500 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 * 30 + 10;

vector<int> cell[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);
}

void init(int R, int C, int sr, int sc, int m, char *s) {
  r = R;
  c = C;
  int x = sr, y = sc;
  cell[x].push_back(y);
  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++;
    cell[x].push_back(y);
  }

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

    sort(all(cell[i]));
    cell[i].resize(unique(all(cell[i])) - cell[i].begin());

    for(int &j : cell[i]) {
      up(it[i], 1, c, j, 1, 0);
      int ok = 0;
      if (check(i, j - 1)) {
        up(it[i], 1, c, j, 1, 1), ok++;
      }
      if (check(i - 1, j)) {
        up(it[i], 1, c, j, 1, 2), ok++;
      }
      if (ok == 2 && check(i - 1, j - 1)) up(it[i], 1, c, j, 1, 3);
    }
  }
}


int colour(int x, int y, int u, int v) {
//  cout << x << " " << y << " " << u << " " << v << endl;
  int V = query(x, y, u, v, 0);
  int E = 0;
  if (y < v) E += query(x, y + 1, u, v, 1);
  if (x < u) E += query(x + 1, y, u, v, 2);

  E += query(x, y, x, v, 0);
  E += query(u, y, u, v, 0);
  E += query(x, y, u, y, 0);
  E += query(x, v, u, v, 0);

  int quad = 0;
  if (x < u && y < v) quad += query(x + 1, y + 1, u, v, 3);
  if (x < u) {
    quad += query(x + 1, y, u, y, 2);
    quad += query(x + 1, v, u, v, 2);
  }

  if (y < v) {
    quad += query(x, y + 1, x, v, 1);
    quad += query(u, y + 1, u, v, 1);
  }

//  cout << query(4, 3, 4, 3, 1) << endl;

//  cout << quad << " " << check(x, y) << " " << check(x, v) << " " << check(u, y) << " " << check(u, v) << endl;

  quad += check(x, y) + check(x, v) + check(u, y) + check(u, v);

//  cout << E << " " << V << " " << quad << endl;

  int ans = E - V + 1 - quad;
  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: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26