Submission #972812

#	Time	Username	Problem	Language	Result	Execution time	Memory
972812		bachhoangxuan	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	353 ms	88824 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 2e5+5;

int R,C;

struct BIT{
    vector<int> com[maxn],pre[maxn];
    BIT(){}
    void update(int x,int y){
        for(int i=x;i<=R;i+=(i&(-i))) com[i].push_back(y);
    }
    void build(int x){
        sort(com[x].begin(),com[x].end());
        vector<int> cur=com[x];com[x].clear();
        for(int y:cur){
            if(com[x].empty() || com[x].back()!=y){
                com[x].push_back(y);
                pre[x].push_back(1);
            }
            else pre[x].back()++;
        }
        for(int i=1;i<(int)com[x].size();i++) pre[x][i]+=pre[x][i-1];
    }
    void init(vector<pii> &A){
        sort(A.begin(),A.end());
        A.erase(unique(A.begin(),A.end()),A.end());
        for(auto [x,y]:A) update(x,y);
        for(int i=1;i<=R;i++) build(i);
    }
    int query(int x,int y){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))){
            int pos=upper_bound(com[x].begin(),com[x].end(),y)-com[x].begin()-1;
            res+=(pos<0?0:pre[x][pos]);
        }
        return res;
    }
    int get(int sx,int sy,int tx,int ty){
        return query(tx,ty)-query(tx,sy-1)-query(sx-1,ty)+query(sx-1,sy-1);
    }
}g,p,cc,rw;

void init(int _R, int _C, int x, int y, int M, char *S) {
    vector<pii> row,col,G,P;
    R=_R+1;C=_C+1;
    for(int i=0;i<=M;i++){
        G.push_back({x,y});
        for(int a=0;a<=1;a++) for(int b=0;b<=1;b++){
            P.push_back({x+a,y+b});
            if(!b) row.push_back({x+a,y+b});
            if(!a) col.push_back({x+a,y+b});
        }
        if(i==M) break;
        if(S[i]=='N') x--;
        else if(S[i]=='S') x++;
        else if(S[i]=='W') y--;
        else y++;
    }
    g.init(G);p.init(P);
    rw.init(row);cc.init(col);
}

int colour(int ar, int ac, int br, int bc) {
    int V=p.get(ar+1,ac+1,br,bc);
    int E=rw.get(ar+1,ac,br,bc)+cc.get(ar,ac+1,br,bc);
    int total=g.get(ar,ac,br,bc),mid=0;
    if(ar+2<=br && ac+2<=bc) mid=g.get(ar+1,ac+1,br-1,bc-1);
    int CC=1;
    if(V>=1 && (total-mid)==0) CC++;
    //cout << E << ' ' << V << ' ' << CC << ' ' << total << '\n';
    return E-V+CC-total;
 }

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