oj.uz

Submission #883164

# Submission time Handle Problem Language Result Execution time Memory
883164 2023-12-04T16:59:36 Z nguyentunglam Land of the Rainbow Gold (APIO17_rainbow) C++17
38 / 100
 258 ms 335348 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], 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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB Output is correct
2 Correct 6 ms 23240 KB Output is correct
3 Correct 6 ms 23132 KB Output is correct
4 Correct 6 ms 23228 KB Output is correct
5 Correct 7 ms 23264 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 5 ms 23252 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23260 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 6 ms 23360 KB Output is correct
12 Correct 7 ms 23220 KB Output is correct
13 Correct 6 ms 23132 KB Output is correct
14 Correct 7 ms 23388 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23260 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23260 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 207 ms 155580 KB Output is correct
4 Runtime error 250 ms 335348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23132 KB Output is correct
2 Runtime error 258 ms 334492 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB Output is correct
2 Correct 6 ms 23240 KB Output is correct
3 Correct 6 ms 23132 KB Output is correct
4 Correct 6 ms 23228 KB Output is correct
5 Correct 7 ms 23264 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 5 ms 23252 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23260 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 6 ms 23360 KB Output is correct
12 Correct 7 ms 23220 KB Output is correct
13 Correct 6 ms 23132 KB Output is correct
14 Correct 7 ms 23388 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23260 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct
18 Correct 235 ms 101716 KB Output is correct
19 Correct 150 ms 28760 KB Output is correct
20 Correct 113 ms 26616 KB Output is correct
21 Correct 128 ms 26704 KB Output is correct
22 Correct 133 ms 28608 KB Output is correct
23 Correct 160 ms 28892 KB Output is correct
24 Correct 128 ms 26604 KB Output is correct
25 Correct 125 ms 26652 KB Output is correct
26 Correct 138 ms 28752 KB Output is correct
27 Correct 133 ms 89392 KB Output is correct
28 Correct 124 ms 58664 KB Output is correct
29 Correct 130 ms 83456 KB Output is correct
30 Correct 205 ms 169024 KB Output is correct
31 Correct 7 ms 23128 KB Output is correct
32 Correct 207 ms 88660 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB Output is correct
2 Correct 6 ms 23240 KB Output is correct
3 Correct 6 ms 23132 KB Output is correct
4 Correct 6 ms 23228 KB Output is correct
5 Correct 7 ms 23264 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 5 ms 23252 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23260 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 6 ms 23360 KB Output is correct
12 Correct 7 ms 23220 KB Output is correct
13 Correct 6 ms 23132 KB Output is correct
14 Correct 7 ms 23388 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23260 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct
18 Correct 235 ms 101716 KB Output is correct
19 Correct 150 ms 28760 KB Output is correct
20 Correct 113 ms 26616 KB Output is correct
21 Correct 128 ms 26704 KB Output is correct
22 Correct 133 ms 28608 KB Output is correct
23 Correct 160 ms 28892 KB Output is correct
24 Correct 128 ms 26604 KB Output is correct
25 Correct 125 ms 26652 KB Output is correct
26 Correct 138 ms 28752 KB Output is correct
27 Correct 133 ms 89392 KB Output is correct
28 Correct 124 ms 58664 KB Output is correct
29 Correct 130 ms 83456 KB Output is correct
30 Correct 205 ms 169024 KB Output is correct
31 Correct 7 ms 23128 KB Output is correct
32 Correct 207 ms 88660 KB Output is correct
33 Runtime error 258 ms 334492 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -