Submission #218329

#	Time	Username	Problem	Language	Result	Execution time	Memory
218329		anonymous	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1170 ms	169724 KiB

rainbow

#include "rainbow.h"
#include <set>
#include <utility>
#include <iostream>
#define MAXN 200005
using namespace std;
 
class PersistentSegtree {
    int ST[MAXN*40][3], R[MAXN*2], X[MAXN*2];
    int V=1, P=1;
    int upd(int ind, int l, int r, int cur) {
        if (l > ind || ind > r) {return(cur);}
        if (l == r) {
            ST[V][0] = ST[cur][0] + 1, V++;
            return(V-1);
        } else {
            int mid = (l + r) >> 1, at = V;
            V++;
            ST[at][1] = upd(ind, l, mid, ST[cur][1]);
            ST[at][2] = upd(ind, mid+1, r, ST[cur][2]);
            ST[at][0] = ST[ST[at][1]][0] + ST[ST[at][2]][0];
            return(at);
        }
    }
    int ask(int lo, int hi, int l, int r, int cur) {
        if (l > hi || r < lo || cur == 0) {return(0);}
        else if (lo <= l && hi >= r) {return(ST[cur][0]);}
        else {
            int mid = (l + r) >> 1;
            return(ask(lo, hi, l, mid, ST[cur][1])+
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
public:
    void put(int x, int y) {
        X[P] = x;
        R[P] = upd(y, 1, MAXN, R[P-1]);
        P++;
    }
    int lb(int x) {
        int lo = 0, hi = P;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (X[mid] > x) {hi = mid;}
            else {lo = mid;}
        }
        return(lo);
    }
    int ask(int xlo, int ylo, int xhi, int yhi) {
        if (xlo > xhi || ylo > yhi) {return(0);}
        int ql = lb(xlo-1), qr = lb(xhi);
        return(ask(ylo, yhi, 1, MAXN, R[qr])-
               ask(ylo, yhi, 1, MAXN, R[ql]));
    }
} rT, vT, hT, VT;
int R,C;
set<pair<int,int> > rS, vS, hS, VS;
 
void init(int r, int c, int sr, int sc, int M, char *S) {
    R = r, C = c;
    int x = sr, y = sc; //cur
    for (int i=0; i<=M; i++) {
        rS.insert({x, y}); //river
        vS.insert({x,y}); //lines
        vS.insert({x,y+1});
        hS.insert({x,y});
        hS.insert({x+1,y});
        VS.insert({x,y}); //vertex
        VS.insert({x+1,y});
        VS.insert({x,y+1});
        VS.insert({x+1,y+1});
        if (i == M) {break;}
        switch(S[i]) {
            case 'N':
                x--;
                break;
            case 'S':
                x++;
                break;
            case 'W':
                y--;
                break;
            case 'E':
                y++;
                break;
        }
    }
    for (auto p: rS) {
        rT.put(p.first,p.second);
    }
    for (auto p: vS) {
        vT.put(p.first,p.second);
    }
    for (auto p: hS) {
        hT.put(p.first,p.second);
    }
    for (auto p: VS) {
        VT.put(p.first,p.second);
    }
}
 
int colour(int ar, int ac, int br, int bc) {
    int V = VT.ask(ar+1, ac+1, br, bc); 
    int Fr = rT.ask(ar, ac, br, bc);
    int E = hT.ask(ar+1, ac, br, bc) + vT.ask(ar, ac+1, br, bc);
    int ans = E - V - Fr + 1;
    if (V == VS.size()) {ans+=1;}
    return(ans);
}

Compilation message (stderr)

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (V == VS.size()) {ans+=1;}
         ~~^~~~~~~~~~~~

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