Submission #155292

#	Time	Username	Problem	Language	Result	Execution time	Memory
155292		arnold518	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1842 ms	140132 KiB

rainbow

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int R, C;

struct SEG
{
    vector<int> tree[MAXN*4+10];

    void push(int node, int tl, int tr, int pos, int val)
    {
        if(tl==tr) { tree[node].push_back(val); return; }
        int mid=tl+tr>>1;
        if(pos<=mid) push(node*2, tl, mid, pos, val);
        else push(node*2+1, mid+1, tr, pos, val);
    }
    void push(int pos, int val) { push(1, 0, C, pos, val); }

    void init(int node, int tl, int tr)
    {
        if(tl==tr)
        {
            sort(tree[node].begin(), tree[node].end());
            return;
        }
        int mid=tl+tr>>1;
        init(node*2, tl, mid);
        init(node*2+1, mid+1, tr);
        tree[node].resize(tree[node*2].size()+tree[node*2+1].size());
        merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin());
    }
    void init() { init(1, 0, C); }

    int query(int node, int tl, int tr, int xl, int xr, int yl, int yr)
    {
        if(xl>xr || yl>yr) return 0;
        if(xr<tl || tr<xl) return 0;
        if(xl<=tl && tr<=xr) return upper_bound(tree[node].begin(), tree[node].end(), yr)-lower_bound(tree[node].begin(), tree[node].end(), yl);
        int mid=tl+tr>>1;
        return query(node*2, tl, mid, xl, xr, yl, yr)+query(node*2+1, mid+1, tr, xl, xr, yl, yr);
    }
    int query(int xl, int xr, int yl, int yr) { return query(1, 0, C, xl, xr, yl, yr); }
};
SEG segv, sege1, sege2, segf;

void init(int _R, int _C, int sy, int sx, int M, char *S)
{
    int i, j;
    R=_R; C=_C;

    vector<pii> T, TT;
    T.push_back({sx, sy});
    TT.push_back({sx, sy});
    TT.push_back({sx-1, sy});
    TT.push_back({sx, sy-1});
    TT.push_back({sx-1, sy-1});
    for(i=0; i<M; i++)
    {
        if(S[i]=='N') sy--;
        if(S[i]=='W') sx--;
        if(S[i]=='S') sy++;
        if(S[i]=='E') sx++;
        T.push_back({sx, sy});
        TT.push_back({sx, sy});
        TT.push_back({sx-1, sy});
        TT.push_back({sx, sy-1});
        TT.push_back({sx-1, sy-1});
    }
    sort(T.begin(), T.end());
    T.erase(unique(T.begin(), T.end()), T.end());

    sort(TT.begin(), TT.end());
    TT.erase(unique(TT.begin(), TT.end()), TT.end());

    for(auto it : TT) segv.push(it.first, it.second);
    for(auto it : TT) if(binary_search(T.begin(), T.end(), pii(it.first, it.second)) || binary_search(T.begin(), T.end(), pii(it.first, it.second+1))) sege1.push(it.first, it.second);
    for(auto it : TT) if(binary_search(T.begin(), T.end(), pii(it.first, it.second)) || binary_search(T.begin(), T.end(), pii(it.first+1, it.second))) sege2.push(it.first, it.second);
    for(auto it : T) segf.push(it.first, it.second);

    segv.init();
    sege1.init();
    sege2.init();
    segf.init();
}

int colour(int Y1, int X1, int Y2, int X2)
{
    ll v, e, f, c;
    v=segv.query(X1, X2-1, Y1, Y2-1)+2*((ll)Y2-Y1+X2-X1+2);
    e=sege1.query(X1, X2, Y1, Y2-1)+sege2.query(X1, X2-1, Y1, Y2)+2*((ll)Y2-Y1+X2-X1+2);
    f=segf.query(X1, X2, Y1, Y2);
    if(f==0) c=1;
    else if(segf.query(X1, X2, Y1, Y1) || segf.query(X1, X2, Y2, Y2) || segf.query(X1, X1, Y1, Y2) || segf.query(X2, X2, Y1, Y2)) c=1;
    else c=2;

    //printf("%lld %lld %lld %lld\n", v, e, f, c);
    //printf("============================================\n");
    return c-v+e-f;
}

Compilation message (stderr)

rainbow.cpp: In member function 'void SEG::push(int, int, int, int, int)':
rainbow.cpp:20:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In member function 'void SEG::init(int, int, int)':
rainbow.cpp:33:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In member function 'int SEG::query(int, int, int, int, int, int, int)':
rainbow.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:55:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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