oj.uz

Submission #1064631

# Submission time Handle Problem Language Result Execution time Memory
1064631 2024-08-18T15:54:59 Z abczz Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 463 ms 263524 KB 
#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;
  if (ar < mnx && mxx+1 < br && ac < mny && mxy+1 < bc) return 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

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

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99156 KB Output is correct
2 Correct 52 ms 99668 KB Output is correct
3 Incorrect 58 ms 99152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98896 KB Output is correct
2 Correct 64 ms 99052 KB Output is correct
3 Correct 325 ms 149828 KB Output is correct
4 Correct 407 ms 182188 KB Output is correct
5 Correct 414 ms 181168 KB Output is correct
6 Correct 361 ms 164544 KB Output is correct
7 Correct 406 ms 164472 KB Output is correct
8 Correct 131 ms 104304 KB Output is correct
9 Correct 445 ms 182196 KB Output is correct
10 Correct 463 ms 180944 KB Output is correct
11 Correct 406 ms 164852 KB Output is correct
12 Correct 325 ms 176800 KB Output is correct
13 Correct 368 ms 182200 KB Output is correct
14 Correct 344 ms 180912 KB Output is correct
15 Correct 334 ms 164844 KB Output is correct
16 Correct 317 ms 159676 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98900 KB Output is correct
2 Correct 346 ms 240728 KB Output is correct
3 Correct 344 ms 259004 KB Output is correct
4 Correct 338 ms 263524 KB Output is correct
5 Correct 263 ms 215484 KB Output is correct
6 Correct 122 ms 127932 KB Output is correct
7 Incorrect 178 ms 154000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99156 KB Output is correct
2 Correct 52 ms 99668 KB Output is correct
3 Incorrect 58 ms 99152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99156 KB Output is correct
2 Correct 52 ms 99668 KB Output is correct
3 Incorrect 58 ms 99152 KB Output isn't correct
4 Halted 0 ms 0 KB -