Submission #960646

#	Time	Username	Problem	Language	Result	Execution time	Memory
960646		hazzle	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	1538 ms	473824 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

typedef struct node* pnode;
struct node{
     int s;
     pnode l, r;
     node(int x = 0): s(x) { l = r = nullptr; }
     node(pnode tl, pnode tr): l(tl), r(tr) {
          s = 0;
          if (l) s += l->s;
          if (r) s += r->s;
     }
};

pnode build(int tl, int tr){
     if (tl + 1 == tr) return new node();
     int tm = tl + tr >> 1;
     return new node(build(tl, tm), build(tm, tr));
}

pnode upd(int p, int x, int tl, int tr, pnode t){
     if (tl + 1 == tr) return new node(t->s + x);
     int tm = tl + tr >> 1;
     if (p < tm) return new node(upd(p, x, tl, tm, t->l), t->r);
     return new node(t->l, upd(p, x, tm, tr, t->r));
}

int get(int l, int r, int tl, int tr, pnode t){
     if (!t || l >= r) return 0;
     if (tl == l && tr == r) return t->s;
     int tm = tl + tr >> 1;
     return get(l, min(tm, r), tl, tm, t->l)
          + get(max(l, tm), r, tm, tr, t->r);
}

struct sum2d{
     int n, m;
     vec <pnode> t;
     vec <map <int, int>> updates;

     sum2d() {}

     sum2d(int n, int m): n(n), m(m) {
          t.resize(n);
          updates.resize(n);
     }

     void mark(int x, int y){
          assert(x < n);
          assert(x >= 0);
          assert(y < m);
          assert(y >= 0);
          updates[x][y] = 1;
     }

     void init(){
          t[0] = build(0, m);
          for (int i = 0; i < n; ++i){
               if (i) t[i] = t[i - 1];
               for (auto &[y, d]: updates[i]){
                    t[i] = upd(y, d, 0, m, t[i]);
               }
          }
     }

     int sum(int lx, int ly, int rx, int ry){ // sum on [lx, rx] U [ly, ry]
          int ans = get(ly, ry + 1, 0, m, t[rx]);
          if (lx) ans -= get(ly, ry + 1, 0, m, t[lx - 1]);
          return ans;
     }

     int at(int x, int y){
          int ans = get(y, y + 1, 0, m, t[x]);
          if (x) ans -= get(y, y + 1, 0, m, t[x - 1]);
          return ans;
     }
};

sum2d f, v_e, h_e, v;

void init(int R, int C, int sr, int sc, int M, char *S) {
     --sr, --sc;

     f = sum2d(R, C);
     v_e = sum2d(R, C + 1);
     h_e = sum2d(R + 1, C);
     v = sum2d(R + 1, C + 1);

     auto mark = [&](int x, int y){
          f.mark(x, y);
          v.mark(x, y);
          v.mark(x + 1, y);
          v.mark(x, y + 1);
          v.mark(x + 1, y + 1);
          h_e.mark(x, y);
          h_e.mark(x + 1, y);
          v_e.mark(x, y);
          v_e.mark(x, y + 1);
     };

     mark(sr, sc);
     for (int i = 0; i < M; ++i){
          if (S[i] == 'N') --sr;
          if (S[i] == 'S') ++sr;
          if (S[i] == 'W') --sc;
          if (S[i] == 'E') ++sc;
          mark(sr, sc);
     }
     f.init();
     v.init();
     h_e.init();
     v_e.init();
//     cout << "\n";
//     for (int i = 0; i < R; ++i){
//          for (int j = 0; j < C; ++j){
//               cout << f.at(i, j);
//          }
//          cout << "\n";
//     }
//     cout << "\n";
}

int colour(int lx, int ly, int rx, int ry) {
     --lx, --ly, --rx, --ry;

     int extra_faces = f.sum(lx, ly, rx, ry); // river cells

     int vertices = v.sum(lx, ly, rx + 1, ry + 1); // inside


     vertices += rx - lx + 2 - v.sum(lx, ly, rx + 1, ly);
     vertices += rx - lx + 2 - v.sum(lx, ry + 1, rx + 1, ry + 1);
     vertices += ry - ly - v.sum(lx, ly + 1, lx, ry);
     vertices += ry - ly - v.sum(rx + 1, ly + 1, rx + 1, ry); // borders

//     cout << "inside: " << v.sum(lx, ly, rx + 1, ry + 1) << "\n";
//     cout << "left border: " << rx - lx + 2 << " - " << v.sum(lx, ly, rx + 1, ly) << "\n";
//     cout << "right border: " << rx - lx + 2 << " - " << v.sum(lx, ry + 1, rx + 1, ry + 1) << "\n";
//     cout << "top border: " << ry - ly << " - " << v.sum(lx, ly + 1, lx, ry) << "\n";
//     cout << "bottom border: " << ry - ly << " - " << v.sum(rx + 1, ly + 1, rx + 1, ry) << "\n";
//     cout << "\n";

     int v_edges = v_e.sum(lx, ly, rx, ry + 1); // inside
     v_edges += rx - lx + 1 - v_e.sum(lx, ly, rx, ly);
     v_edges += rx - lx + 1 - v_e.sum(lx, ry + 1, rx, ry + 1); // borders

     int h_edges = h_e.sum(lx, ly, rx + 1, ry); //inside
     h_edges += ry - ly + 1 - h_e.sum(lx, ly, lx, ry);
     h_edges += ry - ly + 1 - h_e.sum(rx + 1, ly, rx + 1, ry); // borders

//     cout << "hor inside: " << h_e.sum(lx, ly, rx + 1, ry) << "\n";
//     cout << "hor top border: " << ry - ly + 1 << " - " << h_e.sum(lx, ly, lx, ry) << "\n";
//     cout << "hor bottom border: " << ry - ly + 1 << " - " << h_e.sum(rx + 1, ly, rx + 1, ry) << "\n";
//     cout << "\n";
//
//     cout << "v_e:" << v_edges << "\n";
//     cout << "h_e:" << h_edges << "\n";
//     cout << "v:" << vertices << "\n";
//     cout << "e_f:" << extra_faces << "\n";

     return 2 + v_edges + h_edges - vertices - extra_faces - 1; //using v - e + f = 2 => f = 2 + e - v
}

Compilation message (stderr)

rainbow.cpp: In function 'node* build(int, int)':
rainbow.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |      int tm = tl + tr >> 1;
      |               ~~~^~~~
rainbow.cpp: In function 'node* upd(int, int, int, int, pnode)':
rainbow.cpp:57:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |      int tm = tl + tr >> 1;
      |               ~~~^~~~
rainbow.cpp: In function 'int get(int, int, int, int, pnode)':
rainbow.cpp:65:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |      int tm = tl + tr >> 1;
      |               ~~~^~~~

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