oj.uz

Submission #883122

# Submission time Handle Problem Language Result Execution time Memory
883122 2023-12-04T14:58:11 Z nguyentunglam Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 326 ms 101500 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 211 ms 62192 KB Output is correct
4 Correct 326 ms 95212 KB Output is correct
5 Correct 276 ms 95372 KB Output is correct
6 Correct 233 ms 101500 KB Output is correct
7 Correct 295 ms 74868 KB Output is correct
8 Correct 112 ms 13308 KB Output is correct
9 Correct 301 ms 95216 KB Output is correct
10 Correct 298 ms 95388 KB Output is correct
11 Correct 252 ms 101500 KB Output is correct
12 Correct 114 ms 89168 KB Output is correct
13 Correct 128 ms 95200 KB Output is correct
14 Correct 153 ms 95340 KB Output is correct
15 Correct 146 ms 101420 KB Output is correct
16 Correct 209 ms 70524 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 52 ms 98224 KB Output is correct
3 Correct 42 ms 96604 KB Output is correct
4 Correct 45 ms 99300 KB Output is correct
5 Correct 36 ms 76748 KB Output is correct
6 Correct 25 ms 49124 KB Output is correct
7 Incorrect 43 ms 85888 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9052 KB Output isn't correct
2 Halted 0 ms 0 KB -