Submission #1209838

#TimeUsernameProblemLanguageResultExecution timeMemory
1209838Zbyszek99Land of the Rainbow Gold (APIO17_rainbow)C++20
12 / 100
2080 ms592328 KiB
#include "rainbow.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; struct node { int sum = 0; int l = 0; int r = (1 << 18)-1; bool is_son = 0; node* left; node* right; void upd() { if(!is_son) { left = new node; left -> l = l; left -> r = (l+r)/2; right = new node; right -> l = (l+r)/2+1; right -> r = r; } is_son = 1; } int get_sum(int l2, int r2) { if(r2 < l || l2 > r) return 0; if(l >= l2 && r <= r2) return sum; upd(); return left -> get_sum(l2,r2) + right -> get_sum(l2,r2); } void add_poz(int poz, node* prev) { sum = prev->sum + 1; if(l == r) { return; } is_son = 1; prev -> upd(); if(poz <= (l+r)/2) { right = prev->right; left = new node; left -> l = l; left -> r = (l+r)/2; left -> add_poz(poz,prev->left); } else { left = prev->left; right = new node; right-> l = (l+r)/2+1; right -> r = r; right -> add_poz(poz,prev->right); } } }; struct psgtree { vector<node> nodes; map<int,int> xpoz; set<int> xposes; psgtree() { node beg_node; nodes.pb(beg_node); xpoz[-1] = 0; xposes.insert(-1); } void addy(int x, int y) { xpoz[x] = siz(nodes); node new_node; new_node.add_poz(y,&(nodes.back())); nodes.pb(new_node); xposes.insert(x); } int get_sum_x(int x, int l, int r) { auto it = xposes.upper_bound(x); it--; return nodes[xpoz[*it]].get_sum(l,r); } int get_square(int lx, int rx, int ly, int ry) { if(lx > rx || ly > ry) return 0; return get_sum_x(rx,ly,ry) - get_sum_x(lx-1,ly,ry); } }; psgtree nodes; psgtree edges1; psgtree edges2; psgtree regions; set<pii> nodes_s; set<pii> edges1_s; set<pii> edges2_s; set<pii> regions_s; void add_reg(int x, int y) { regions_s.insert({x,y}); edges1_s.insert({x,y}); edges1_s.insert({x,y+1}); edges2_s.insert({x,y}); edges2_s.insert({x+1,y}); nodes_s.insert({x,y}); nodes_s.insert({x+1,y}); nodes_s.insert({x,y+1}); nodes_s.insert({x+1,y+1}); } void make_tree(set<pii>* s, psgtree* tr) { forall(it,*s) { tr -> addy(it.ff,it.ss); } } void init(int R, int C, int sr, int sc, int M, char *S) { int cur_x = sc; int cur_y = sr; add_reg(cur_x,cur_y); rep(i,M) { switch(S[i]) { case 'N': { cur_y--; break; } case 'S': { cur_y++; break; } case 'W': { cur_x--; break; } case 'E': { cur_x++; break; } } add_reg(cur_x,cur_y); } make_tree(&nodes_s,&nodes); make_tree(&edges1_s,&edges1); make_tree(&edges2_s,&edges2); make_tree(&regions_s,&regions); } int colour(int ly, int lx, int ry, int rx) { //F= 2 + E - V - old_F int E = (edges1.get_square(lx,rx,ly+1,ry) + 2 * (rx-lx+1)) + (edges2.get_square(lx+1,rx,ly,ry) + 2 * (ry-ly+1)); int old_F = regions.get_square(lx,rx,ly,ry)+1; int V = nodes.get_square(lx+1,rx,ly+1,ry) + 2 * (rx - lx + ry - ly + 4) - 4; return 2 + E - V - old_F; }
#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...