Submission #155786

#	Time	Username	Problem	Language	Result	Execution time	Memory
155786		mhy908	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	1984 ms	1048580 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(t) t.begin(), t.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int tt;

struct MERGE_SORT_TREE {
    struct NODE {
        int st, fin;
        int l, r;
        vector<int> vc;
    };
    vector<NODE> tree;
    void newNode(int a, int b) {
        NODE temp;
        temp.st=a;
        temp.fin=b;
        temp.l=temp.r=0;
        tree.pb(temp);
        //printf("%d\n", tree.size());
        tt=tree.size();
    }
    void in_DST(int point, int num, int p) {
        tree[point].vc.pb(p);
        if(tree[point].st==tree[point].fin)return;
        int mid=(tree[point].st+tree[point].fin)/2;
        //printf("%d %d %d %d\n", tree[point].l, tree[point].r, tree[point].st, tree[point].fin);
        if(!tree[point].l)newNode(tree[point].st, mid), tree[point].l=tt-1;
        if(!tree[point].r)newNode(mid+1, tree[point].fin), tree[point].r=tt-1;
        //printf("%d %d %d %d\n", tree[point].l, tree[point].r, tree[point].st, tree[point].fin);
        if(num<=mid)in_DST(tree[point].l, num, p);
        else in_DST(tree[point].r, num, p);
    }
    void relax(int point){
        sort(all(tree[point].vc));
        if(tree[point].l)relax(tree[point].l);
        if(tree[point].r)relax(tree[point].r);
    }
    int sumrange(int point, int xl, int xr, int yl, int yr){
        if(tree[point].st>=xl&&tree[point].fin<=xr)
            return upper_bound(all(tree[point].vc), yr)-lower_bound(all(tree[point].vc), yl);
        if(tree[point].st>xl||tree[point].fin<xr)return 0;
        return sumrange(tree[point].l, xl, xr, yl, yr)+sumrange(tree[point].r, xl, xr, yl, yr);
    }
    MERGE_SORT_TREE(){newNode(0, 300000);}
    void update(int num, int p){
        in_DST(0, num, p);
    }
    int get_sum(int xl, int xr, int yl, int yr){
        if(xl>xr||yl>yr)return 0;
        return sumrange(0, xl, xr, yl, yr);
    }
};
MERGE_SORT_TREE seg, segdown, segright, segf;
int n, m;
unordered_set<LL> us;
vector<pii> a, b;
void invec(int x, int y)
{
    a.pb(mp(x, y));
    b.pb(mp(x, y));
    b.pb(mp(x-1, y));
    b.pb(mp(x, y-1));
    b.pb(mp(x-1, y-1));
}
void init(int R, int C, int sr, int sc, int M, char S[]){
    n=R;
    m=C;
    invec(sr, sc);
    for(int i=0; i<M; i++){
        if(S[i]=='N')sr--;
        if(S[i]=='S')sr++;
        if(S[i]=='W')sc--;
        if(S[i]=='E')sc++;
        invec(sr, sc);
    }
    sort(all(a));
    sort(all(b));
    a.erase(unique(all(a)), a.end());
    b.erase(unique(all(b)), b.end());
    for(int i=0; i<a.size(); i++)seg.update(a[i].x, a[i].y);
    for(int i=0; i<b.size(); i++){
        int xx=b[i].x, yy=b[i].y;
        segf.update(xx, yy);
        if(binary_search(all(a), mp(xx, yy))||binary_search(all(a), mp(xx+1, yy)))segdown.update(xx, yy);
        if(binary_search(all(a), mp(xx, yy))||binary_search(all(a), mp(xx, yy+1)))segright.update(xx, yy);
    }
    seg.relax(0);
    segf.relax(0);
    segdown.relax(0);
    segright.relax(0);
}
int colour(int ar, int br, int ac, int bc) {
    int v=segf.get_sum(ar, ac-1, br, bc-1)+2*(bc-br+1+ac-ar+1);
    int e=segright.get_sum(ar, ac-1, br, bc)+segdown.get_sum(ar, ac, br, bc-1)+2*(bc-br+1+ac-ar+1);
    int temp=seg.get_sum(ar, ac, br, bc);
    //printf("v=%d e=%d f=%d\n", v, e, temp);
    if(temp==0||seg.get_sum(ar, ar, br, bc)||seg.get_sum(ac, ac, br, bc)||seg.get_sum(ar, ac, br, br)||seg.get_sum(ar, ac, bc, bc))return e-v+1-temp;
    return e-v+2-temp;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++)seg.update(a[i].x, a[i].y);
                  ~^~~~~~~~~
rainbow.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<b.size(); i++){
                  ~^~~~~~~~~

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