Submission #321307

#TimeUsernameProblemLanguageResultExecution timeMemory
321307couplefire무지개나라 (APIO17_rainbow)C++17
12 / 100
915 ms214560 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; #define MAXN 1<<19 const int SZ = MAXN; template<class T> struct node { T val = 0; node<T>* c[2]; node() { c[0] = c[1] = NULL; } void upd(int ind, T v, int L = 0, int R = SZ-1) { // add v if (L == ind && R == ind) { val += v; return; } int M = (L+R)/2; if (ind <= M) { if (!c[0]) c[0] = new node(); c[0]->upd(ind,v,L,M); } else { if (!c[1]) c[1] = new node(); c[1]->upd(ind,v,M+1,R); } val = 0; for(int i = 0; i<2; i++) if (c[i]) val += c[i]->val; } T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment if (hi < L || R < lo) return 0; if (lo <= L && R <= hi) return val; int M = (L+R)/2; T res = 0; if (c[0]) res += c[0]->query(lo,hi,L,M); if (c[1]) res += c[1]->query(lo,hi,M+1,R); return res; } void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree if (L != R) { int M = (L+R)/2; if (ind <= M) { if (!c[0]) c[0] = new node(); c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M); } else { if (!c[1]) c[1] = new node(); c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R); } } val = (c0?c0->val:0)+(c1?c1->val:0); } }; template<class T> struct Node { node<T> seg; Node* c[2]; Node() { c[0] = c[1] = NULL; } void upd(int x, int y, T v, int L = 0, int R = SZ-1) { // add v if (L == x && R == x) { seg.upd(y,v); return; } int M = (L+R)/2; if (x <= M) { if (!c[0]) c[0] = new Node(); c[0]->upd(x,y,v,L,M); } else { if (!c[1]) c[1] = new Node(); c[1]->upd(x,y,v,M+1,R); } seg.upd(y,v); // only for addition // seg.UPD(y,c[0]?&c[0]->seg:NULL,c[1]?&c[1]->seg:NULL); } T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ-1) { // query sum of rectangle if (x1 <= L && R <= x2) return seg.query(y1,y2); if (x2 < L || R < x1) return 0; int M = (L+R)/2; T res = 0; if (c[0]) res += c[0]->query(x1,x2,y1,y2,L,M); if (c[1]) res += c[1]->query(x1,x2,y1,y2,M+1,R); return res; } }; map<pair<int, int>, int> mp; set<pair<int, int>> visited; vector<int> trows[MAXN]; vector<int> tcols[MAXN]; vector<pair<int, int>> rows[MAXN]; vector<pair<int, int>> cols[MAXN]; Node<int> seg; int minr = MAXN, maxr = -MAXN, minc = MAXN, maxc = -MAXN; void addSquare(int a, int b){ if(visited.count({a, b})) return; visited.insert({a, b}); mp[{a, b}]++; mp[{a+1, b}]++; mp[{a, b+1}]++; mp[{a+1, b+1}]++; trows[a].push_back(b); tcols[b].push_back(a); minr = min(minr, a); maxr = max(maxr, a); minc = min(minc, b); maxc = max(maxc, b); } void init(int R, int C, int sr, int sc, int M, char *S) { string s = S; addSquare(sr, sc); for(auto c : s){ if(c == 'N') sr--; if(c == 'S') sr++; if(c == 'W') sc--; if(c == 'E') sc++; addSquare(sr, sc); } for(auto p : mp){ if(p.second == 1) seg.upd(p.first.first, p.first.second, 1); if(p.second == 3) seg.upd(p.first.first, p.first.second, -1); } for(int i = 0; i<MAXN; i++) sort(trows[i].begin(), trows[i].end()); for(int i = 0; i<MAXN; i++) sort(tcols[i].begin(), tcols[i].end()); for(int i = 0; i<MAXN; i++){ if(trows[i].empty()) continue; int cur = trows[i][0]; for(int j = 1; j<trows[i].size(); j++){ if(trows[i][j] != trows[i][j-1]+1){ rows[i].push_back({cur, trows[i][j-1]}); cur = trows[i][j]; } } rows[i].push_back({cur, trows[i].back()}); } for(int i = 0; i<MAXN; i++){ if(tcols[i].empty()) continue; int cur = tcols[i][0]; for(int j = 1; j<tcols[i].size(); j++){ if(tcols[i][j] != tcols[i][j-1]+1){ cols[i].push_back({cur, tcols[i][j-1]}); cur = tcols[i][j]; } } cols[i].push_back({cur, tcols[i].back()}); } // for(int i = 0; i<MAXN; i++){ // if(cols[i].empty()) continue; // cout << i << endl; // for(auto j : cols[i]) cout << j.first << " " << j.second << endl; // cout << endl; // } } int colour(int ar, int ac, int br, int bc) { int ans = 0; ans += seg.query(ar+1, br, ac+1, bc); int p1, p2; // top row p1 = lower_bound(rows[ar].begin(), rows[ar].end(), make_pair(ac+1, -1))-rows[ar].begin(); p2 = lower_bound(rows[ar].begin(), rows[ar].end(), make_pair(bc+1, -1))-rows[ar].begin(); p1--; p2--; if(p1 >= 0 && rows[ar][p1].second >= ac && rows[ar][p1].second < bc) ans--; if(p2 >= 0 && rows[ar][p2].first > ac && rows[ar][p2].second >= bc) ans--; p1++; if(p2 >= 0 && rows[ar][p2].second >= bc) p2--; if(p1 < rows[ar].size() && rows[ar][p1].second < bc && p2 >= 0 && rows[ar][p2].first > ac) ans -= (p2-p1+1)*2; p1 = lower_bound(rows[br].begin(), rows[br].end(), make_pair(ac+1, -1))-rows[br].begin(); p2 = lower_bound(rows[br].begin(), rows[br].end(), make_pair(bc+1, -1))-rows[br].begin(); p1--; p2--; if(p1 >= 0 && rows[br][p1].second >= ac && rows[br][p1].second < bc) ans--; if(p2 >= 0 && rows[br][p2].first > ac && rows[br][p2].second >= bc) ans--; p1++; if(p2 >= 0 && rows[br][p2].second >= bc) p2--; if(p1 < rows[br].size() && rows[br][p1].second < bc && p2 >= 0 && rows[br][p2].first > ac) ans -= (p2-p1+1)*2; p1 = lower_bound(cols[ac].begin(), cols[ac].end(), make_pair(ar+1, -1))-cols[ac].begin(); p2 = lower_bound(cols[ac].begin(), cols[ac].end(), make_pair(br+1, -1))-cols[ac].begin(); p1--; p2--; if(p1 >= 0 && cols[ac][p1].second >= ar && cols[ac][p1].second < br) ans--; if(p2 >= 0 && cols[ac][p2].first > ar && cols[ac][p2].second >= br) ans--; p1++; if(p2 >= 0 && cols[ac][p2].second >= br) p2--; if(p1 < cols[ac].size() && cols[ac][p1].second < br && p2 >= 0 && cols[ac][p2].first > ar) ans -= (p2-p1+1)*2; p1 = lower_bound(cols[bc].begin(), cols[bc].end(), make_pair(ar+1, -1))-cols[bc].begin(); p2 = lower_bound(cols[bc].begin(), cols[bc].end(), make_pair(br+1, -1))-cols[bc].begin(); p1--; p2--; if(p1 >= 0 && cols[bc][p1].second >= ar && cols[bc][p1].second < br) ans--; if(p2 >= 0 && cols[bc][p2].first > ar && cols[bc][p2].second >= br) ans--; p1++; if(p2 >= 0 && cols[bc][p2].second >= br) p2--; if(p1 < cols[bc].size() && cols[bc][p1].second < br && p2 >= 0 && cols[bc][p2].first > ar) ans -= (p2-p1+1)*2; if(!visited.count({ar, ac})) ans--; if(!visited.count({ar, bc})) ans--; if(!visited.count({br, ac})) ans--; if(!visited.count({br, bc})) ans--; if(ar < minr && br > maxr && ac < minc && bc > maxc) ans -= 4; return -ans/4; }

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:113:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int j = 1; j<trows[i].size(); j++){
      |                        ~^~~~~~~~~~~~~~~~
rainbow.cpp:124:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int j = 1; j<tcols[i].size(); j++){
      |                        ~^~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:151:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     if(p1 < rows[ar].size() && rows[ar][p1].second < bc && p2 >= 0 && rows[ar][p2].first > ac) ans -= (p2-p1+1)*2;
      |        ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:159:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     if(p1 < rows[br].size() && rows[br][p1].second < bc && p2 >= 0 && rows[br][p2].first > ac) ans -= (p2-p1+1)*2;
      |        ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:167:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     if(p1 < cols[ac].size() && cols[ac][p1].second < br && p2 >= 0 && cols[ac][p2].first > ar) ans -= (p2-p1+1)*2;
      |        ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:175:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     if(p1 < cols[bc].size() && cols[bc][p1].second < br && p2 >= 0 && cols[bc][p2].first > ar) ans -= (p2-p1+1)*2;
      |        ~~~^~~~~~~~~~~~~~~~~
#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...