Submission #984069

#	Time	Username	Problem	Language	Result	Execution time	Memory
984069		Unforgettablepl	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	49 ms	4940 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;

//#define int long long

bool water[3][200002];
vector<pair<int,int>> row1,row2,rowboth;

void init(int32_t R, int32_t C, int32_t sr, int32_t sc, int32_t M, char *S) {
    water[sr][sc]=true;
    for(int i=0;i<M;i++){
        if(S[i]=='N')sr--;
        else if(S[i]=='S')sr++;
        else if(S[i]=='E')sc++;
        else if(S[i]=='W')sc--;
        water[sr][sc]=true;
    }
    int c = 0;
    water[1][0]=true;
    water[2][0]=true;
    water[1][C+1]=true;
    water[2][C+1]=true;
    for(int i=1;i<=C+1;i++){
        if(water[1][i]==water[1][i-1])continue;
        if(water[1][i])row1.emplace_back(i-1,c);
        else row1.emplace_back(i,++c);
    }
    for(int i=1;i<=C+1;i++){
        if(water[2][i]==water[2][i-1])continue;
        if(water[2][i])row2.emplace_back(i-1,c);
        else row2.emplace_back(i,++c);
    }
    for(int i=1;i<=C+1;i++){
        if(water[1][i] and water[2][i] and !(water[1][i-1] and water[2][i-1]))rowboth.emplace_back(i-1,c);
        else if(water[1][i-1] and water[2][i-1] and !(water[1][i] and water[2][i]))rowboth.emplace_back(i,++c);
    }
}

int32_t colour(int32_t ar, int32_t ac, int32_t br, int32_t bc) {
    if(ar==2){
        if(row2.empty() or bc<row2.front().first or row2.back().first<ac)return 0;
        auto lo = (lower_bound(row2.begin(), row2.end(), make_pair(ac,0))->second)-1;
        auto hi = (--lower_bound(row2.begin(), row2.end(), make_pair(bc,(int)1e6)))->second;
        return hi-lo;
    } else if(br==1){
        if(row1.empty() or bc<row1.front().first or row1.back().first<ac)return 0;
        auto lo = (lower_bound(row1.begin(), row1.end(), make_pair(ac,0))->second)-1;
        auto hi = (--lower_bound(row1.begin(), row1.end(), make_pair(bc,(int)1e6)))->second;
        return hi-lo;
    } else {
        if(rowboth.empty() or bc<rowboth.front().first or rowboth.back().first<ac)return 0;
        auto lo = (lower_bound(rowboth.begin(), rowboth.end(), make_pair(ac,0))->second)-1;
        auto hi = (--lower_bound(rowboth.begin(), rowboth.end(), make_pair(bc,(int)1e6)))->second;
        return hi-lo;
    }
}

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26