Submission #166350

#	Time	Username	Problem	Language	Result	Execution time	Memory
166350		combi1k1	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1315 ms	80932 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

#define pb  emplace_back

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

const int   N   = 2e5 + 1;

typedef pair<int,int>   ii;
typedef vector<int>     vi;

vector<vi>  dx = {{0},{0,1},{0},{0,1}};
vector<vi>  dy = {{0},{0,1},{0,1},{0}};

struct  BIT2D   {
    vector<ii>  add;
    vector<int> v[N];
    void ini()  {
        sort(add.begin(),add.end());
        add.erase(unique(add.begin(),add.end()),add.end());
        for(ii  a : add)
        for(int x = a.X ; x < N ; x += x & -x)
            v[x].push_back(a.Y);
        for(int i = 1 ; i < N ; ++i)
            sort(v[i].begin(),v[i].end());
    }
    int get(int x,int l,int r)  {
        int ans = 0;
        for(; x > 0 ; x -= x & -x)  {
            auto L = lower_bound(v[x].begin(),v[x].end(),l);
            auto R = upper_bound(v[x].begin(),v[x].end(),r);

            ans += R - L;
        }
        return  ans;
    }
    int get(int l,int r,int u,int d)    {
        if (l > r)  return  0;
        if (u > d)  return  0;

        return  get(r,u,d) - get(l - 1,u,d);
    }
}   T[4];

int min_r =  1e9, min_c =  1e9;
int max_r = -1e9, max_c = -1e9;

void rose(ii  P)    {
    min_r = min(min_r,P.X); max_r = max(max_r,P.X);
    min_c = min(min_c,P.Y); max_c = max(max_c,P.Y);

    for(int i = 0 ; i < 4 ; ++i)
    for(int x : dx[i])
    for(int y : dy[i])  T[i].add.pb(P.X + x,P.Y + y);
}
void init(int R,int C,int sr,int sc,int m,char *S)  {
    ii  Head(sr,sc);    rose(Head);

    for(int i = 0 ; i < m ; ++i)    {
        char c = S[i];
        if (c == 'N')   Head.X--;
        if (c == 'S')   Head.X++;
        if (c == 'W')   Head.Y--;
        if (c == 'E')   Head.Y++;

        rose(Head);
    }
    for(int i = 0 ; i < 4 ; ++i)    T[i].ini();
}
int colour(int l,int u,int r,int d) {
    int V = T[1].get(l + 1,r,u + 1,d);
    int F = T[0].get(l,r,u,d);
    int E = T[2].get(l,r,u + 1,d) + T[3].get(l + 1,r,u,d);

    return  E - V - F + 1 + (l < min_r && max_r < r && u < min_c && max_c < d);
}

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