제출 #683780

#제출 시각아이디문제언어결과실행 시간메모리
683780S2speed무지개나라 (APIO17_rainbow)C++17
12 / 100
361 ms176980 KiB
#include "rainbow.h" #include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") #define all(x) x.begin() , x.end() #define sze(x) (int)(x.size()) #define mp(x , y) make_pair(x , y) #define wall cout<<"--------------------------------------\n"; typedef long long int ll; typedef pair<ll , ll> pll; typedef pair<int , int> pii; typedef double db; typedef pair<pll , ll> plll; typedef pair<int , pii> piii; typedef pair<pll , pll> pllll; const ll maxn = 1e6 + 17 , md = 1e9 + 7 , inf = 2e8; vector<int> merge(vector<int> &a , vector<int> &b){ vector<int> res; int as = sze(a) , bs = sze(b); a.push_back(inf); b.push_back(inf); int x = 0 , y = 0; for(int e = 0 ; e < as + bs ; e++){ if(a[x] < b[y]){ res.push_back(a[x++]); } else { res.push_back(b[y++]); } } a.pop_back(); b.pop_back(); return res; } struct segtree { int sz = 1; vector<vector<int>> val; void init(int n){ while(sz < n) sz <<= 1; val.resize(sz << 1); return; } void add(int i , int k , int x , int lx , int rx){ if(rx - lx == 1){ val[x].push_back(k); return; } int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; if(i < m){ add(i , k , ln , lx , m); } else { add(i , k , rn , m , rx); } return; } void add(int i , int k){ add(i , k , 0 , 0 , sz); return; } void build(int x , int lx , int rx){ if(rx - lx == 1){ sort(all(val[x])); val[x].resize(distance(val[x].begin() , unique(all(val[x])))); return; } int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; build(ln , lx , m); build(rn , m , rx); val[x] = merge(val[ln] , val[rn]); return; } void build(){ build(0 , 0 , sz); return; } int cal(int l1 , int r1 , int l2 , int r2 , int x , int lx , int rx){ if(rx <= l1 || lx >= r1) return 0; if(rx <= r1 && lx >= l1){ int res = lower_bound(all(val[x]) , r2) - lower_bound(all(val[x]) , l2); return res; } int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1; int a = cal(l1 , r1 , l2 , r2 , ln , lx , m) , b = cal(l1 , r1 , l2 , r2 , rn , m , rx); return a + b; } int cal(int l1 , int r1 , int l2 , int r2){ return cal(l1 , r1 , l2 , r2 , 0 , 0 , sz); } }; segtree v , e[2] , f; void add(int x , int y){ v.add(x , y); e[0].add(x - 1 , y); e[0].add(x , y); e[1].add(x , y - 1); e[1].add(x , y); f.add(x - 1 , y - 1); f.add(x - 1 , y); f.add(x , y - 1); f.add(x , y); return; } void init(int n , int m , int sx , int sy , int k , char *s){ v.init(n + 1); e[0].init(n + 1); e[1].init(n + 1); f.init(n + 1); int x = sx , y = sy; for(int i = 0 ; ; i++){ add(x , y); if(i == k) break; if(s[i] == 'N'){ x--; } else if(s[i] == 'S'){ x++; } else if(s[i] == 'E'){ y++; } else { y--; } } v.build(); e[0].build(); e[1].build(); f.build(); return; } int colour(int l1 , int l2 , int r1 , int r2){ r1++; r2++; ll V = 1ll * (r1 - l1) * (r2 - l2) - v.cal(l1 , r1 , l2 , r2); ll E = 1ll * (r1 - l1) * (r2 - l2 - 1) + 1ll * (r1 - l1 - 1) * (r2 - l2); E -= e[0].cal(l1 , r1 - 1 , l2 , r2) + e[1].cal(l1 , r1 , l2 , r2 - 1); ll F = 1ll * (r1 - l1 - 1) * (r2 - l2 - 1) - f.cal(l1 , r1 - 1 , l2 , r2 - 1) + 1; return V - E + F - 1; }
#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...