이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |