oj.uz

Submission #733427

# Submission time Handle Problem Language Result Execution time Memory
733427 2023-04-30T17:11:47 Z 1075508020060209tc Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 144 ms 15812 KB 
#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
int n;int m;int sx;int sy;
string s;
int gr[5][200005];

struct SGTR{
int l;int r;
int gp[3];
}tr[800005];

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){
    tr[nw].gp[0]=0;
    tr[nw].gp[1]=0;
    tr[nw].gp[2]=0;
    if(gr[1][l]||gr[2][l]){
        tr[nw].gp[0]=1;
    }
    if(gr[1][l]){
        tr[nw].gp[1]=1;
    }
    if(gr[2][l]){
        tr[nw].gp[2]=1;
    }
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
tr[nw].gp[0]=tr[nw*2].gp[0]+tr[nw*2+1].gp[0];
tr[nw].gp[1]=tr[nw*2].gp[1]+tr[nw*2+1].gp[1];
tr[nw].gp[2]=tr[nw*2].gp[2]+tr[nw*2+1].gp[2];
if((gr[1][mi]&&gr[1][mi+1])||(gr[2][mi]&&gr[2][mi+1])){
    tr[nw].gp[0]--;
}
if((gr[2][mi]&&gr[2][mi+1])){
    tr[nw].gp[2]--;
}
if((gr[1][mi]&&gr[1][mi+1])){
    tr[nw].gp[1]--;
}
}



void init(int R, int C, int sr, int sc, int M, char *S) {
n=R;m=C;
gr[sr][sc]=1;
for(int i=0;i<M;i++){
    if(S[i]=='N'){sr--;}
    if(S[i]=='S'){sr++;}
    if(S[i]=='W'){sc--;}
    if(S[i]=='E'){sc++;}
    gr[sr][sc]=1;
}
for(int i=1;i<=C;i++){
    gr[1][i]^=1;
    gr[2][i]^=1;
}
buildtr(1,1,C);
}

int ans;int vs;

void slv(int pl,int id){
if(id==0){
    if( (gr[1][pl-1]&&gr[1][pl])||(gr[2][pl-1]&&gr[2][pl])  ){
        ans--;
    }
    return;
}
    if( (gr[id][pl-1]&&gr[id][pl])  ){
        ans--;
    }

}

void qry(int nw,int l,int r,int id){
if(tr[nw].l>=l&&tr[nw].r<=r){
    ans+=tr[nw].gp[id];
    if(vs){slv(tr[nw].l,id);}
    vs=1;
    return;
}
if(tr[nw].l>r||tr[nw].r<l){
    return;
}
qry(nw*2,l,r,id);qry(nw*2+1,l,r,id);
}



int colour(int ar, int ac, int br, int bc) {
ans=0;vs=0;
if(ar==1&&br==2){
    qry(1,ac,bc,0);
    return ans;
}
qry(1,ac,bc,ar);
return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 139 ms 15404 KB Output is correct
4 Correct 134 ms 15792 KB Output is correct
5 Correct 128 ms 15712 KB Output is correct
6 Correct 142 ms 15712 KB Output is correct
7 Correct 108 ms 15784 KB Output is correct
8 Correct 121 ms 15676 KB Output is correct
9 Correct 141 ms 15812 KB Output is correct
10 Correct 144 ms 15712 KB Output is correct
11 Correct 127 ms 15684 KB Output is correct
12 Correct 55 ms 15700 KB Output is correct
13 Correct 57 ms 15704 KB Output is correct
14 Correct 59 ms 15692 KB Output is correct
15 Correct 56 ms 15664 KB Output is correct
16 Correct 124 ms 15700 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -