| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 239069 | urd05 | 무지개나라 (APIO17_rainbow) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
char str[100001];
int r,c,sr,sc;
int l;
int arr[51][200001];
vector<int> rst[200001];
vector<int> ren[200001];
vector<int> cst[200001];
vector<int> cen[200001];
typedef pair<int,int> P;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
vector<int> check[3];
void init(int rr,int cc,int srr,int scc,int m,char s[]) {
r=rr;
c=cc;
sr=srr;
sc=scc;
l=m;
for(int i=0;i<m;i++) {
str[i]=s[i];
}
arr[sr][sc]=1;
vector<P> v;
int x=sr;
int y=sc;
v.push_back(P(x,y));
for(int i=0;i<m;i++) {
if (str[i]=='W') {
y--;
}
if (str[i]=='E') {
y++;
}
if (str[i]=='N') {
x--;
}
if (str[i]=='S') {
x++;
}
arr[x][y]=1;
v.push_back(P(x,y));
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++) {
if (i==0) {
rst[v[i].first].push_back(v[i].second);
}
if (i+1==v.size()) {
ren[v[i].first].push_back(v[i].second);
}
if (i!=0&&(v[i-1].first!=v[i].first||v[i-1].second+1!=v[i].second)) {
ren[v[i-1].first].push_back(v[i-1].second);
rst[v[i].first].push_back(v[i].second);
}
}
for(int i=0;i<v.size();i++) {
int temp=v[i].first;
v[i].first=v[i].second;
v[i].second=temp;
}
for(int i=0;i<v.size();i++) {
if (i==0) {
cst[v[i].first].push_back(v[i].second);
}
if (i+1==v.size()) {
cen[v[i].first].push_back(v[i].second);
}
if (i!=0&&(v[i-1].first!=v[i].first||v[i-1].second+1!=v[i].second)) {
cen[v[i-1].first].push_back(v[i-1].second);
cst[v[i].first].push_back(v[i].second);
}
}
if (r==2) {
for(int i=1;i<=c;i++) {
if (arr[1][i]==1) {
check[1].push_back(i);
}
}
for(int i=1;i<=c;i++) {
if (arr[2][i]==1) {
check[2].push_back(i);
}
}
}
}
int solve1(int ar,int ac,int br,int bc) {
int inter=0;
inter+=(upper_bound(rst[ar].begin(),rst[ar].end(),bc)-rst[ar].begin())-(lower_bound(ren[ar].begin(),ren[ar].end(),ac)-ren[ar].begin());
inter+=(upper_bound(rst[br].begin(),rst[br].end(),bc)-rst[br].begin())-(lower_bound(ren[br].begin(),ren[br].end(),ac)-ren[br].begin());
inter+=(upper_bound(cst[ac].begin(),cst[ac].end(),br)-cst[ac].begin())-(lower_bound(cen[ac].begin(),cen[ac].end(),ar)-cen[ac].begin());
inter+=(upper_bound(cst[bc].begin(),cst[bc].end(),bc)-cst[bc].begin())-(lower_bound(cen[bc].begin(),cen[bc].end(),bc)-cen[bc].begin());
if (inter==4&&arr[ar][ac]==1&&arr[ar][bc]==1&&arr[br][ac]==1&&arr[br][bc]==1) {
inter=1;
}
else {
inter-=arr[ar][ac]+arr[ar][bc]+arr[br][ac]+arr[br][bc];
}
if (inter==0) {
return 1;
}
}
int solve2(int ar,int ac,int br,int bc) {
int inter=0;
inter+=(upper_bound(rst[ar].begin(),rst[ar].end(),bc)-rst[ar].begin())-(lower_bound(ren[ar].begin(),ren[ar].end(),ac)-ren[ar].begin());
inter+=(upper_bound(rst[br].begin(),rst[br].end(),bc)-rst[br].begin())-(lower_bound(ren[br].begin(),ren[br].end(),ac)-ren[br].begin());
inter+=(upper_bound(cst[ac].begin(),cst[ac].end(),br)-cst[ac].begin())-(lower_bound(cen[ac].begin(),cen[ac].end(),ar)-cen[ac].begin());
inter+=(upper_bound(cst[bc].begin(),cst[bc].end(),bc)-cst[bc].begin())-(lower_bound(cen[bc].begin(),cen[bc].end(),bc)-cen[bc].begin());
if (inter==4&&arr[ar][ac]==1&&arr[ar][bc]==1&&arr[br][ac]==1&&arr[br][bc]==1) {
inter=1;
}
else {
inter-=arr[ar][ac]+arr[ar][bc]+arr[br][ac]+arr[br][bc];
}
if (inter==0) {
return 1;
}
bool flag=false;
for(int i=ar;i<=br;i++) {
auto iter=lower_bound(check[i].begin(),check[i].end(),ac);
if (iter==check[i].end()||(*iter)>bc) {
flag=true;
}
}
return inter-flag+1;
}
int solve3(int ar,int ac,int br,int bc) {
}
int colours(int ar,int ac,int br,int bc) {
solve2(ar,ac,br,bc);
}