| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 197338 | stefdasca | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
using namespace std;
const int maxsz = 2e7;
int cnt = 1, segtree[maxsz], left_c[maxsz], right_c[maxsz];
struct aint
{
set<int> data[200002];
int roots[200002];
void add(int x, int y)
{
data[x].insert(y);
}
void build()
{
for(int i = 1; i <= 200000; ++i)
{
roots[i+1] = roots[i];
for(set<int> ::iterator it = data[i].begin(); it != data[i].end(); ++it)
update(*it, roots[i+1]);
}
}
void update(int pos, int &node, int l = 1, int r = 200000)
{
segtree[cnt] = segtree[node] + 1;
left_c[cnt] = left_c[node];
right_c[cnt] = right_c[node];
node = cnt++;
if (l == r)
return;
int mid = (l + r) / 2;
if (pos > mid)
update(pos, right_c[node], mid + 1, r);
else
update(pos, left_c[node], l, mid);
}
int query(int l1, int r1, int l2, int r2)
{
if (l2 > r2)
return 0;
return query(l2, r2, roots[r1 + 1], 1, 200000) - query(l2, r2, roots[l1], 1, 200000);
}
int query(int a, int b, int node, int l, int r)
{
if (a > r || b < l)
return 0;
if (a <= l && b >= r)
return segtree[node];
int mid = (l + r) / 2;
return query(a, b, left_c[node], l, mid) + query(a, b, right_c[node], mid + 1, r);
}
} vertices, edges_horiz, edges_vert, rivers;
int mxL, mnL = (1<<20), mxC, mnC = (1<<20);
void add_river(int L, int C)
{
mxL = max(mxL, L);
mxC = max(mxC, C);
mnL = min(mnL, L);
mnC = min(mnC, C);
vertices.add(x, y);
vertices.add(x + 1, y);
vertices.add(x, y + 1);
vertices.add(x + 1, y + 1);
edges_horiz.add(x, y);
edges_horiz.add(x + 1, y);
edges_vert.add(x, y);
edges_vert.add(x, y + 1);
rivers.add(x, y);
}
void init(int R, int C, int sr, int sc, int M, char *S)
{
add_river(sr, sc);
for(int i = 0; i < M; ++i)
{
sr += (S[i] == 'S');
sr -= (S[i] == 'N');
sc += (S[i] == 'E');
sc -= (S[i] == 'W');
add_river(sr, sc);
}
vertices.build();
edges_horiz.build();
edges_vert.build();
rivers.build();
}
int colour(int ar, int ac, int br, int bc)
{
int E = edges_horiz.query(ar + 1, br, ac, bc) + edges_vert.query(ar, br, ac + 1, bc);
int V = vertices.query(ar + 1, br, ac + 1, bc);
int R = rivers.query(ar, br, ac, bc);
int C;
if(ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c)
C = 1;
else
C = 2;
return E - V + C - R;
}