Submission #262289

#TimeUsernameProblemLanguageResultExecution timeMemory
262289evpipisLand of the Rainbow Gold (APIO17_rainbow)C++11
12 / 100
1883 ms314716 KiB
#include <bits/stdc++.h> using namespace std; #include "rainbow.h" #define fi first #define se second #define mp make_pair #define pb push_back typedef pair<int, int> ii; const int len = 2e5+5; int n, m; vector<ii> com[len], edg[len]; set<int> mys[len]; struct node{ int sum; node *lef, *rig; node(int s = 0, node *l = NULL, node *r = NULL){ sum = s; lef = l; rig = r; } }; typedef node *pnode; pnode null = new node(); pnode update(pnode t, int l, int r, int i){ pnode cur = t; if (cur == null) cur = new node(0, null, null); cur->sum++; if (l == r) return cur; int mid = (l+r)/2; if (i <= mid) cur->lef = update(t->lef, l, mid, i); else cur->rig = update(t->rig, mid+1, r, i); return cur; } int query(pnode t, int l, int r, int i, int j){ if (r < i || j < l) return 0; if (i <= l && r <= j) return t->sum; int mid = (l+r)/2; return query(t->lef, l, mid, i, j) + query(t->rig, mid+1, r, i, j); } struct bit{ pnode tree[len]; // try to replace with vector instead int rev, row, col; // pref or suf? bit(int x = 0, int y = 0, int r = 0){ row = x; col = y; rev = r; } void init(){ for (int i = 1; i <= col; i++) tree[i] = null; } void upd(int i, int j){ if (rev) i = col-i+1; while (i <= col) tree[i] = update(tree[i], 1, row, j), i += i&(-i); } int ask(int i, int l, int r){ if (rev) i = col-i+1; int ans = 0; while (i > 0) ans += query(tree[i], 1, row, l, r), i -= i&(-i); return ans; } }; bit pref_com, suf_com; bit pref_edg, suf_edg; void nex_mov(int &x, int &y, char &c){ if (c == 'N') x--; else if (c == 'S') x++; else if (c == 'W') y--; else y++; } void find_com(int x, int y, char *moves){ int pos = 0; while (true){ mys[x].insert(y); if (moves[pos] == '\0') break; nex_mov(x, y, moves[pos++]); } for (int row = 1; row <= n; row++){ //printf("row%d\n", row); int cur = 1; for (auto col: mys[row]){ //printf("%d\n", col); if (cur <= col-1) com[row].pb(mp(cur, col-1)); cur = col+1; } //printf("cur in the end: %d\n", cur); //printf("n = %d, m = %d\n", n, m); if (cur <= m) com[row].pb(mp(cur, m)); } for (int row = 1; row <= n; row++){ //printf("row#%d:", row); for (auto cur: com[row]){ //printf(" (%d, %d)", cur.fi, cur.se); pref_com.upd(cur.se, row); suf_com.upd(cur.fi, row); } //printf("\n"); } } bool inter(ii a, ii b){ return !(a.se < b.fi || b.se < a.fi); } void find_edg(){ //printf("ins find_edg\n"); for (int row = 2; row <= n; row++){ for (int i = 0, j = 0; i < com[row].size(); i++){ while (j < com[row-1].size() && com[row-1][j].se < com[row][i].fi) j++; while (j < com[row-1].size() && inter(com[row-1][j], com[row][i])){ int for_pref = min(com[row-1][j].se, com[row][i].se); int for_suf = max(com[row-1][j].fi, com[row][i].fi); edg[row].pb(mp(for_suf, for_pref)); pref_edg.upd(for_pref, row); suf_edg.upd(for_suf, row); j++; } j = max(0, j-1); } } } void init(int n_, int m_, int sr, int sc, int M, char *moves) { n = n_, m = m_; null->lef = null->rig = null; pref_com = bit(n, m); suf_com = bit(n, m, 1); pref_edg = bit(n, m); suf_edg = bit(n, m, 1); pref_com.init(); suf_com.init(); pref_edg.init(); suf_edg.init(); find_com(sr, sc, moves); find_edg(); } int colour(int ar, int ac, int br, int bc) { int ans = 0; for (int row = ar; row <= br; row++) for (auto cur: com[row]) if (inter(mp(ac, bc), cur)) ans++; for (int row = ar+1; row <= br; row++) for (auto cur: edg[row]) if (inter(mp(ac, bc), cur)) ans--; /* int ans = pref_com.ask(m, ar, br) - pref_edg.ask(m, ar+1, br); ans -= pref_com.ask(ac-1, ar, br) - pref_edg.ask(ac-1, ar+1, br); ans -= suf_com.ask(bc+1, ar, br) - suf_edg.ask(bc+1, ar+1, br); */ return ans; }

Compilation message (stderr)

rainbow.cpp: In function 'void find_edg()':
rainbow.cpp:152:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for (int i = 0, j = 0; i < com[row].size(); i++){
      |                                ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:153:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             while (j < com[row-1].size() && com[row-1][j].se < com[row][i].fi)
      |                    ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |             while (j < com[row-1].size() && inter(com[row-1][j], com[row][i])){
      |                    ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...