| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 252941 | orgiooo | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ret return 0
#define con continue
#define db double
#define gcd __gcd
#define freopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
using namespace std;
ll n,m,ans,t,cnt,x,y,z,u;
ll i,j,r,l,k;
ll a[1231234],b[1234567],d[1234567],e[1234567];
map <ll,ll> f;
set<pair<ll,ll>> s;
set<int>::iterator it;
vector <ll> c[1234567];
string p[2000000],q,w[2000000];
ll lcm(ll x,ll y){
ll z=gcd(x,y);
return x*y/z;
}
int main(){
cin>>n>>m>>k>>t;
cin>>x>>y;
cin>>q;
x--;y--;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
w[i][j]='0';
}
}
w[x][y]='1';
for(i=0;i<k;i++){
if (q[i]=='W'){
y--;
}
if (q[i]=='E'){
y++;
}
if (q[i]=='N'){
x--;
}
if (q[i]=='S'){
x++;
}
w[x][y]='1';
}
ll x1 ,x2,y1,y2;
while (t--){
cin>>x1>>y1>>x2>>y2;
x1--;y1--;x2--;y2--;
for(i=x1;i<=x2;i++){
for(j=y1;j<=y2;j++){
p[i-x1][j-y1]=w[i][j];
}
}
x=x2-x1;y=y2-y1;x++;y++;
cnt=0 ;
for (i=0;i<x;i++){
for(j=0;j<y;j++){
if (p[i][j]=='0'){
cnt ++ ;
}
}
}
l=1;
while (cnt>0){
ll ss =0 ;
for (i=0;i<x;i++){
for(j=0;j<y;j++){
if (p[i][j]>49){
if (i+1<x&&p[i+1][j]=='0'){
ss++;
p[i+1][j]=p[i][j];
}
if (j+1<y&&p[i][j+1]=='0'){
ss++;
p[i][j+1]=p[i][j];
}
if (i-1>=0&&p[i-1][j]=='0'){
ss++;
p[i-1][j]=p[i][j];
}
if (j-1>=0&&p[i][j-1]=='0'){
ss++;
p[i][j-1]=p[i][j];
}
}
}
}
if (ss==0){
l++;
for (i=0;i<x;i++){
ll kk =0;
for(j=0;j<y;j++){
if (p[i][j]=='0'){
p[i][j]=char(l+48);
kk++;break;
}
}
if (kk>0){
break;
}
}
}
cnt=0;
for (i=0;i<x;i++){
for(j=0;j<y;j++){
if (p[i][j]=='0'){
cnt ++ ;
}
}
}
}
cout<<l-2+1<<endl;
}
}