Submission #59356

#	Time	Username	Problem	Language	Result	Execution time	Memory
59356		duality	Land of the Rainbow Gold (APIO17_rainbow)	C++11	12 / 100	153 ms	42720 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#include "rainbow.h"

int r,c;
vpii p;
int grid[2][200000];
vpii r1,r2,r12;
void init(int R,int C,int sr,int sc,int M,char *S) {
    int i;
    r = R,c = C;
    sr--,sc--;
    p.pb(mp(sr,sc));
    for (i = 0; i < M; i++) {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'W') sc--;
        else sc++;
        p.pb(mp(sr,sc));
    }
    sort(p.begin(),p.end());
    p.resize(unique(p.begin(),p.end())-p.begin());
    //cout<<"hhh"<<endl;
    //for (i=0;i<p.size();i++)cout<<p[i].first<<","<<p[i].second<<endl;
    if (R == 2) {
        for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
        int pre = -1;
        for (i = 0; i < C; i++) {
            if (grid[0][i]) {
                if (pre != (i-1)) r1.pb(mp(pre+1,i-1));
                pre = i;
            }
        }
        if (pre != C-1) r1.pb(mp(pre+1,C-1));
        pre = -1;
        for (i = 0; i < C; i++) {
            if (grid[1][i]) {
                if (pre != (i-1)) r2.pb(mp(pre+1,i-1));
                pre = i;
            }
        }
        if (pre != C-1) r2.pb(mp(pre+1,C-1));
        pre = -1;
        for (i = 0; i < C; i++) {
            if (grid[0][i] && grid[1][i]) {
                if (pre != (i-1)) r12.pb(mp(pre+1,i-1));
                pre = i;
            }
        }
        if (pre != C-1) r12.pb(mp(pre+1,C-1));
        //cout<<"hhhh"<<endl;
    }
    else {

    }
}

int colour(int ar,int ac,int br,int bc) {
    ar--,ac--,br--,bc--;
    if (r == 2) {
        vpii *_use;
        //cout<<"here"<<endl;
        if ((ar == 0) && (br == 0)) _use = &r1;
        else if ((ar == 0) && (br == 1)) _use = &r12;
        else _use = &r2;
        //cout<<"here"<<endl;
        vpii &use = *_use;
        //for (int i = 0;i<use.size();i++)cout<<use[i].first<<","<<use[i].second<<" ";
        int l = lower_bound(use.begin(),use.end(),mp(ac,0))-use.begin()-1;
        if ((l == -1) || (use[l].second < ac)) l++;
        int r = upper_bound(use.begin(),use.end(),mp(bc,c))-use.begin()-1;
        return r-l+1;
    }
    return 1;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
                     ~~^~~~~~~~~~

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